How to Check for Matching Parenthesis

Another common whiteboarding question you will be asked is to create a function where you need to check a given expression if all open parentheses have matching close parentheses or vice versa.

An example of expression is: {{[([({{(([]){})){}((((((]}]}}

Evaluating this expression will result to false. 

It seems easy but it may be difficult for developers without so much experience on stacks or recursive functions. And as you've guessed it, we will solve the problem using stacks (I'll leave it up to you to approach it thru recursion as an exercise).

But why stacks? The trick here is to find patterns by doing it on paper and see what data structure can best represent your findings.

Well, consider evaluating the simple expression below. Certainly, you can do it by hand by striking thru matching parentheses.

• (a) { ( [ ] { } ) }          (b) { ( [ } ] ) { )
•     valid expression             invalid expression

If we find an open parenthesis, regardless of its type, we copy the parenthesis in our open pairs list. If we find a closing parenthesis then we cross out the closing parenthesis and remove the opening parenthesis in our list. It is noteworthy at this point to recognize that if the last open parenthesis doesn't match the closing then it's an invalid expression. We have to do this until the end of the expression. If there are expressions remaining in our Open Pairs List then we have invalid expression. Otherwise, it's valid.

As we have noticed in the figure above, the last opening parenthesis we put on our Open Pairs List, is the first item we compare with the close parenthesis. A LIFO data access method is necessary for our algorithm, hence we implement our solution using a stack.

You can use the regular stack data structure or a representation of a stack, i.e. stacks thru arrays, or stacks thru string concatenation / disjoin to implement last in first out method.

Want to try it out? Download the attached C++ program below.