Parentheses Matching Problem: Stack’s “Super Simple” Application¶
In data structures, a stack is a fundamental yet widely used structure with the Last-In-First-Out (LIFO) property—like stacking books in a bucket, where the most recently added book is the first to be removed. This feature makes stacks invaluable in many problems, with one of the most classic applications being the parentheses matching problem.
I. What is the Parentheses Matching Problem?¶
The core of the parentheses matching problem is to determine if a string composed of (), [], and {} is valid. A valid string must satisfy:
1. All left parentheses have corresponding right parentheses, and they are in the correct order (no crossing).
- Example: "(()())" is valid; "([)]" is invalid (crossing).
II. Why Use a Stack to Solve It?¶
A stack’s LIFO property perfectly aligns with the logic of parentheses matching:
- When encountering a left parenthesis, we “remember” it to match with a future right parenthesis.
- When encountering a right parenthesis, we must find the most recent unmatched left parenthesis (i.e., the top of the stack) to ensure correct order.
III. Steps to Solve Parentheses Matching with a Stack¶
Step 1: Initialize a stack (simulated with a list in Python, where append pushes and pop pops).
Step 2: Traverse each character in the string and handle two cases:
- If it’s a left parenthesis ((, [, {): Push it onto the stack (mark as “unmatched”).
- If it’s a right parenthesis (), ], }):
- If the stack is empty, there’s no matching left parenthesis → return “invalid”.
- If the stack is not empty, pop the top element and check if it matches the right parenthesis. For example:
- ) must match (; ] must match [; } must match {.
- If matched, pop the top (mark as “matched”); if not, return “invalid”.
Step 3: After traversal, if the stack is empty, all left parentheses are matched → return “valid”; otherwise, unmatched left parentheses remain → return “invalid”.
IV. Example to Make It Crystal Clear!¶
Example 1: Valid Parentheses – “(()())”
- Initialize stack: []
- Traverse: ( → push → stack: ['(']
- Traverse: ( → push → stack: ['(', '(']
- Traverse: ) → top is (, match → pop → stack: ['(']
- Traverse: ( → push → stack: ['(', '(']
- Traverse: ) → top is (, match → pop → stack: ['(']
- Traverse: ) → top is (, match → pop → stack: []
- After traversal, stack is empty → valid.
Example 2: Invalid Parentheses – “([)]”
- Initialize stack: []
- Traverse: ( → push → stack: ['(']
- Traverse: [ → push → stack: ['(', '[']
- Traverse: ) → top is [ (should match (), mismatch → invalid.
V. Key Details to Watch For!¶
- Distinguish Parentheses Types: Right parentheses must match their corresponding left parentheses (e.g.,
(only matches)). Use a dictionary for mapping:{')':'(', ']':'[', '}':'{'}. - Right Parentheses First Check: If a right parenthesis is encountered when the stack is empty, return “invalid” (no matching left parenthesis).
- Final Stack Check: After traversal, an empty stack means all left parentheses are matched; otherwise, there are unmatched left parentheses → invalid.
VI. Summary¶
A stack’s LIFO property naturally solves “most recent match” problems, and parentheses matching is a prime example. The core logic is: push left parentheses, check top of stack for right parentheses, and verify the stack is empty at the end. With these steps, you can easily determine if any parentheses string is valid!
Practice Problems¶
Try solving these with a stack:
1. "()[]{}" → valid
2. "([)]" → invalid
3. "(())" → valid
4. "(()" → invalid
(Answers: 1. Valid, 2. Invalid, 3. Valid, 4. Invalid)
Through these examples, you’ll see how simple stack applications can be. Mastering this core idea will simplify tackling more complex data structure problems later!