Balanced Parentheses —
Push open. Pop on close. Match or fail.
Checking if parentheses, brackets, and braces are balanced is the classic stack problem. Every opening bracket gets pushed. Every closing bracket pops and checks for a match. If the stack is empty at the end — balanced. Watch each character drive the stack on LearnBug and the algorithm becomes second nature.
What is the problem?
Given a string of brackets — (, ), [, ], {, } — determine if every opening bracket has a corresponding closing bracket in the correct order. "([]{})" is valid. "([)]" is not — the brackets overlap incorrectly. The stack perfectly models this: LIFO ensures the most recently opened bracket is always closed first.
Why the stack is perfect here
Brackets must close in reverse order of how they opened — that's exactly what LIFO gives you. The top of the stack is always the most recently opened bracket, which is the one that must close next. On LearnBug, you watch brackets push and pop one character at a time, and the mismatch is immediately visible when the wrong bracket tries to close.
Tracing "([]{})" — should return True
'(' — opening bracket → push
Push ( onto stack. Stack: ['(']
'[' — opening bracket → push
Push [. Stack grows. Stack: ['(', '[']
']' — closing bracket → pop and check
Pop [ from top. Does [ match ]? Yes ✓. Stack: ['(']
'{}' — push then pop, match ✓
Push {. Then } pops it and matches. Stack back to ['('].
')' — pop and check → stack empty → return True
Pop (. Matches ) ✓. Stack is now empty. All brackets matched — return True.
Tracing "([)]" — should return False
Push '(' and '['
Both opening brackets pushed. Stack: ['(', '[']
')' — pop '[' but expected '(' → MISMATCH!
Top of stack is [. Closing bracket is ). They don't match — return False immediately.
Clean implementation with a hash map
Time & Space Complexity
Frequently asked questions
Why do we check if the stack is empty before popping?
If a closing bracket appears before any opening bracket has been pushed, the stack is empty and stack[-1] would throw an IndexError. Checking not stack first handles this — an empty stack on a closing bracket means it's unmatched, so return False immediately.
Why return len(stack) == 0 at the end instead of just True?
A string like "(((" would pass all the inner checks (no closing brackets ever cause a mismatch) but leave three unmatched opening brackets on the stack. Checking len(stack) == 0 catches this case — unmatched opening brackets are also invalid.
Can I solve this without a hash map?
Yes — use three if/elif conditions comparing the stack top directly to the expected opener. The hash map approach is cleaner and more extensible (adding new bracket types is a one-line change). Both are O(n) time and space.
How does this extend to checking code syntax?
Compilers and IDEs use exactly this algorithm to validate bracket matching in code. They also track line numbers inside frames to give you the "unmatched bracket at line X" error message. The core algorithm is identical — just richer bookkeeping around each push.
What is the LeetCode problem for this?
LeetCode 20 — Valid Parentheses. One of the most common beginner stack problems. Extensions include: LC 1047 (Remove All Adjacent Duplicates — same push/pop pattern), LC 394 (Decode String — nested brackets with counts), and LC 726 (Number of Atoms — nested chemical formulas).
Watch brackets push and pop on your own input
Paste any bracket string into LearnBug and see every push, pop, and mismatch happen step by step.