Stack Simulation, Parsing & Expression Evaluation

What this subtopic covers

Not every stack problem is about monotonicity. A huge, separate class of interview problems just needs the plain Last-In-First-Out behavior: something is "open" until it's explicitly "closed," and the most recently opened thing must be the first one closed. This subtopic groups three closely related uses of a vanilla stack:

1. Balanced/nested structure validation — brackets, tags, or any "opens must close in reverse order" structure.
2. Stack-based simulation — replaying a sequence of operations where each new operation can only interact with the most recent unresolved item (collisions, undo, running aggregates).
3. Expression parsing & evaluation — postfix (RPN) evaluation, and infix evaluation with operator precedence and parentheses (calculators).

All three share the same underlying justification for using a stack: the next piece of information you need is always the most recently seen unresolved one — which is precisely what a stack gives you O(1) access to.

Recognizing it in a problem statement

• Brackets, parentheses, tags, or any explicit "open X / close X" vocabulary → balanced structure matching.
• "Replay these operations," "each operation depends on previous results," "undo the last score/move" → stack simulation.
• "Evaluate this expression," "calculator," "Reverse Polish Notation," k[encoded_string]-style nested repetition → expression parsing.
• Anything recursively nested — an expression inside parentheses, a repeated block inside brackets — is a strong signal, because a stack is the standard iterative substitute for the recursive call stack you'd otherwise write with DFS (see Trees and Backtracking, where you'll use actual recursion for similar nesting).

Technique 1: balanced structure matching

Push every "opening" token; on a "closing" token, check that it matches whatever is currently on top of the stack, then pop. The structure is valid if and only if the stack is empty at the end (every open was matched, and nothing closes something that wasn't open).

The key invariant: the stack, read top to bottom, always represents the "currently open, still-unmatched" context, most recent first — which is exactly why the top must match the next closer you see.

Technique 2: stack-based simulation

Here the stack literally is your evolving state — each incoming token/event either pushes new state or reaches back to mutate/remove the most recent state. A generic version of this shape (deliberately distinct from any problem in the list below) is removing adjacent duplicate characters:

The pattern generalizes directly to any process where a new event can "collide with," "merge with," or "invalidate" whatever is currently on top — you'll apply the exact same push/inspect-top/conditionally-pop shape to score-keeping and collision problems below, just with a domain-specific rule for what counts as a collision and what the outcome of that collision is.

Technique 3: expression evaluation

Postfix (Reverse Polish Notation) is the easy case: operators always apply to the two most recently seen operands, so a single stack suffices — push numbers, and on an operator, pop two operands, apply it, push the result back.

Infix expressions (the normal "2 + 3 * 4" notation you write by hand) are harder because of operator precedence (*// bind tighter than +/-) and parentheses (which override precedence locally). Two standard approaches:

• Direct one-pass evaluation with a stack of pending values (what "Basic Calculator"-style problems want): track a running number and the last-seen operator; when you hit a lower- or equal-precedence operator (or the end of input), resolve the pending multiplication/division immediately by popping and combining, but leave additions/subtractions on the stack to be summed at the end. Parentheses are handled by pushing the current accumulated result and sign onto the stack before recursing into the sub-expression, then popping and combining when the matching ) is found.
• Convert infix → postfix first, then evaluate the postfix — the classic two-stage approach, formalized by Dijkstra's shunting-yard algorithm: maintain an output queue and an operator stack; push operators onto the stack but first pop (into the output) any stacked operator with greater-or-equal precedence; ( pushes onto the operator stack, ) pops operators into the output until the matching ( is found.

Both approaches are O(n) — every character is looked at a constant number of times — but the one-pass approach uses less auxiliary structure and is what most interviewers expect for "implement a calculator" questions, while shunting-yard is the better mental model if the expression includes many operators of differing precedence or needs to be evaluated multiple times.

A comparison of the three techniques

Technique	What the stack holds	Resolves on	Typical problems
Balanced matching	Currently-open bracket/tag types	Seeing a closing token	Valid Parentheses
Simulation / collision	Evolving sequence of "surviving" events	Each new incoming event	Baseball Game, Asteroid Collision
Postfix (RPN) evaluation	Operands waiting to be combined	Seeing an operator token	Evaluate Reverse Polish Notation
Infix evaluation / calculator	Pending sub-results, signs, and operators (bracketed by parens)	Seeing a lower-precedence operator or )	Basic Calculator, Basic Calculator II
Nested-repetition decoding	Partially-built strings and pending repeat counts, one per bracket depth	Seeing a closing bracket	Decode String

Complexity analysis

All of these run in O(n) time and O(n) space in the worst case (a fully-nested input pushes every character before popping any of them — think ((((()))))). Unlike the monotonic stack, there's no amortized argument needed here: each character is pushed at most once and popped at most once, directly, with no hidden nested work — the linear bound is immediate from the single pass.

Common pitfalls and interview gotchas

• Popping from an empty stack. A closing bracket with nothing open, or a C/undo operation with no prior score, is invalid input in some problems and a bug in your traversal in others — always guard with an emptiness check before popping.
• Multi-digit numbers and whitespace. Real calculator inputs have numbers longer than one character and may contain spaces (" 2-1 + 2 "). Build the number by accumulating digits (num = num * 10 + int(ch)) rather than assuming one digit per token, and explicitly skip whitespace.
• Unary minus / sign handling. "-(2+3)" or "1-(-2)" trips up calculator implementations that only expect binary operators — decide up front how you track sign state (often via a sign variable reset at each ().
• Integer division truncation toward zero, not floor division — -7 // 2 is -4 in Python but the expected calculator answer is -3. This is a classic silent-wrong-answer bug for Python solvers specifically.
• Order of operands when popping two values. For non-commutative operators (-, /), the first popped value is the right operand and the second popped is the left operand — b, a = stack.pop(), stack.pop(); stack.append(a - b), not the reverse.
• Mixing up "resolve inside the loop" vs. "resolve after the loop ends." Many calculator solutions need one extra resolution step after the final character to flush the last pending number/operator — a frequent off-by-one source.
• Recursion depth vs. explicit stack. Nested-structure problems (like decoding k[...] patterns) can be solved either recursively or with an explicit stack; recursion mirrors the call stack you'd get from a DFS (see Trees) and is often more readable, but an explicit stack avoids Python's recursion limit on deeply nested or adversarial inputs — know both and be ready to justify your choice.

How this connects to the rest of the roadmap

The "resolve using only the most recent unresolved item" idea you're practicing here is the same mental model behind DFS using an explicit stack instead of recursion (Trees, Graphs), and nested-repetition parsing is structurally identical to recursive tree construction from a serialized format. If you're comfortable reasoning about stack depth and state here, that transfers almost directly.