Balanced Parenthesis Problem in C++

Understanding Balanced Parenthesis Problem

The balanced parenthesis problem involves checking whether a given string of brackets is balanced or not.

We will explore three different methods to solve this problem in C++.

Method 1: Using Stack

#include <iostream>
#include <stack>
using namespace std;

bool isBalanced(string expr) {
    stack s;
    for (char ch : expr) {
        if (ch == '(' || ch == '{' || ch == '[') {
            s.push(ch);
        } else {
            if (s.empty()) return false;
            char last = s.top(); s.pop();
            if ((ch == ')' && last != '(') || 
                (ch == '}' && last != '{') || 
                (ch == ']' && last != '[')) {
                return false;
            }
        }
    }
    return s.empty();
}

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

Method 2: Using Counter

#include <iostream>
using namespace std;

bool isBalanced(string expr) {
    int count = 0;
    for (char ch : expr) {
        if (ch == '(') count++;
        else if (ch == ')') count--;
        if (count < 0) return false;
    }
    return count == 0;
}

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

Method 3: Recursion

#include <iostream>
using namespace std;

bool checkBalance(string expr, int index, int count) {
    if (count < 0) return false;
    if (index == expr.size()) return count == 0;
    if (expr[index] == '(') return checkBalance(expr, index + 1, count + 1);
    if (expr[index] == ')') return checkBalance(expr, index + 1, count - 1);
    return checkBalance(expr, index + 1, count);
}

int main() {
    string expr = "((()))";
    cout << (checkBalance(expr, 0, 0) ? "Balanced" : "Not Balanced") << endl;
    return 0;
}