In this algorithm, we use the term "parenthesis" to refer to traditional parentheses () but also curly brackets {} or other styles of brackets [].

When checking for balanced parentheses, we first remove all values and operators, leaving just the parentheses. Then there are four cases we need to look for:

balanced

example: { ( ) }

unbalanced- extra open parenthesis

example: { ( )

unbalanced- extra closed parenthesis

example: ( ) }

unbalanced- mismatched (cross-over) parentheses

example: { ( } )

Algorithm

The basic idea is to gather up open parentheses on the stack. When we find a close parenthesis, we pop the top element of the stack. The two parentheses should match. When we are done, the stack should be empty.

Here is the pseudocode:

while there are more tokens, read in a token

if the token is an open parenthesis

push the token onto the stack

else (the token is a closed parenthesis)

if the stack is empty

the expression is unbalanced (we're done- return false because of extra closed parentheses)

else (the stack is not empty)

pop a token

if the closed and open parenthesis don't match

the expression is unbalanced (we're done- return false because of mismatched parentheses)

// there are no more tokens left- the while loop is done

if the stack is empty

the expression is balanced (we're done- return true)

else (the stack has tokens remaining in it)

the expression is unbalanced (we're done- return false because of extra open parentheses)

Question: evaluate whether the 2 parentheses are balanced. Select the situation that will cause the algorithm to end.

a [ b [ c - d ] * e + { f / g } ) + h

mismatch found when popping from the stack

none of these is correct

closed parenthesis left on the stack

open parenthesis left on the stack

empty stack with no match for a close parenthesis

empty stack and no more tokens

Part 2A:

Is the expression balanced or unbalanced?

unbalanced because of an extra close parenthesis

unbalanced because of a mismatch in parentheses

balanced

unbalanced because of an extra open parenthesis

( a { b + c } + [ d * e ] - f ) / g ]

empty stack with no match for a close parenthesis

none of these is correct

open parenthesis left on the stack

empty stack and no more tokens

mismatch found when popping from the stack

closed parenthesis left on the stack

Part 2A:

Is the expression balanced or unbalanced?

balanced

unbalanced because of an extra close parenthesis

unbalanced because of an extra open parenthesis

unbalanced because of a mismatch in parentheses