What a stack is for#
A stack does two things in constant time: put something on the top, and take the top thing off. That sounds too simple to be useful until you notice how many problems are about nesting.
When you read ([{}]) left to right, the ] has to match the most recently opened bracket that is still unclosed. Not the first one, not any one: the most recent. That is precisely what a stack gives you.
The algorithm#
- Read the string one character at a time.
- An opening bracket goes on the stack.
- A closing bracket must match the top of the stack. Pop and compare. If the stack is empty, or the top is the wrong kind, the string is invalid.
- At the end, the stack must be empty. Anything left is a bracket that was opened and never closed.
Three failure cases, and all three are easy to get wrong by forgetting one. (] is a mismatch, ) alone is a close with nothing open, and ( alone is an open with nothing closing it.
Why not counting?#
With a single kind of bracket you can get away with a counter: add one for open, subtract one for close, never go below zero, end at zero. With several kinds that breaks, because a counter cannot tell you which bracket is waiting. ([)] keeps the counts balanced and is still wrong.
The stack is a counter that remembers what it counted.
The cost#
- Time:
O(n). Each character is pushed at most once and popped at most once. - Memory:
O(n)in the worst case, which is a string of all opening brackets.
Where this shows up#
Undo history, expression evaluation, converting infix to postfix, the call stack your own program runs on, matching HTML tags, and the whole family of "next greater element" problems, where the stack holds elements still waiting for their answer.
Common mistakes#
- Popping without checking that the stack is not empty first.
- Forgetting the final emptiness check.
- Comparing characters instead of matching pairs, so
(]slips through.