This discussion is archived
4 Replies Latest reply: Apr 30, 2013 7:05 PM by rp0428 RSS

Give me technical idea to solve this requirement

NothingNatarajan Newbie
Currently Being Moderated
Analyze and develop a program in java which reads a sentence which may contain any type of brackets (Eg : ‘(’, ’)’, ‘{’,  ’}’, ’[’, ’]’ ). The brackets in the sentence may not have closed properly.
-     First task is to validate whether the brackets are closed properly. State true or false.
-     Next task is to read the sentence and identify the position (index and word) at which the bracket is not closed properly. Also you need to identify what type brackets need to be placed in order to close the sentence properly.

Sample Input :
Input Sentence :
{ A recruitment was conducted in a college (SREC  on April 20,2013 [Saturday] for all colleges

Sample Output :
Index at which ‘)’ needs to be placed : 43, SREC
Index at which ‘}’ needs to be placed : 90, colleges
Output Sentence :
{ A recruitment was conducted in a college (SREC)  on April 20,2013 [Saturday] for all colleges}

I tried using Stack Data Structure. But i can't get it correctly. If u have any idea or any code to implement this means please Help me,


Thanks In Advance..
  • 1. Re: Give me technical idea to solve this requirement
    maheshguruswamy Journeyer
    Currently Being Moderated
    1003292 wrote:
    Analyze and develop a program in java which reads a sentence which may contain any type of brackets (Eg : ‘(’, ’)’, ‘{’,  ’}’, ’[’, ’]’ ). The brackets in the sentence may not have closed properly.
    -     First task is to validate whether the brackets are closed properly. State true or false.
    -     Next task is to read the sentence and identify the position (index and word) at which the bracket is not closed properly. Also you need to identify what type brackets need to be placed in order to close the sentence properly.

    Sample Input :
    Input Sentence :
    { A recruitment was conducted in a college (SREC  on April 20,2013 [Saturday] for all colleges

    Sample Output :
    Index at which ‘)’ needs to be placed : 43, SREC
    Index at which ‘}’ needs to be placed : 90, colleges
    Output Sentence :
    { A recruitment was conducted in a college (SREC)  on April 20,2013 [Saturday] for all colleges}

    I tried using Stack Data Structure. But i can't get it correctly. If u have any idea or any code to implement this means please Help me,


    Thanks In Advance..
    Can you post the code that you have written so far?
  • 2. Re: Give me technical idea to solve this requirement
    rp0428 Guru
    Currently Being Moderated
    >
    Analyze and develop a program in java which reads a sentence which may contain any type of brackets (Eg : ‘(’, ’)’, ‘{’, ’}’, ’[’, ’]’ ). The brackets in the sentence may not have closed properly.
    - First task is to validate whether the brackets are closed properly. State true or false.
    >
    Simple - just count the number of 'left' (opening) occurences for each bracket and count the number of 'right' (closing) occurences. If the number of left and right are differenct then that bracket type is not closed.
    >
    - Next task is to read the sentence and identify the position (index and word) at which the bracket is not closed properly. Also you need to identify what type brackets need to be placed in order to close the sentence properly.
    >
    That isn't possible at all given only the information that you posted. Any bracket type is 'closed' when the number of 'right' occurences equals the number of 'left occurences. There is NO way to tell where any needed 'right' occurences should be placed to do the closure so the only place you can put them is at the END of the sentence.
    >
    Sample Input :
    Input Sentence :
    { A recruitment was conducted in a college (SREC on April 20,2013 [Saturday] for all colleges

    Sample Output :
    Index at which ‘)’ needs to be placed : 43, SREC
    Index at which ‘}’ needs to be placed : 90, colleges
    Output Sentence :
    { A recruitment was conducted in a college (SREC) on April 20,2013 [Saturday] for all colleges}
    >
    Given only what you posted that is NOT the only possibility. You have provided no rule by which to decide that the ')' should be placed immediately after the word 'SREC'. It could just as easily be placed after '2013', after 'for', after 'all', after 'colleges' or at the end of the sentence. Nothing in the requirement you provided makes any of those placements wrong.

    This output is equally valid
    >
    { A recruitment was conducted in a college (SREC on April 20,2013 [Saturday for all colleges})]
    >
    No rule was stated about brackets not being able to overlap. Even if there was then this would still be valid:
    >
    { A recruitment was conducted in a college (SREC on April 20,2013) [Saturday for all colleges]}
    >
    That is a very poor requirement as there is not nearly enough information to use to make the necessary decisions as to the proper placement of any missing brackets.
  • 3. Re: Give me technical idea to solve this requirement
    EJP Guru
    Currently Being Moderated
    Simple - just count the number of 'left' (opening) occurences for each bracket and count the number of 'right' (closing) occurences. If the number of left and right are differenct then that bracket type is not closed.
    It would be better to use a stack. Push each left bracket as you encounter it. Pop it when you reach the matching right bracket.
    That isn't possible at all given only the information that you posted.
    Yes it is. When you encounter a closing bracket, if the top of the stack isn't the same type (e.g. '{' for '}'), then either this is an extra closing bracket with no matching opener, or the closing bracket for the opener on top of the stack is missing at this point in the input. You can tell which was which by knowing the total counts of each, which you could do in a prior scan.
  • 4. Re: Give me technical idea to solve this requirement
    rp0428 Guru
    Currently Being Moderated
    >
    Yes it is. When you encounter a closing bracket, if the top of the stack isn't the same type (e.g. '{' for '}'), then either this is an extra closing bracket with no matching opener, or the closing bracket for the opener on top of the stack is missing at this point in the input. You can tell which was which by knowing the total counts of each, which you could do in a prior scan.
    >
    No - it isn't. Not based solely on the information provided.
    >
    Analyze and develop a program in java which reads a sentence which may contain any type of brackets (Eg : ‘(’, ’)’, ‘{’, ’}’, ’[’, ’]’ ).
    >
    You need to reread my reply where I said this:
    >
    Given only what you posted that is NOT the only possibility. You have provided no rule by which to decide that the ')' should be placed immediately after the word 'SREC'. It could just as easily be placed after '2013', after 'for', after 'all', after 'colleges' or at the end of the sentence. Nothing in the requirement you provided makes any of those placements wrong.
    >
    Even using your assumptions that different bracket types can not overlap there is absolutely NO WAY to tell where a closing bracket belongs.

    OP provided this an input
    >
    { A recruitment was conducted in a college (SREC on April 20,2013 [Saturday] for all colleges
    >
    and provided this as the only correct output
    >
    { A recruitment was conducted in a college (SREC) on April 20,2013 [Saturday] for all colleges}
    >
    There is NO basis for concluding that the closing right parethesis belongs after the word 'SREC' or that the closing brace belongs ONLY at the end of the entire phrase.

    Any such business rules that apply to the proper determination of the placement of missing brackets need to be stated; not assumed.

    As for this
    >
    It would be better to use a stack. Push each left bracket as you encounter it. Pop it when you reach the matching right bracket.
    >
    That is the wrong approach as well. You can't pop a right bracket from an empty stack. And there are three different types of 'brackets', not just one. Using a stack doesn't buy you anything. The process doesn't involve nested evaluation like you might have with an arithmetic expression processor.

    Only simple counting is needed.

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points