Valid parentheses
Scenario
Imagine typing a math formula with multiple nested brackets. You need to ensure every opened bracket is properly closed.
How can a program verify this without getting confused by the nesting?
Why it exists
Problem: Parsing nested scopes (like brackets, HTML tags, or code blocks) requires verifying they are perfectly balanced. A naive counter approach fails because `([)]` yields equal counts but violates hierarchical nesting.
Naive approach: Counting the number of open and closed brackets. This fails for '([)]' because it ignores the correct nesting order.
Better idea: Use a stack as an active memory of unresolved scopes. Push opening brackets. When a closing bracket arrives, verify it matches the most recently opened scope by popping the stack.
Mental model
Unresolved open brackets pile up. A closing bracket must perfectly match the one on the top of the pile.
The parser scans left to right. Opening brackets are pushed. Closing brackets never enter the stack; instead, they act as triggers to pop the top of the stack and check for a match. The invariant is that the stack strictly contains unmatched open brackets in chronological order. A valid string leaves the stack empty.
Repeated decision: Is this a closing bracket that matches the most recent unmatched opener on top of the stack?
Explanation
Validating perfectly nested scopes is a fundamental problem in theoretical computer science, separating finite state machines (which can only parse regular expressions) from pushdown automata (which have stack memory and can parse context-free grammars).
The stack is the perfect tool because it elegantly handles nesting. By storing only the unmatched opening characters, the stack naturally exposes the *most recently opened* scope at its top boundary. Thus, when a closing bracket arrives, determining if it is legally positioned is an instant O(1) peek.
In compiler theory, checking nested brackets requires a memory of what was opened. A left-to-right scan can't count nesting depth; a stack gives it the memory to keep track of this state. This is exactly how a pushdown automaton (a machine with a stack) parses context-free grammars.
For advanced problems like finding the 'Longest Valid Parentheses', we use an index-stack with a sentinel value. We seed the stack with -1 to represent the boundary before the string starts. We push indices of unmatched `(`, and on a match, we compute the length as `i - stack.top()`. This technique seamlessly handles contiguous valid sequences.
Key points
- Invariant: Every closing bracket must match the most recently opened unmatched bracket at the top of the stack.
- Complexity: O(n) time to scan the string, O(n) space for the stack.
- Gotcha: Don't forget to check if the stack is empty at the end; leftover open brackets mean it's invalid.
Pattern: Stack-based Parsing
Recognition cues:
- Nested structures
- Matching pairs
- Context-free grammar parsing
Failure signals
- Just counting the number of brackets (fails on ordering)
Engineering examples
Compilers and Interpreters
Generating Abstract Syntax Trees (ASTs)
Pushdown Automata (PDA) couple a finite state machine with a stack to parse context-free grammars like nested brackets.
JSON / HTML Validation
Validating structural token nesting
The stack verifies that deeply nested objects or tags close in the exact reverse order they opened.
Common mistakes
- Forgetting to check if stack is empty before popping: If a closing bracket arrives when the stack is empty, it means a scope is being closed before it was ever opened. This should immediately return false.
- Forgetting the final emptiness check: After processing all characters, the stack must be empty. If elements remain, it means there are unclosed scopes.
Recall questions
- Why doesn't a simple counter work for validating parentheses?
- What does the stack represent at any given point in the algorithm?
- What are the two failure conditions during parsing?
Questions & answers
Determine if a string of brackets is valid.
Scan left to right. Push openers. On closer, pop stack and check if they form a valid pair. Finally, return `stack.isEmpty()`.
Approach: Standard stack matching invariant.
Find the length of the longest valid parentheses substring.
Use a stack to store indices instead of characters, initializing with -1 to serve as a base. When a valid pair is formed, compute length using the current index minus the new top of stack.
Approach: Store indices in the stack to calculate distances between matching boundaries.
Continue learning
Previous: Stack fundamentals
Related: Stack fundamentals