On 2010-6-11 13:39, BALARUKESH wrote:
The increment and decrement method wont work correctly for all
cases....
Ex:-
))a+b((
It works. In this example, the first ')' lead to -1 which indicate the
expression is not well formed.
This is not a well formed parenthesis... But satisfies the algorithm.
The better way is to use a stack... When u find a ' ( ' push it into
the stack and when u find a ' )' pop off the top element. Finally the
stack should be empty. If [stack has one or more ' ( ' ] or [the stack
is empty and exp is not empty] then it is not a well formed
parenthesis...
The later condition [the stack is empty and exp is not empty] does not
necessary lead to ill formed parenthesis. Ex: (a+b)*(c+d).
To solve this, you can 1) add an additional pair of parenthesis around
the whole expression
or 2) change the condition to [the stack is empty and ')' is the next
element of the expression]
Actually, the increment and decrement method is maintaining the stack
size, checking 1) no stack underflow, and 2) stack is empty at the end.
So the two method is equivalent.
--
You received this message because you are subscribed to the Google Groups "Algorithm
Geeks" group.
To post to this group, send email to algoge...@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.
