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:

Each opening on the left delimiter must be matched by a closing (right) delimiter.
Left delimiters that occur later should be closed before those occurring earlier.

Examples

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:

Read the characters from the string.
Whenever you see a left (opening) delimiter, push it to the stack.
Whenever you see a right (closing) delimiter, pop the (hopefully matching) opening delimiter from the stack, and

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

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