Parenthesis Stack:

Consider a mathematical expression that includes several sets of nested parenthesis.

7 – ((x * (( x + y) / (j - 3)) + Y) / (4 – 2))

In expression we want to check

1. There are an equal number of right and left parenthesis.
2.  Every right parenthesis is preceded by a matching left parenthesis.

Expressions like ((A+B) or A+B( violates condition 1 and expressions like )A + B(-C violate condition 2.

Nested Depth: is the number of scopes that have been opened and not yet closed.

Parenthesis count: no of left parenthesis – no of right parenthesis.

Expression id valid if following conditions are met.

•  Parenthesis count at end should be zero.
•  Parenthesis count at each point in expression should be non negative.

              7 – ( ( x *  ( (  x + y )  / ( j -  3  )  ) + Y )  / ( 4 – 2.5 ) )

              0 0 1 2 2 2 3 4 4 4 4 3 3 4 4 4 4 3 2 2  2 1 1 2 2 2  2 1 0

               ( ( A + B ) and (A + B] is illegal

         1  2 2 2 2 1

Algorithm for Example:

valid = true

s = empty stack;

while (we have not read the entire string) {

     read the next symbol (symb) in the string;

     if (symb == ‘(’ || symb == ‘{’ || symb == ‘[’ )

         s.push(symb);

   if (symb == ‘)’ || symb == ‘}’ || symb == ‘]’ )

         if (empty(s))

            valid = false;

         else{

               i = s.pop();

               if (i is not the matching opener of symb)

                 valid = false }

}// end of while

if (!s.empty()) valid = false;

if (valid)

   cout << “String is valid”;

else cout << “String is not valid”;

Dry Run for parenthesis stack: