Lesson 9.2 · Stack and Monotonic Stack
Matching and Nesting
Push every opener; when a closer arrives it must match the opener on top. Anything left over, or a mismatch, means invalid.
12 min
Think of it like this
Russian dolls: every doll you open must be closed before the doll that contains it. If you try to close the big doll while a small one is still open, something is wrong.
1.Why the stack fits
In "( [ ] )", the ] must close the most recent unclosed opener, which is [. "Most recent unclosed" is exactly the stack's top. So push openers, and for each closer, pop and check that it matches.
At the end the stack must be empty; otherwise some opener was never closed.
s = "([]{})"stack(stack)
Step 1/5'(' is an opener: push.
2.Stacks of state, not just characters
In harder problems you push richer state: a count and the string built so far (Decode String), or a running result and a sign (Basic Calculator). When a nested part closes, pop the saved state and combine it with what was built inside.
Remember
- Push openers, pop and compare on closers.
- Empty stack at the end = everything closed.
- Push saved state to handle nesting in parsers.
Common mistakes
- Forgetting the final emptiness check ("((" would pass).
- Popping on a closer without checking the stack is non-empty (")" crashes).