Editor

Balanced brackets with a stack in Python

A stack checks that brackets are balanced: every opening bracket is pushed, and every closing bracket must match the one on top of the stack. Last in, first out is exactly how nested brackets close.

The arrow keys step through it. Edit the code to try your own input.

How it works

  1. Opening brackets are pushed onto stack with append.
  2. A closing bracket must match the opener on top of the stack. pairs maps each closer to its opener, and pop() takes the top one off.
  3. A closer that finds the stack empty, or matches the wrong opener, means the text is not balanced.
  4. At the end the stack must be empty: any opener still on it was never closed.

What to watch

  • Watch stack grow and shrink at its right end: the last opener in is the first one out.
  • Watch ([)] fail at ): the top of the stack is [, not (.
  • Watch (() get through every character and still fail, because one ( is left on the stack.

The code

def is_balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for char in text:
        if char in "([{":
            stack.append(char)          # remember the opener
        elif char in pairs:
            if not stack:
                return False            # a closer with no opener
            if stack.pop() != pairs[char]:
                return False            # closes the wrong opener
    return not stack                    # leftovers were never closed

for text in ["{[()()]}", "([)]", "(()"]:
    print(text, is_balanced(text))
Output
{[()()]} True
([)] False
(() False

Open it in the editor · Python Program to Check Balanced Parentheses Using a Stack, explained