Stacks

## What is really being asked Delimiter matching is the first application of a stack most people meet, and it is also where an over-generalisation takes root: "any balance check needs a stack." That is false. Knowing precisely when the stack earns its place is what separates an understood answer from a memorised one. ## The one-type case: a counter is enough Suppose a config linter only has to verify that a file's parentheses balance. Scan left to right, add one on an opener, subtract one on a closer. Two rules decide the file: - if the counter ever goes **negative**, a closer appeared with nothing open — reject immediately, at that position; - if the counter is **non-zero at end of input**, some opener was never closed — reject. Otherwise accept. Time `O(n)`, extra space `O(1)`. A stack would also work, but in a deeply nested file it stores up to n/2 identical entries to answer a question one integer answers. With a single type, "which opener is on top?" has only one possible answer, so the stack carries no information the counter lacks. Notice the asymmetry that already appears, though. The counter tells you *that* the file is unbalanced, not *where*. If the linter must emit "unclosed delimiter opened at line 42, column 7", it needs somewhere to keep the position of every pending opener — and that is a stack again, even with one type. The structure follows what you must *report*, not only what you must decide. ## Several types: the counter breaks Now the linter handles round, square and curly pairs plus a pair of typographic quotation marks. Consider the sequence `( [ ) ]`. Each type appears exactly once open and once closed, so every per-type counter ends at zero and no total ever goes negative. The input is nonetheless malformed: the parenthesis closes while the bracket is still open, so the two regions **overlap** instead of nesting. That is the whole point. Counting answers "how many are open". Nesting is a claim about **order**: the region opened most recently must be the region closed first. To reject `( [ ) ]` you must know, at the moment the closer arrives, that the most recently opened and still-unclosed delimiter is the square bracket. "Most recently opened, first to be closed" is last-in-first-out stated in the problem's own vocabulary — which is why the stack is not a clever trick here but a restatement of the requirement. ## The algorithm Scan the input one delimiter at a time. - **Opener** — push it, together with its position if you need to report one. - **Closer** — if the stack is empty, reject: a closer with nothing open. Otherwise pop; if the popped opener is not this closer's partner, reject with both offenders named. - **End of input** — accept if and only if the stack is empty. Anything left is unclosed, and the bottom-most entry is the outermost unclosed region. Each delimiter is pushed and popped at most once, so the scan is `O(n)` time and `O(d)` space where d is maximum nesting depth (`O(n)` worst case, small in practice). ## What a real linter adds on top Real inputs are not pure delimiter soup, and this is where interview answers thin out. - A delimiter **inside a quoted string** is text, not structure. A closing bracket in a message string must not pop anything. - **Escapes** suppress the next character's structural meaning; **comments** hide delimiters entirely. So the scanner is a small state machine — in-code, in-string, in-comment — and only the in-code state feeds the stack. - **Text encoding** matters for error messages: with multi-byte characters, the position you record should be a character or grapheme index, not a byte offset, or the caret in the reported error lands in the wrong column. - Some pairs cannot be matched by shape at all. A **symmetric** delimiter, where the same character opens and closes, carries no direction, so a stack cannot tell an opener from a closer; you toggle a flag instead, or rely on typographic pairs that genuinely differ. Another case where the stack is the wrong instrument. ## The transferable lesson A stack is the right structure when you are tracking **pending obligations that must be discharged in reverse order of arrival**. Nested delimiters, nested markup elements, nested scopes, nested calls — all the same shape. When there is only one kind of obligation and you only need a yes/no verdict, a counter is a cheaper realisation of the same idea. When the obligations differ in kind, or you must name the one still outstanding, only the stack retains that. The interview failure mode is reaching for the stack reflexively and being unable to say what it buys. The strong answer names the counter case, names the input that breaks it, and names LIFO as the reason the stack fits.