C++ Program to Check Balanced Parentheses

Use a stack in C++ to check balanced parentheses by pushing opening brackets with stack.push() and popping when matching closing brackets appear, returning false if mismatched or stack is not empty at the end.

Examples

Input()[]{}

OutputBalanced

Input([)]

OutputNot Balanced

Input((()))

OutputBalanced

How to Think About It

To check balanced parentheses, scan the string from left to right. When you see an opening bracket like (, [, or {, remember it by pushing it onto a stack. When you see a closing bracket, check if it matches the last opening bracket by popping from the stack. If it doesn't match or the stack is empty when you try to pop, the parentheses are not balanced. At the end, if the stack is empty, all parentheses matched correctly.

Algorithm

1

Create an empty stack.

2

For each character in the input string:

3

If it is an opening bracket, push it onto the stack.

4

If it is a closing bracket, check if the stack is empty or the top does not match; if so, return not balanced.

5

Pop the matching opening bracket from the stack.

6

After processing all characters, if the stack is empty, return balanced; otherwise, not balanced.

Code

cpp

#include <iostream>
#include <stack>
#include <string>

bool isBalanced(const std::string& s) {
    std::stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
            st.pop();
        }
    }
    return st.empty();
}

int main() {
    std::string input = "()[]{}";
    std::cout << (isBalanced(input) ? "Balanced" : "Not Balanced") << std::endl;
    return 0;
}

Output

Balanced

Dry Run

Let's trace the input "()[]{}" through the code

1

Start with empty stack

stack = []

2

Read '(' - push to stack

stack = ['(']

3

Read ')' - matches top '(' - pop stack

stack = []

4

Read '[' - push to stack

stack = ['[']

5

Read ']' - matches top '[' - pop stack

stack = []

6

Read '{' - push to stack

stack = ['{']

7

Read '}' - matches top '{' - pop stack

stack = []

8

End of string - stack empty means balanced

stack = []

Step	Character	Stack Content	Action
1	(	['(']	Push '('
2	)	[]	Pop '('
3	[	['[']	Push '['
4	]	[]	Pop '['
5	{	['{']	Push '{'
6	}	[]	Pop '{'

Why This Works

Step 1: Use stack to remember opening brackets

A stack stores opening brackets as they appear, so we can check them later against closing brackets.

Step 2: Match closing brackets with stack top

When a closing bracket appears, it must match the last opening bracket on the stack; otherwise, parentheses are unbalanced.

Step 3: Check stack empty at end

If the stack is empty after processing all characters, all brackets matched correctly, so the string is balanced.

Alternative Approaches

Using counters for only parentheses ()

cpp

#include <iostream>
#include <string>

bool isBalancedSimple(const std::string& s) {
    int count = 0;
    for (char c : s) {
        if (c == '(') count++;
        else if (c == ')') {
            if (count == 0) return false;
            count--;
        }
    }
    return count == 0;
}

int main() {
    std::string input = "(()())";
    std::cout << (isBalancedSimple(input) ? "Balanced" : "Not Balanced") << std::endl;
    return 0;
}

This method only works for parentheses '()' and is simpler but cannot handle mixed types like '{}' or '[]'.

Using recursion to check balanced parentheses

cpp

#include <iostream>
#include <string>

bool check(const std::string& s, int& i) {
    while (i < (int)s.size()) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            char open = s[i];
            i++;
            if (!check(s, i)) return false;
            if (i >= (int)s.size()) return false;
            char close = s[i];
            if ((open == '(' && close != ')') ||
                (open == '[' && close != ']') ||
                (open == '{' && close != '}')) return false;
            i++;
        } else {
            return true;
        }
    }
    return true;
}

bool isBalancedRecursive(const std::string& s) {
    int i = 0;
    if (!check(s, i)) return false;
    return i == (int)s.size();
}

int main() {
    std::string input = "({[]})";
    std::cout << (isBalancedRecursive(input) ? "Balanced" : "Not Balanced") << std::endl;
    return 0;
}

Recursion can check balanced parentheses by matching pairs, but it is more complex and less efficient than stack.

Complexity: O(n) time, O(n) space

Time Complexity

The program scans the string once, processing each character in constant time, so time is O(n) where n is string length.

Space Complexity

The stack can hold up to n/2 opening brackets in worst case, so space is O(n).

Which Approach is Fastest?

The stack approach is efficient and clear for all bracket types; counter method is faster but limited to one bracket type; recursion is slower and more complex.

Approach	Time	Space	Best For
Stack	O(n)	O(n)	All bracket types, general use
Counter (simple)	O(n)	O(1)	Only parentheses '()'
Recursion	O(n)	O(n)	Conceptual understanding, less practical