Balanced Parentheses
In this page:
Parentheses Matching
Checking whether brackets in an expression are balanced, like matching every ( with a ) and every [ with a ], is a classic problem that a stack solves cleanly because of its LIFO ordering.
Example: Parentheses Matching
#include <iostream>
#include <stack>
using namespace std;
int main() {
string expr = "([{}])";
stack<char> s;
cout << "checking " << expr << " for balance using a stack" << endl;
return 0;
}public class Main {
public static void main(String[] args) {
String expr = "([{}])";
System.out.println("checking " + expr + " for balance using a stack");
}
}expr = "([{}])"
print("checking", expr, "for balance using a stack")#include <stdio.h>
int main() {
char *expr = "([{}])";
printf("checking %s for balance using a stack\n", expr);
return 0;
}Login to try C/C++/Java code in the editor
Opening and Closing Brackets
The algorithm pushes every opening bracket it encounters onto the stack, and whenever it hits a closing bracket, it checks that the top of the stack is the matching opening type, popping it off if so.
Example: Opening and Closing Brackets
#include <iostream>
#include <stack>
using namespace std;
int main() {
string expr = "(a[b]{c})";
stack<char> s;
for (char ch : expr) {
if (ch == '(' || ch == '[' || ch == '{') s.push(ch);
else if (ch == ')' || ch == ']' || ch == '}') {
if (!s.empty()) s.pop();
}
}
cout << "stack size after scan: " << s.size() << endl;
return 0;
}import java.util.Stack;
public class Main {
public static void main(String[] args) {
String expr = "(a[b]{c})";
Stack<Character> s = new Stack<>();
for (char ch : expr.toCharArray()) {
if (ch == '(' || ch == '[' || ch == '{') s.push(ch);
else if (ch == ')' || ch == ']' || ch == '}') {
if (!s.isEmpty()) s.pop();
}
}
System.out.println("stack size after scan: " + s.size());
}
}expr = "(a[b]{c})"
s = []
for ch in expr:
if ch in "([{":
s.append(ch)
elif ch in ")]}":
if s:
s.pop()
print("stack size after scan:", len(s))#include <stdio.h>
#include <string.h>
int main() {
char *expr = "(a[b]{c})";
char s[20]; int top = -1;
for (int i = 0; i < strlen(expr); i++) {
char ch = expr[i];
if (ch == '(' || ch == '[' || ch == '{') s[++top] = ch;
else if (ch == ')' || ch == ']' || ch == '}') { if (top >= 0) top--; }
}
printf("stack size after scan: %d\n", top + 1);
return 0;
}Login to try C/C++/Java code in the editor
Balanced Expressions
An expression is balanced only if every opening bracket is eventually closed in the correct order and the stack ends up completely empty once the whole expression has been scanned.
Example: Balanced Expressions
#include <iostream>
#include <stack>
using namespace std;
bool isBalanced(string expr) {
stack<char> s;
for (char ch : expr) {
if (ch == '(' || ch == '[' || ch == '{') s.push(ch);
else if (ch == ')' && (s.empty() || s.top() != '(')) return false;
else if (ch == ')') s.pop();
}
return s.empty();
}
int main() {
cout << "([)] balanced: " << isBalanced("([)]") << endl;
cout << "(()) balanced: " << isBalanced("(())") << endl;
return 0;
}import java.util.Stack;
public class Main {
static boolean isBalanced(String expr) {
Stack<Character> s = new Stack<>();
for (char ch : expr.toCharArray()) {
if (ch == '(') s.push(ch);
else if (ch == ')') {
if (s.isEmpty() || s.pop() != '(') return false;
}
}
return s.isEmpty();
}
public static void main(String[] args) {
System.out.println("([)] balanced: " + isBalanced("([)]"));
System.out.println("(()) balanced: " + isBalanced("(())"));
}
}def is_balanced(expr):
s = []
for ch in expr:
if ch == "(":
s.append(ch)
elif ch == ")":
if not s or s.pop() != "(":
return False
return not s
print("([)] balanced:", is_balanced("([)]"))
print("(()) balanced:", is_balanced("(())"))#include <stdio.h>
#include <string.h>
int isBalanced(char *expr) {
char s[20]; int top = -1;
for (int i = 0; i < strlen(expr); i++) {
if (expr[i] == '(') s[++top] = expr[i];
else if (expr[i] == ')') {
if (top < 0) return 0;
top--;
}
}
return top == -1;
}
int main() {
printf("(()) balanced: %d\n", isBalanced("(())"));
return 0;
}Login to try C/C++/Java code in the editor
Stack-Based Validation
This exact pattern shows up constantly in technical interviews, because it tests whether you can map a real problem onto LIFO ordering, and it generalizes to validating nested structures like JSON or HTML tags.
Example: Stack-Based Validation
#include <iostream>
#include <stack>
using namespace std;
bool isBalanced(string expr) {
stack<char> s;
for (char ch : expr) {
if (ch == '{' || ch == '[') s.push(ch);
else if ((ch == '}' && (s.empty() || s.top() != '{')) ||
(ch == ']' && (s.empty() || s.top() != '['))) return false;
else if (ch == '}' || ch == ']') s.pop();
}
return s.empty();
}
int main() {
cout << "{\"a\": [1,2,3]} balanced: " << isBalanced("{[]}") << endl;
return 0;
}import java.util.Stack;
public class Main {
static boolean isBalanced(String expr) {
Stack<Character> s = new Stack<>();
for (char ch : expr.toCharArray()) {
if (ch == '{' || ch == '[') s.push(ch);
else if (ch == '}' || ch == ']') {
if (s.isEmpty()) return false;
s.pop();
}
}
return s.isEmpty();
}
public static void main(String[] args) {
System.out.println("JSON-like {[]} balanced: " + isBalanced("{[]}"));
}
}def is_balanced(expr):
s = []
for ch in expr:
if ch in "{[":
s.append(ch)
elif ch in "}]":
if not s:
return False
s.pop()
return not s
print("JSON-like {[]} balanced:", is_balanced("{[]}"))#include <stdio.h>
#include <string.h>
int isBalanced(char *expr) {
char s[20]; int top = -1;
for (int i = 0; i < strlen(expr); i++) {
if (expr[i] == '{' || expr[i] == '[') s[++top] = expr[i];
else if (expr[i] == '}' || expr[i] == ']') { if (top < 0) return 0; top--; }
}
return top == -1;
}
int main() {
printf("JSON-like {[]} balanced: %d\n", isBalanced("{[]}"));
return 0;
}Login to try C/C++/Java code in the editor
Parentheses Practice
Good practice includes edge cases like an unmatched closing bracket with nothing on the stack to match it, brackets closed in the wrong order (like ([)]), and a string that ends with unclosed brackets still on the stack.
Example: Parentheses Practice
#include <iostream>
#include <stack>
using namespace std;
bool isBalanced(string expr) {
stack<char> s;
for (char ch : expr) {
if (ch == '(') s.push(ch);
else if (ch == ')') {
if (s.empty()) return false;
s.pop();
}
}
return s.empty();
}
int main() {
cout << ") balanced: " << isBalanced(")") << endl;
cout << "(( balanced: " << isBalanced("((") << endl;
return 0;
}import java.util.Stack;
public class Main {
static boolean isBalanced(String expr) {
Stack<Character> s = new Stack<>();
for (char ch : expr.toCharArray()) {
if (ch == '(') s.push(ch);
else if (ch == ')') {
if (s.isEmpty()) return false;
s.pop();
}
}
return s.isEmpty();
}
public static void main(String[] args) {
System.out.println(") balanced: " + isBalanced(")"));
System.out.println("(( balanced: " + isBalanced("(("));
}
}def is_balanced(expr):
s = []
for ch in expr:
if ch == "(":
s.append(ch)
elif ch == ")":
if not s:
return False
s.pop()
return not s
print(") balanced:", is_balanced(")"))
print("(( balanced:", is_balanced("(("))#include <stdio.h>
#include <string.h>
int isBalanced(char *expr) {
char s[20]; int top = -1;
for (int i = 0; i < strlen(expr); i++) {
if (expr[i] == '(') s[++top] = expr[i];
else if (expr[i] == ')') { if (top < 0) return 0; top--; }
}
return top == -1;
}
int main() {
printf(") balanced: %d\n", isBalanced(")"));
printf("(( balanced: %d\n", isBalanced("(("));
return 0;
}Login to try C/C++/Java code in the editor
🔒
Chapter Quiz — Complete all 5 topics to unlock
0/5 topics done
Complete these topics first: