Algorithm to Check Matching and Nesting of Grouping Symbols


Input: Sequence T = T1...Tn of n tokens; set G of pairs of grouping symbols.
Output: TRUE if all grouping symbols in T are correctly matched and nested; FALSE otherwise.
 
S ← new stack // S stores unmatched opening ("left") symbols; last-read on top.

for each i in 1..n
{
   x ← Ti 
   if x is an opening symbol from G
   { 
      push x on S 
   }
   else if x is a closing symbol from G
   {
      if S is empty 
      {
         // too many closing symbols
         return FALSE         
      }
      y = pop S
      if x and y don't match 
      { 
         // mis-matched left and right symbols
         return FALSE
      }
   }
   // Note: if x is not a grouping symbol, we just ignore it.
}
if S is not empty 
{  
   // too many opening symbols
   return FALSE
} 
// If execution reaches this point, we claim: 
//   - every token has been read, 
//   - all grouping symbols have been paired up,
//   - no pair of symbols is incorrectly nested.
return TRUE

Exercises:
  1. Simulate the algorithm on a sample C++ program.
  2. Similate the algorithm on the same sample, modified to have various errors in grouping symbol matching or nesting.