Stack Example: Matching Brackets in an Expression

Each closing bracket must match the most recent opening bracket still waiting.

A stack fits any problem in which the next thing to finish is the most recent thing started, and checking that brackets are balanced is the most familiar such problem. This card covers that check on a short expression, with the stack traced one character at a time.

An expression such as ( [ ] { } ) is balanced when every closing bracket closes the most recent opening bracket still open, and none is left open at the end. The check reads the characters from left to right. An opening bracket is pushed. A closing bracket must match the bracket on top of the stack, which is then popped; if the stack is empty, or its top is a different kind, the expression is unbalanced. At the end the stack must be empty.

In the trace, the cells are the stack's slots from the bottom, _ is an empty slot, and top marks the top item. Each label gives i, the index of the character read.

Checking ( [ ] { } ) with a stack

Input( [ ] { } )

Start: the stack is empty
1. _
2. _
3. _
Nothing is open yet, so nothing is waiting to be closed.
i = 0, read (: push it
1. (top
2. _
3. _
An opening bracket waits for its partner, so it goes on the stack.
i = 1, read [: push it
1. (
2. [top
3. _
The [ is now the most recent bracket still open, and it sits on top.
i = 2, read ]: pop its [
1. (top
2. _
3. _
] must match the top, which is [, so the [ comes off and ( is on top again.
i = 3, read {: push it
1. (
2. {top
3. _
The { is pushed above the (, in the slot the [ used.
i = 4, read }: pop its {
1. (top
2. _
3. _
} matches the top, {, so the { comes off.
i = 5, read ): pop its (
1. _
2. _
3. _
) matches the (, the last bracket open, and the stack ends empty: balanced.

ResultBalanced: every closing bracket matched the top of the stack, and the stack ended empty.

The same run rejected three other inputs. In ( [ ) ] the ) at index 2 meets a [ on top, so the pairs cross. In ( ( ) one ( is still open at the end, and in ( ) ) the second ) finds the stack empty. A counter of open brackets would accept ( [ ) ], because it records how many are open but not which kind was opened last; the stack records both.

The cue is the phrase "most recent unfinished". Closing tags in HTML, functions that call other functions and return in reverse order, and an editor's undo all share it, and each is a stack.

← → move through sections and cards