Stacks in practice

Implement bracket matching and reverse Polish notation evaluation using a Python list as a stack.

Two problems that have clean stack solutions. Read through the code, then modify and re-run to build intuition.

Bracket matching and RPN evaluation

is_balanced checks that every opening bracket has a matching closer in the right order. evaluate_rpn evaluates a postfix expression. Both follow the same pattern: scan the input left to right, push to or pop from a stack at each step.

Python — editable, runs in your browser

MATCH = {')': '(', ']': '[', '}': '{'}
OPENERS = set(MATCH.values())

def is_balanced(s):
  """Return True if all brackets in s are correctly matched and nested."""
  stack = []
  for ch in s:
      if ch in OPENERS:
          stack.append(ch)
      elif ch in MATCH:
          if not stack or stack[-1] != MATCH[ch]:
              return False
          stack.pop()
  return len(stack) == 0

def evaluate_rpn(tokens):
  """Evaluate a Reverse Polish Notation expression given as a list of strings."""
  stack = []
  ops = {
      '+': lambda a, b: a + b,
      '-': lambda a, b: a - b,
      '*': lambda a, b: a * b,
      '/': lambda a, b: int(a / b),
  }
  for token in tokens:
      if token in ops:
          b = stack.pop()
          a = stack.pop()
          stack.append(ops[token](a, b))
      else:
          stack.append(int(token))
  return stack[0]

# --- is_balanced ---
tests_balanced = [
  ("{[()]}", True),
  ("{[(])}", False),
  ("((()))", True),
  ("([)]",   False),
  ("",       True),
]
for s, expected in tests_balanced:
  result = is_balanced(s)
  status = "OK" if result == expected else "FAIL"
  print(f"{status}  is_balanced({s!r:12}) = {result}")

print()

# --- evaluate_rpn ---
# 3 4 + 2 * = (3+4)*2 = 14
expr1 = ['3', '4', '+', '2', '*']
print(f"['3','4','+','2','*']  ==>  {evaluate_rpn(expr1)}")

# 5 1 2 + 4 * + 3 - = 5 + (1+2)*4 - 3 = 14
expr2 = ['5', '1', '2', '+', '4', '*', '+', '3', '-']
print(f"5 + (1+2)*4 - 3  ==>  {evaluate_rpn(expr2)}")

Tracing is_balanced on `{[()]}`

Walk through {[()]} character by character:

Step	Character	Action	Stack
1	`{`	push opener	`[{]`
2	`[`	push opener	`[{, []`
3	`(`	push opener	`[{, [, (]`
4	`)`	pop `(`, matches	`[{, []`
5	`]`	pop `[`, matches	`[{]`
6	`}`	pop `{`, matches	`[]`

Stack is empty at the end — balanced.

Now try {[(]): at step 4 you hit ], pop (, but ( does not match ] — return False immediately.

Tracing evaluate_rpn on `3 4 + 2 *`

Step	Token	Action	Stack
1	`3`	push number	`[3]`
2	`4`	push number	`[3,4]`
3	`+`	pop 4 and 3, push 7	`[7]`
4	`2`	push number	`[7,2]`
5	`*`	pop 2 and 7, push 14	`[14]`

Result: 14. The order of pops matters: the second pop is the left operand.

RPN eliminates the need for parentheses and operator precedence rules entirely. Calculators from the 1970s used RPN because it was simpler to implement in hardware. Postscript (the language behind PDFs) is RPN-based.

Where to go next

Next: queues — the FIFO counterpart to the stack, and why collections.deque matters for efficient queue operations.

Finished reading? Mark it complete to track your progress.

Bracket matching and RPN evaluation

Tracing is_balanced on {[()]}

Tracing evaluate_rpn on 3 4 + 2 *

Where to go next

On this page

Tracing is_balanced on `{[()]}`

Tracing evaluate_rpn on `3 4 + 2 *`