juniorStacks

How do you check for balanced parentheses using a stack?

Updated Feb 20, 2026

Short answer

Scan the string once. Push every opening bracket; on a closing bracket, pop and check it matches the expected partner. The string is balanced if every closing bracket finds its match and the stack is empty at the end. It runs in O(n) time and O(n) space, and a stack is the natural fit because brackets close in last-opened-first-closed order.

Deep explanation

Python
def is_balanced(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False        # nothing to match, or the wrong opener
        # any other character is ignored
    return not stack                # leftovers mean unclosed openers

There are exactly three ways a string fails, and each maps to a line above:

  • Wrong type — ([)]. The pop returns [ where ( was needed.
  • Closing with nothing open — ()). The stack is empty when a closer arrives.
  • Unclosed opener — ((). The loop finishes with a non-empty stack.

The final return not stack is the one people forget, and it is what makes ((( fail correctly.

Why a stack and not a counter. A counter works for a single bracket type — increment on open, decrement on close, fail if it goes negative or ends non-zero. It cannot handle multiple types, because it loses the information about which bracket is innermost. ([)] keeps a counter perfectly balanced at every step while being obviously wrong. The stack preserves nesting order, which is exactly the missing information.

This is the same reason stacks underpin expression parsing and recursive-descent compilers: nested structure is inherently last-in-first-out.

Real-world example

A code editor highlighting the matching bracket under the cursor needs positions, not just a boolean:

Python
def match_positions(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack, matches = [], {}
    for i, ch in enumerate(s):
        if ch in '([{':
            stack.append((ch, i))
        elif ch in pairs:
            if not stack or stack[-1][0] != pairs[ch]:
                return None, i          # first offending position
            _, j = stack.pop()
            matches[i] = j              # link the pair both ways
            matches[j] = i
    return (matches, None) if not stack else (None, stack[-1][1])

Pushing the index alongside the character is the only change needed, and it turns validation into the editor's bracket-matching feature.

Common mistakes

  • - Omitting the final empty-stack check, so `(((` is wrongly reported as balanced.
  • - Popping without first checking the stack is non-empty, which throws on input like `)`.
  • - Using a counter instead of a stack, which cannot detect interleaved types such as `([)]`.
  • - Failing to ignore non-bracket characters, so real source code or text is rejected.
  • - Comparing the popped opener against the closer directly instead of mapping through the pairs table.

Follow-up questions

  • Why is a counter insufficient for multiple bracket types?
  • How would you find the longest valid parentheses substring?
  • What is the space complexity, and can it be reduced?
  • How does this generalise to XML or HTML tag matching?

More Stacks interview questions

View all →