Algorithm to Check Matching of Parentheses


Input: Sequence T = T1...Tn of n tokens.
Output: TRUE if the parentheses in T are correctly matched; FALSE otherwise.
 
S ← new stack // S stores unmatched opening parentheses.

for each i in 1..n
{
   x ← Ti 
   if x is '('
   { 
      push x on S 
   }
   else if x is ')'
   {
      if S is empty 
      {
         // too many ')'s
         return FALSE         
      }
      pop S
   }
   // Note: if x is not a '(' or ')', we just ignore it.
}
if S is not empty 
{  
   // too many '('s
   return FALSE
} 
// If execution reachees this point, we claim: 
//   - every token has been read, 
//   - all parentheses have been matched correctly.
return TRUE

Exercise: Notice that we don't really need the stack. The only thing is stores is '('s, so it is sufficient to keep track of how many of have been read but not yet matched. We can do this just with a counter. Re-write the given pseudo-code to use a counter (and integer variable) instead of the stack. Intuitively, push becomes +1, pop becomes -1, etc.