Stack
A stack only lets you touch the top: push puts an item there, pop takes the newest one off. That is exactly how brackets nest. The last bracket opened is always the next one that must close, so it is always the one on top.
{[()()]}
Is every bracket closed by the right partner, in the right order? Press play or step forward to start.
1function isBalanced(s) {2 const pairs = { ')': '(', ']': '[', '}': '{' };3 const stack = [];4 for (const c of s) {5 if (!(c in pairs)) {6 stack.push(c);7 } else if (stack.pop() !== pairs[c]) {8 return false;9 }10 }11 return stack.length === 0;12}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | 1 | the first bracket is a closer |
| average | n | one push or pop per bracket |
| worst | n | the string is balanced: every bracket is read |
| space | n | all openers wait on the stack |
Where it breaks
- Counting is not enough.
([)]has two of each bracket, so counts balance. Pick it: the stack catches that)arrives while[is on top. - Leftovers at the end. Pick ((): no closer ever fails, but one opener is still waiting when the string ends. Always check the stack is empty at the end.
- A closer with nothing open. Pick ())(: the second
)finds an empty stack. In Python, popping an empty list is an error, which is why the code checksnot stackfirst.