Re: [algogeeks] Re: Return index of first mismatch bracket "(" or ")"

Terence Thu, 22 Dec 2011 05:49:38 -0800

And I think the comparing between first unmatched open/close bracketindex is not needed.

If we found an unmatched close bracket (ie. the stack is empty whenencounter a close bracket),we could return current index immediately, since all open bracketsbefore that position are matched and popped out.

If we could not find an unmatched close bracket, and the stack is notempty,

we examine the stack and return the bottom index (the left most unmatched),
or the top index (the inner most unmatch) as needed.

On 2011-12-22 13:27, Terence wrote:

Then what's your output for test case "()(()"?

On 2011-12-22 12:45, atul anand wrote:

i guess there is no need of stack , we can take a variable say top;

increment top when open bracket occur "(" and decrement when closebracket ")" occurs.

keep track of first close bracket mismatch i.e when top is zero andcurrent bracket is ")".


if top!=0
       report min(index,top);

On Tue, Dec 20, 2011 at 11:06 PM, shady <sinv...@gmail.com<mailto:sinv...@gmail.com>> wrote:


    true, we have to look at the entire string to find the first
    mismatch,
    and its meaning depends on how you interpret it... either way stack
    will solve it :)

    On Dec 20, 10:32 pm, Arun Vishwanathan <aaron.nar...@gmail.com
    <mailto:aaron.nar...@gmail.com>> wrote:
    > @shady: I guess first mismatch means the innermost open brace
    that doesnt
    > have a close brace. U cannot know that the first brace does not
    have a
    > closing one unless u look at the entire string.
    >
    >
    >
    >
    >
    >
    >
    >
    >
    > On Tue, Dec 20, 2011 at 9:23 AM, shady <sinv...@gmail.com
    <mailto:sinv...@gmail.com>> wrote:
    > > ( ( ) ( ( ) ( ( ) ) (  )  for this SAMM faulty index is 0,
    because the
    > > first bracket has itself found no matching....
    >
    > > @atul
    > > ( ( ( () ) ) for this first bracket is faulty as it couldn't
    find a
    > > closing bracket, , ,
    > > you can keep a stack with map as element
    > > stack< map<int, char> >
    >
    > > map<int, char> where integer is the index of the bracket,
    which is stored
    > > as char
    > > idea is similar to don's.
    >
    > > On Tue, Dec 20, 2011 at 10:42 PM, atul anand
    <atul.87fri...@gmail.com <mailto:atul.87fri...@gmail.com>>wrote:
    >
    > >> there are multiple mismatch or only one mis-match in the
    input string.
    >
    > >> if the given string as below :-
    >
    > >> ( ( ( () ) ) -> for this is missing match is for 1st , 2nd
    or 3rd
    > >> bracket.
    >
    > >> what would be the answer for this.
    >
    > >> On Tue, Dec 20, 2011 at 8:10 PM, zeroByZero
    <shri.nit...@gmail.com <mailto:shri.nit...@gmail.com>>wrote:
    >
    > >>> In a given string arrary arr[] = "((()())" or any other
    string return
    > >>> index for which no match is found as for this example is
    index 0 and
    > >>> for "()()()(()" is index 6
    >
    > >>> --
    > >>> You received this message because you are subscribed to the
    Google
    > >>> Groups "Algorithm Geeks" group.
    > >>> To post to this group, send email to
    algogeeks@googlegroups.com <mailto:algogeeks@googlegroups.com>.
    > >>> To unsubscribe from this group, send email to
    > >>> algogeeks+unsubscr...@googlegroups.com
    <mailto:algogeeks%2bunsubscr...@googlegroups.com>.
    > >>> For more options, visit this group at
    > >>>http://groups.google.com/group/algogeeks?hl=en.
    >
    > >>  --
    > >> You received this message because you are subscribed to the
    Google Groups
    > >> "Algorithm Geeks" group.
    > >> To post to this group, send email to
    algogeeks@googlegroups.com <mailto:algogeeks@googlegroups.com>.
    > >> To unsubscribe from this group, send email to
    > >> algogeeks+unsubscr...@googlegroups.com
    <mailto:algogeeks%2bunsubscr...@googlegroups.com>.
    > >> For more options, visit this group at
    > >>http://groups.google.com/group/algogeeks?hl=en.
    >
    > >  --
    > > You received this message because you are subscribed to the
    Google Groups
    > > "Algorithm Geeks" group.
    > > To post to this group, send email to
    algogeeks@googlegroups.com <mailto:algogeeks@googlegroups.com>.
    > > To unsubscribe from this group, send email to
    > > algogeeks+unsubscr...@googlegroups.com
    <mailto:algogeeks%2bunsubscr...@googlegroups.com>.
    > > For more options, visit this group at
    > >http://groups.google.com/group/algogeeks?hl=en.
    >
    > --
    >  "People often say that motivation doesn't last. Well, neither
    does bathing
    > - that's why we recommend it daily."

    --
    You received this message because you are subscribed to the
    Google Groups "Algorithm Geeks" group.
    To post to this group, send email to algogeeks@googlegroups.com
    <mailto:algogeeks@googlegroups.com>.
    To unsubscribe from this group, send email to
    algogeeks+unsubscr...@googlegroups.com
    <mailto:algogeeks%2bunsubscr...@googlegroups.com>.
    For more options, visit this group at
    http://groups.google.com/group/algogeeks?hl=en.


--

You received this message because you are subscribed to the GoogleGroups "Algorithm Geeks" group.

To post to this group, send email to algogeeks@googlegroups.com.

To unsubscribe from this group, send email toalgogeeks+unsubscr...@googlegroups.com.For more options, visit this group athttp://groups.google.com/group/algogeeks?hl=en.


--
You received this message because you are subscribed to the Google Groups "Algorithm 
Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Return index of first mismatch bracket "(" or ")"

Reply via email to