Using a Stack to Find Unbalanced Parentheses

Stacks are a really cool data structure, they’re really simple to use and they get used all over the place in Computer Science.

If you’ve ever done a calculation involving parenthesis (parens), or a complicated if-statement, you’ll know your code doesn’t work correctly when the parens are unbalanced.

Stacks are a cool way to quickly check an expression’s parens match.

For example:

( 2 * ( 1 + 3 )

The expression above has two opening parens but only one closing one, so it’s unbalanced. In the next expression, the parens are balanced - for each opening paren there’s a closing one.

(2 * ( 1 + 3 ) )

One place where this might be useful is when we’re parsing an expression, maybe we’re building a calculator, in that case matching the parens will be important.

THE CODE

def valid_parens(expr):
    stack = []
    for char in expr:
        if char == '(':
            stack.append(char)
        elif char == ')':
            try:
                stack.pop()
            except IndexError:
                return False

    if len(stack) != 0:
        return False
    return True

print(check_parens( '(1+3)' ))  # returns True
print(check_parens( '(1+3(' ))  # returns False

The check_parens function returns True if the parens are balanced and False otherwise. It works like this:

  • It loops over each character in the expression, ignoring anything which isn’t a ( or a )
  • Each time it sees a ( it pushes it onto the stack
  • Each time it sees a ) it pops the top of the stack off.
  • If stack.pop() throws an IndexError it means the stack was already empty before the current ), so the parens must be unbalanced - there aren’t enough opening parens for the number of closing ones.
  • After looping through the entire expression the stack should be empty, if it’s not we know there were too many ( and not enough ).

And that’s it!