Matching & Nesting

Nesting is stack-shaped, provably

([{}]) is well-nested; ([)] is not. What distinguishes them? In well-nested text, every closer closes the most recently opened thing. That phrase — most recently — is LIFO verbatim, which is why the stack is not merely a way to check nesting but the canonical one:

Scan left to right. Opener ⇒ push it (an obligation). Closer ⇒ it must match the stack's top obligation — pop on match, fail on mismatch. Well-nested ⇔ the scan never fails and ends with an empty stack.

The three failure modes fall out mechanically, and enumerating them is what makes implementations correct rather than lucky:

1. Wrong closer — top is ( but you read ] → mismatch (([)]).
2. Closer with nothing open — pop on empty (())... the last )).
3. Leftover obligations — scan ends, stack non-empty ((().

Trace failure mode 1 on ([)]: read (, push — stack ['(']. Read [, push — stack ['(', '[']. Read ) — pop the top, [, and compare: [ is not the partner of ) (that's ]) — mismatch, halt, reject. The counts of (/) and [/] are each balanced in this string; only the order is wrong, which is exactly the property a stack — and only a stack — checks. (For a single bracket type, order and count collapse into the same fact: a running counter that increments on open, decrements on close, and must never go negative — the "closer with nothing open" check — suffices, because there's only one kind of obligation to track. Multiple types need the stack because "was the most recent obligation THIS type" is an ordering question a bare count can't answer.)

The Valid Parentheses problem asks you to turn exactly this into code; its quiz will ask which failure mode each broken input triggers.

The same shape in the wild

The opener/obligation framing generalizes far past brackets — push an obligation when a context opens, pop when it closes, and the stack top is always "the context I'm inside right now":

• Parsers and compilers — every { block, XML/HTML tag, or indent level is an obligation; your editor's "highlight matching bracket" is running this scan continuously.
• Directory traversal — cd into a folder pushes, cd .. pops; paths like a/b/../c simplify with a stack (Simplify Path problem).
• Backspace processing — a backspace "closes" the previous character: ab#c → stack ends ["a","c"].
• Nested function evaluation — the deepest call finishes first; expression evaluation (next lessons) rides entirely on this.

The recognition cue: the input has paired open/close events, or edits that cancel the most recent item. Either phrase should make your hand reach for a stack before your brain finishes the sentence.

Worked micro-example: string with cancellations

Remove adjacent duplicate pairs repeatedly: "abbaca" → remove bb → "aaca" → remove aa → "ca". The naive re-scan-after-each-removal is O(n²): each removal rewrites the string (splice out two characters, copy the rest) at O(n), and up to O(n) removals can cascade — O(n) removals × O(n) per rewrite = O(n²). The stack sees it in one pass:

def remove_adjacent_dupes(s: str) -> str:
    stack: list[str] = []
    for ch in s:
        if stack and stack[-1] == ch:
            stack.pop()              # ch cancels the most recent survivor
        else:
            stack.append(ch)
    return "".join(stack)            # builder pattern, Module 5

Why one pass suffices when removals cascade (abba: removing bb exposes aa): the stack top after a pop is exactly the character that became adjacent — the cascade is automatic, no re-scan. The stack's survivors are always "the processed prefix after all cancellations," an invariant that makes the O(n) bound and the correctness one argument.

Trace it character by character on "abbaca" to see the cascade happen without ever looking backward:

Popping the second b exposes a as the new top — precisely the character that must compare against the incoming a next. Result: "ca". Think of it like a stack of cafeteria trays: pulling the top tray off doesn't just remove one tray, it instantly puts whatever was underneath into "top" position — no separate step required to notice it.

That push-once/pop-once accounting is worth tattooing somewhere: it's the exact argument that will make the monotonic stack (next lesson) O(n) despite its nested-looking while loop.