Delimiter Matching

We are doing delimiter matching when we check to see if the parentheses in an expression -- like the one shown below -- are balanced.

$$( w \times ( x + y ) \,/\, z - ( p \,/\, ( r - q ) ) )$$

Of course, we are not limited to parentheses. We may have to ensure that several different types of delimiters are balanced (e.g., braces {}, brackets[], parentheses(), angle brackets<>). In doing so, we must ensure that:


c[d]          // correct
a{b[c]d}e     // correct
a{b(c]d}e     // not correct; the "]" after the c doesn't match the "(" after the b
a[b{c}d]e}    // not correct; nothing matches the final }
a{b(c)        // not correct; nothing matches the opening }

Delimeter Matching by Using Stacks

The below gives a simple algorithm that uses a stack to determine if the delimeters in an expression match:

  1. Read the characters from the string.

  2. Whenever you see a left (opening) delimiter, push it to the stack.

  3. Whenever you see a right (closing) delimiter, pop the (hopefully matching) opening delimiter from the stack, and

    1. If they don't match, report a matching error
    2. If you can't pop the stack because it is empty, report a missing left delimiter error

  4. If the stack is non-empty after all the characters of the expression have been processed, report a missing right delimeter error.