Stacks and Queues

Balanced Parentheses

Walk a string of bracket characters. Push every opening bracket. On a closing bracket, pop and verify the popped opener matches. Mismatch or empty-stack pop means unbalanced; an empty stack at the end means balanced.

Algorithm

Canonical balanced input is "({[]})"; the stack grows to three elements then empties as the closers arrive in matching order.

push opener pop matching closer Each closing bracket must match the most recent unmatched opener.

Basic Implementation

basic.py
Replay: real traced execution (multi-file project)
text = "({[]})"
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
balanced = True
for ch in text:
    if ch in "({[":
        stack.append(ch)
    else:
        if not stack or stack[-1] != pairs[ch]:
            balanced = False
            break
        stack.pop()
if stack:
    balanced = False
print(balanced)

  1. text ← ({[]})

    1text = "({[]})"2pairs = {')': '(', ']': '[', '}': '{'}
    values this step({[]})text

  2. stack ← []

    2pairs = {')': '(', ']': '[', '}': '{'}3stack = []4balanced = True
    values this step[]stack

  3. balanced ← True

    3stack = []4balanced = True5for ch in text:
    values this stepTruebalanced

  4. stack ← [(]

    4balanced = True5for ch in text:6    if ch in "({[":
    values this step[(]stack(ch

  5. stack ← [(, {]

    4balanced = True5for ch in text:6    if ch in "({[":
    values this step[(, {]stack{ch

  6. stack ← [(, {, []

    4balanced = True5for ch in text:6    if ch in "({[":
    values this step[(, {, []stack[ch

  7. stack ← [(, {]

    4balanced = True5for ch in text:6    if ch in "({[":
    values this step[(, {]stack]ch

  8. stack ← [(]

    4balanced = True5for ch in text:6    if ch in "({[":
    values this step[(]stack}ch

  9. stack ← []

    4balanced = True5for ch in text:6    if ch in "({[":
    values this step[]stack)ch

  10. balanced ← True, stdout ← True

    12        stack.pop()13if stack:14    balanced = False
    values this stepTruebalancedTruestdout[]stack

Complexity

  • Time: O(n)
  • Space: O(n) worst case

Implementation notes

  • Python: a list is a fine stack — append / pop work in O(1).
  • The replay shows the current character, the operation (push vs. pop), and the post-step stack contents using a literal [(, {, [] notation rather than any object identity.