AlgoVerse

Matching brackets

Check with a stack that parentheses, square brackets and braces open and close properly: each closing one must match the last one opened.

Counting openings and closings is not enough (([)] has equal counts but is wrong). Each closing bracket must match the last bracket opened and not yet closed; "last opened, first closed" is exactly how a stack behaves.

Read the full explanation ↓
Input:
s="{a*[b+(c-d)]…"PDF export

{a*[b+(c-d)]}; three nested kinds, all matching.

  1. def balanced(s):
  2. pairs = {")": "(", "]": "[", "}": "{"}
  3. stack = []
  4. for i in range(len(s)):
  5. ch = s[i]
  6. if ch in "([{":
  7. stack.append(ch)
  8. elif ch in pairs:
  9. if not stack:
  10. return False
  11. top = stack.pop()
  12. if top != pairs[ch]:
  13. return False
  14. pair = top + ch
  15. if stack:
  16. return False
  17. return True

Invariant: The stack is exactly the brackets opened and not yet closed, in the order they were opened.

Start

0123456789101112
{a*[b+(c-d)]}
stack—

Local variables

s'{a*[b+(c-d)]}'

Orange = changed in this step

Call stack

  1. balanced()line 1
Step 1 of 70
Black = open, closed · Orange = key stepopen: 0/3 · closed: 0/3 · balanced: 0/1
    Explanation

    The idea

    Counting openings and closings is not enough (([)] has equal counts but is wrong). Each closing bracket must match the last bracket opened and not yet closed; "last opened, first closed" is exactly how a stack behaves.

    The algorithm

    • Push an opening bracket.
    • A closing bracket: the stack must not be empty and its top must be the same kind; pop it.
    • At the end the stack must be empty.

    Uses

    Compilers, text editors (finding the matching bracket) and checking HTML/XML.

    What to watch in the trace

    • The i pointer on the string and the stack card, which shows the open brackets.