Balanced Parentheses with a Stack
javaJavabeginnerinterview-prepjava
Check that every bracket is closed in the right order by pushing openers on a Deque and matching each closer against the top.
import java.util.*;
public class BalancedParentheses {
public static void main(String[] args) {
System.out.println(isBalanced("{[()]}")); // true
System.out.println(isBalanced("a(b[c]d)e")); // true
System.out.println(isBalanced("([)]")); // false
System.out.println(isBalanced("((")); // false
System.out.println(isBalanced("())")); // false
System.out.println(isBalanced("")); // true
}
// O(n) time, O(n) space. ArrayDeque is the recommended stack: faster than the legacy Stack class.
static boolean isBalanced(String text) {
Map<Character, Character> openerFor = Map.of(')', '(', ']', '[', '}', '{');
Deque<Character> stack = new ArrayDeque<>();
for (char c : text.toCharArray()) {
if (openerFor.containsValue(c)) {
stack.push(c); // an opener: remember it
} else if (openerFor.containsKey(c)) {
char expected = openerFor.get(c);
if (stack.isEmpty() || stack.pop() != expected) return false; // a closer with no matching opener
}
}
return stack.isEmpty(); // anything left over was never closed
}
}