Stacks & Queues

Stack: Matching & Evaluation

Use a stack for nested structure: brackets, expressions, undo.

Easy, about 60 minutes to practise.

1Understand

The idea

A stack remembers what is still open. Push when something opens (a bracket, an operand, a directory) and pop when it closes; the top is always the most recent unfinished item. At the end, an empty stack means everything matched.

Intuition

A stack remembers what is still open. Push when something opens (a bracket, an operand, a directory segment) and pop when it closes; the top is always the most recent unfinished item.

At the end, an empty stack means everything matched. A close with an empty stack, or a final leftover open, means failure. The same discipline evaluates RPN, simplifies paths, and decodes nested strings.

Anything "most recently unmatched" is a stack cue.

What you will be able to do

  • Push/pop on the right events
  • Check the stack is empty at the end

When to use it

  • Balanced brackets
  • Evaluate an expression
  • Most recent unmatched item

2See it

Walkthrough

Valid parentheses

s = "([])", push openers, pop on closers; the top must match.

1 / 4

i
(
[
]
)
0123
i → index 0

See "(". Push it. Stack = ["("].

stack.append("(")

Live template

Line 1 active

1stack = []
2for ch in s:
3 if opens(ch): stack.append(ch)
4 elif not stack or not matches(stack.pop(), ch): return False
5return not stack

Complexity: time O(n), space O(n)

Time O(n), space O(n) for the stack in the nested worst case. Regex or counting alone cannot handle multiple bracket types with proper nesting. For path simplify / calculators, the same O(n) bound holds; the stored items change, not the pattern.

Read the walkthrough as text

Valid parentheses. s = "([]){}".

  1. Push '(', then '['.
  2. See ']': top '[' matches, pop.
  3. See ')': top '(' matches, pop.
  4. Push '{', see '}', pop. Stack empty → valid.

In code:

  • pairs = {')':'(', ']':'[', '}':'{'}
  • stack = []
  • for ch in s:
  • if ch in '([{':
  • stack.append(ch)
  • elif not stack or stack.pop() != pairs[ch]:
  • return False
  • return not stack

3Recognise it

Kinds of problems (8)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Balanced brackets

    Example. Is the bracket string valid?

    How. Push opens; on close, pop must match; stack empty at end.

  • Reverse Polish notation

    Example. Evaluate an RPN expression.

    How. Push numbers; on operator, pop right then left (order matters), push result.

  • Simplify a path or undo operations

    Example. Canonical Unix path or matching undo/redo.

    How. Stack of segments: push names, pop on "..", skip duplicates like ".".

  • Decode nested strings

    Example. 3[a2[c]] → accaccacc.

    How. Stack of (count, prefix) or (count, string); expand when you see ].

  • Basic calculator

    Example. Evaluate +, -, parentheses.

    How. Stack current number and last sign; on ")", push outer context and evaluate inner.

  • Collision or fleet simulation with a stack

    Example. Cars stack when slower ahead; process from right.

    How. Monotonic stack of indices by position/speed; pop when current catches up.

  • Stack of (value, count) pairs

    Example. Remove adjacent duplicates k times.

    How. Push (val, count); merge with top when val matches and count+k threshold met.

  • Simulate push and pop sequences

    Example. Can target stack order be built from 1..n pushes?

    How. Simulate: push next number until top equals next needed pop, then pop.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Pop from empty stack

    Why it happens. You expect a close bracket to always have a partner.

    How it fails. s = ")": stack.pop() on empty raises IndexError instead of returning false for invalid.

    Fix. Check stack before pop; on close, empty or mismatch → invalid.

  • Leftover items ignored

    Why it happens. The last closers balanced, so the string feels done.

    How it fails. "(()", stack still has "(" at the end; returning True without checking not stack.

    Fix. Valid only if every open was closed: return not stack after the scan.

  • Operand order

    Why it happens. Addition commutes, so operand order seems irrelevant.

    How it fails. RPN "3 4 -": pop a=3, b=4, push a-b = -1 but correct is b-a = 1.

    Fix. On binary op: second = pop(), first = pop(), push first op second (not the reverse).

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons