Definition
- Valid Parentheses – a classic stack problem that checks whether every opening bracket has a correctly typed and correctly ordered closing bracket.
- Algorithm – push each opening bracket onto a stack, and on each closing bracket pop the top and verify it is the matching opener type.
- Two failure conditions – an empty stack when a closer arrives means an unmatched close, and a non-empty stack after the full scan means unmatched opens.
- Matching map – a small Map from each closer to its expected opener keeps the comparison clean and easy to extend.
- Complexity – O(n) time because each character is pushed and popped at most once, and O(n) space in the worst case of all openers.
Imagine Rajesh at the National Bank of India opening nested approval requests. He opens a loan request, then inside it opens a document-verification request, then inside that a signature request. Each request he opens, he writes on a sticky note and places on top of a pile. When a request closes, the one on top must be the most recently opened. If a signature request tries to close while a document request is on top, the paperwork is out of order and the batch is rejected.
Understanding the Concepts
What is the Valid Parentheses problem?
The problem asks whether a string containing only round (), square [], and curly {} brackets is balanced and properly nested. Every opening bracket must have a matching closing bracket of the same type, and they must close in the reverse order they were opened. This last-opened-first-closed discipline is exactly what a stack models.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;
public class ValidParentheses {
public static boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
for (char c : s.toCharArray()) {
if (pairs.containsValue(c)) {
stack.push(c);
} else if (pairs.containsKey(c)) {
if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
return false;
}
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
System.out.println(isValid("({[]})")); // true
System.out.println(isValid("({[)]")); // false
System.out.println(isValid("(((")); // false
}
}
true
false
false
Why does this problem use a stack?
Brackets must close in the reverse order they opened. If you open round, then square, then curly, you must close curly first, then square, then round. This reverse ordering is exactly Last In First Out, which is the behavior a stack enforces. No other data structure naturally provides this guarantee.
package com.bank.core;
import java.util.ArrayDeque;
import java.util.Deque;
public class WhyStack {
public static void main(String[] args) {
// Nested approvals: loan > document > signature
Deque<String> approvals = new ArrayDeque<>();
approvals.push("Loan approval opened");
approvals.push("Document verification opened");
approvals.push("Signature request opened");
// Must close in reverse order
System.out.println("Close: " + approvals.pop()); // Signature first
System.out.println("Close: " + approvals.pop()); // Document second
System.out.println("Close: " + approvals.pop()); // Loan last
}
}
Close: Signature request opened
Close: Document verification opened
Close: Loan approval opened
How does the algorithm work step by step?
You scan the string left to right. For each opening bracket, push it onto the stack. For each closing bracket, check that the stack is not empty and that the popped top is the matching opener. If either check fails, return false immediately. After the full scan, return whether the stack is empty.
The matching logic uses a small map from each closer to its expected opener. For example, ) maps to (, ] maps to [, and } maps to {. On a closing bracket c, you look up pairs.get(c) and compare it to stack.pop().
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;
public class StepByStepValidation {
public static void main(String[] args) {
String formula = "{[()]}";
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
for (int i = 0; i < formula.length(); i++) {
char c = formula.charAt(i);
if (pairs.containsValue(c)) {
stack.push(c);
System.out.println("Index " + i + ": push '" + c + "' -> stack " + stack);
} else {
char top = stack.pop();
boolean match = top == pairs.get(c);
System.out.println("Index " + i + ": pop '" + top + "' vs expected '" + pairs.get(c) + "' -> " + (match ? "match" : "MISMATCH"));
}
}
System.out.println("Valid: " + stack.isEmpty());
}
}
Index 0: push '{' -> stack [{]
Index 1: push '[' -> stack [[, {]
Index 2: push '(' -> stack [(, [, {]
Index 3: pop '(' vs expected '(' -> match
Index 4: pop '[' vs expected '[' -> match
Index 5: pop '{' vs expected '{' -> match
Valid: true
What are the two failure conditions?
The first failure is a closing bracket arriving when the stack is empty. This means a closer has no matching opener, like a string that starts with ). The second failure is the string ending with brackets still on the stack, which means some openers were never closed. Both checks are essential for correctness.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;
public class FailureCases {
public static String validate(String s) {
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (pairs.containsValue(c)) {
stack.push(c);
} else if (pairs.containsKey(c)) {
if (stack.isEmpty()) return "Failure: unmatched closer at index " + i;
if (stack.pop() != pairs.get(c)) return "Failure: wrong type at index " + i;
}
}
return stack.isEmpty() ? "Valid" : "Failure: " + stack.size() + " unmatched openers";
}
public static void main(String[] args) {
System.out.println(validate(")(")); // unmatched closer
System.out.println(validate("(((")); // unmatched openers
System.out.println(validate("({)}")); // wrong type
System.out.println(validate("()[]{}")); // valid
}
}
Failure: unmatched closer at index 0
Failure: 3 unmatched openers
Failure: wrong type at index 2
Valid
What are the edge cases?
An empty string is valid because there are no unmatched brackets. A string of odd length can never be balanced because brackets pair in twos, so you can reject it in O(1). A single opener or a single closer is invalid. Nested and sequential combinations like "({})[]" must both pass.
package com.bank.service;
public class EdgeCases {
public static boolean isValid(String s) {
if (s.length() % 2 != 0) return false; // odd length shortcut
java.util.Deque<Character> stack = new java.util.ArrayDeque<>();
java.util.Map<Character, Character> pairs = java.util.Map.of(')', '(', ']', '[', '}', '{');
for (char c : s.toCharArray()) {
if (pairs.containsValue(c)) stack.push(c);
else if (pairs.containsKey(c)) {
if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
System.out.println("Empty: " + isValid("")); // true
System.out.println("Odd: " + isValid("(()")); // false (odd shortcut)
System.out.println("Single open: " + isValid("(")); // false
System.out.println("Nested+seq: " + isValid("({})[]")); // true
}
}
Empty: true
Odd: false
Single open: false
Nested+seq: true
What are common mistakes?
The most common mistake is forgetting the final stack.isEmpty() check. Without it, a string of all openers like "(((" passes because no mismatch occurs during the scan. Another mistake is using == to compare Character objects beyond the cached range; using char primitives avoids this.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
public class CommonMistakes {
// WRONG: missing final isEmpty check
public static boolean wrongValidation(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;
stack.pop(); // not even checking the type
}
}
return true; // BUG: should be stack.isEmpty()
}
public static void main(String[] args) {
System.out.println("Wrong accepts '(((': " + wrongValidation("(((")); // true (wrong)
System.out.println("Wrong accepts '({)}': " + wrongValidation("({)}")); // true (wrong)
}
}
Wrong accepts '(((': true
Wrong accepts '({)}': true
How is this applied in banking systems?
In the fee calculation engine at National Bank of India, fee formulas use nested brackets like {(base + [tax * rate]) * discount}. Before the formula parser evaluates the expression, a parentheses validator runs as a fast pre-check. If the brackets are unbalanced, the formula is rejected immediately and written to an audit log, protecting the parser from evaluating a corrupt or truncated expression.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;
public class FeeFormulaValidator {
private static final Map<Character, Character> PAIRS =
Map.of(')', '(', ']', '[', '}', '{');
public static boolean validateFormula(String formula) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : formula.toCharArray()) {
if (PAIRS.containsValue(c)) {
stack.push(c);
} else if (PAIRS.containsKey(c)) {
if (stack.isEmpty() || stack.pop() != PAIRS.get(c)) {
return false;
}
}
// skip non-bracket characters like digits and operators
}
return stack.isEmpty();
}
public static void main(String[] args) {
String good = "{(base + [tax * rate]) * discount}";
String bad = "{(base + [tax * rate) * discount}";
System.out.println("Good formula valid: " + validateFormula(good));
System.out.println("Bad formula valid: " + validateFormula(bad));
}
}
Good formula valid: true
Bad formula valid: false
What about time and space complexity?
Time is O(n) because each character is visited once, and each character is pushed and popped at most once. Space is O(n) in the worst case, which happens when the entire string is openers. In practice, the stack grows only to the maximum nesting depth, which for well-formed formulas is much smaller than the string length.
package com.bank.core;
public class ComplexityAnalysis {
public static void main(String[] args) {
// Worst case: all openers, stack grows to n
String worst = "(((((((((("; // 10 openers
System.out.println("Input length: " + worst.length());
System.out.println("Stack max size: " + worst.length() + " (all openers)");
// Best case: immediate mismatch, O(1) exit
String best = ")";
System.out.println("Immediate fail on: '" + best + "'");
}
}
Input length: 10
Stack max size: 10 (all openers)
Immediate fail on: ')'
What should a senior engineer know?
This stack technique is the foundation of real parsing. The identical idea scales to matching HTML and XML tags, validating nested expressions, and checking balanced quotes. It is also the first step toward shunting-yard expression evaluation. Prefer ArrayDeque over the legacy Stack class because Stack extends Vector and synchronizes every call, which adds needless overhead in single-threaded parsing.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;
public class ExtensibleValidator {
// Easily extensible to new bracket types
private static final Map<Character, Character> PAIRS = Map.of(
')', '(', ']', '[', '}', '{',
'>', '<' // custom angle brackets for XML-style tags
);
public static boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (PAIRS.containsValue(c)) stack.push(c);
else if (PAIRS.containsKey(c)) {
if (stack.isEmpty() || stack.pop() != PAIRS.get(c)) return false;
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
System.out.println(isValid("<{[()]}>")); // true with angle brackets
System.out.println(isValid("<{[(>)]}")); // false
}
}
true
false
Visual Overview
Validation of "{[()]}"
──────────────────────
Index 0: '{' → push
Stack: [ { ]
Index 1: '[' → push
Stack: [ [ { ]
Index 2: '(' → push
Stack: [ ( [ { ]
Index 3: ')' → pop '(' matches ')' ✓
Stack: [ [ { ]
Index 4: ']' → pop '[' matches ']' ✓
Stack: [ { ]
Index 5: '}' → pop '{' matches '}' ✓
Stack: [ ] (empty)
Result: stack is empty → VALID
Failure on "({)}"
─────────────────
Index 0: '(' → push
Stack: [ ( ]
Index 1: '{' → push
Stack: [ { ( ]
Index 2: ')' → pop '{' does NOT match ')' ✗
Result: MISMATCH → INVALID
Key Takeaway
Valid Parentheses is the textbook example of when a stack is the right data structure, because the rule governing brackets is Last In First Out: the bracket that closes must always be the one most recently opened. My approach is to scan the string once, push every opening bracket onto a stack, and on every closing bracket pop the top and confirm it is the matching opener. I keep a small map from each closing bracket to its expected opening bracket so the match check is a constant-time lookup rather than a chain of conditionals.
There are two failure cases I handle explicitly. The first is a closing bracket arriving when the stack is empty, which means a closer has no matching opener. The second is the string ending with brackets still on the stack, which means some openers were never closed. Both checks together are what make the solution correct, and candidates who forget the final isEmpty() check wrongly pass strings like three open parentheses.
The algorithm runs in O(n) time because each character is pushed and popped at most once, and it uses O(n) space in the worst case of an all-opening string. I always reach for ArrayDeque rather than the old Stack class, because Stack extends Vector and synchronizes every call, which adds pointless locking in a single-threaded parser. I also add the odd-length shortcut: a string of odd length can never be balanced, so I reject it in constant time before the loop even starts.
In my banking project at the National Bank of India, I used this as a fast pre-check on fee-calculation formulas whose nested segments are delimited by brackets. A malformed formula with crossed or dangling brackets gets rejected before the parser ever evaluates it, which protects the calculation engine from corrupt expressions and gives the operations team a clean audit trail of every rejected formula.
Remember one sentence: push every opener, pop and type-match on every closer, and the string is valid only if the stack ends empty.
---