Stack Operation Examples: Balanced Parentheses
What You'll Learn
You'll learn how to implement a classic algorithm that checks if parentheses in a string are properly balanced using Deque as a stack.
The Problem
Balanced parentheses means every opening bracket has a matching closing bracket in the correct order. For example:
"(())"is balanced ✓"(()"is not balanced ✗ (missing closing bracket)"())"is not balanced ✗ (extra closing bracket)")()"is not balanced ✗ (wrong order)
The Stack Solution
A stack is perfect for this problem because of its Last-In-First-Out nature:
- When you see an opening bracket
(→ push it onto the stack - When you see a closing bracket
)→ pop from the stack and check if it matches - At the end → the stack should be empty (all brackets were matched)
Think of it like checking nested boxes: each time you open a box (push), you must close that exact box (pop) before moving to the outer one.
Implementation Using ArrayDeque
import java.util.ArrayDeque;
import java.util.Deque;
public class BalancedParentheses {
public static boolean isBalanced(String str) {
Deque<Character> stack = new ArrayDeque<>();
for (char ch : str.toCharArray()) {
if (ch == '(') {
stack.push(ch);
} else if (ch == ')') {
if (stack.isEmpty()) {
return false; // No matching opening bracket
}
stack.pop();
}
}
return stack.isEmpty(); // All brackets matched
}
public static void main(String[] args) {
System.out.println(isBalanced("(())")); // true
System.out.println(isBalanced("(()")); // false
System.out.println(isBalanced("())")); // false
}
}
We use push for adding opening brackets, pop for removing them when we find a match, and isEmpty to verify all brackets paired up correctly.
Key Takeaway: Stacks naturally solve nested structure problems like balanced parentheses—push opening symbols, pop and match closing symbols, and verify the stack is empty at the end.