Valid Parentheses — Stack-Based Matching
Push opening brackets onto a stack and ensure every closing bracket matches the most recent opener.
Problem Statement
Given a string of brackets, determine if the brackets are closed in the correct order.
Why This Problem Matters
- Classic stack exercise that underpins parsing, expression validation, and editor tooling questions.
- Shows how LIFO structures naturally model nested, well-formed constructs.
- Teaches defensive programming with early exits when mismatches occur.
Thought Process
Map openings to closures
Recognise parentheses, braces, and brackets should close in reverse order of opening.
Use a stack for LIFO behaviour
Push opening characters; when seeing a closing one, compare against the stack top.
Guard against underflow
If the stack is empty when a closing bracket arrives, the string is invalid.
Step-by-Step Reasoning
- Initialise an empty stack.
- For each character c in the string, push if it is an opener.
- If c is a closer, pop and verify it matches the expected opening bracket.
- Return true only if the stack is empty after processing the entire string.
Dry Run
Input "([])"
Push (, push [, pop [ with ], pop ( with ); stack ends empty.
Input "(]"
Push (, encounter ], mismatch occurs so return false.
Complexity Analysis
Time
O(n)
Space
O(n)
Why
Each character is touched once and the stack may hold every opening bracket.
Annotated Solution
import java.util.ArrayDeque;
import java.util.Deque;
public class ValidParentheses {
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.isEmpty()) {
return false;
}
char open = stack.pop();
if (open == '(' && c != ')') {
return false;
}
if (open == '{' && c != '}') {
return false;
}
if (open == '[' && c != ']') {
return false;
}
}
}
return stack.isEmpty();
}
}The stack enforces LIFO ordering so every closing bracket must correspond to the most recent opening bracket.
Common Pitfalls
- Comparing character values instead of using a mapping leads to accidental matches.
- Forgetting to check isEmpty before popping causes runtime exceptions.
- Returning true while the stack still holds openers misses unmatched openings.
Follow-Up Questions
- How would you validate HTML/XML tags where tokens are longer than one character?
- Can you check a stream of characters without storing the entire string?