Read tokens left to right. Each token triggers push, pop, reduce, or top-frame mutation; the stack is the minimal set of contexts from the processed prefix that can affect the future.
Recognition signals
The structure is nested with last-opened, first-closed behavior.
Operations include undo, back, return, or collapse.
Recursive calls can be simulated with explicit frames.
A new token needs only the most recent unfinished context.
False friends
Signal
Why it is different
First-in-first-out event handling
When the earliest arrival must be processed first, use a queue.
Delimiter validity only
The narrower balanced-delimiter-stack template is easier to prove.
Core invariant
After each input prefix, frames from bottom to top are exactly the unfinished contexts in opening order, and the top is the only context directly affected next.
State, transition, and processing order
Item
Definition
State
Token cursor and a frame stack, with each frame storing only information needed to resume its parent context.
Transition
An opening event pushes a frame, a closing event pops and reduces into its parent, and an ordinary token updates the top frame.
Frontier / order
A chain from oldest to newest unfinished context, exposing only the top to the next transition.
Python skeleton
def normalize_path(parts):
stack = []
for part in parts:
if part in ('', '.'):
continue
if part == '..':
if stack:
stack.pop()
else:
stack.append(part)
return '/' + '/'.join(stack)
Correctness sketch
An ordinary segment appends the current deepest context while preserving order.
A parent operation removes only the most recent effective segment, exactly matching LIFO semantics.
Induction over all tokens leaves precisely the path segments that were never canceled.
Complexity
Time
Space
Parameters
O(n)
O(d)
n is token/input length and d maximum unfinished depth; output joining also costs output length.
Edge cases
Empty input yields the base state.
Popping at root must be ignored or rejected according to the protocol.
Many consecutive opens or closes reach maximum depth.
A nonempty stack at end may be valid residual output or malformed input, depending on the grammar.
Error patterns
Pattern
Why it fails / fix
Oversized frames
Copying the entire prefix into each frame can inflate O(n) work to O(n²).
Popping an empty stack
Define closing or undo behavior when no context exists.
Confusing child and parent state
Specify frame fields and the reduction performed after pop.
Selection and exclusion rules
Use a stack when the most recently opened context must finish first.
Use the specialized balanced template for delimiter matching only.
If the next item is chosen by numeric priority, use a heap or monotonic structure instead of a generic state stack.
Related templates
Relation
Template
Boundary
Original micro-example
Part
Detail
Result
The normalized path is /home/pics/2026.
Setup
Path parts [home,docs,..,pics,.,2026].
Trace
Push home/docs, pop docs on .., ignore ., then push pics/2026.
Recall prompts
Should a frame store all history or only a future-relevant summary?
Why must the latest opened context close first?
How can recursive parameters be turned into an explicit frame?