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 <stdio.h>
#include <stdbool.h>
#include <string.h>
#define MAX 100

char stack[MAX];
int top = -1;

void push(char c) {
    if (top == MAX - 1) return;
    stack[++top] = c;
}

char pop() {
    if (top == -1) return '\0';
    return stack[top--];
}

bool isBalanced(char *expr) {
    for (int i = 0; i < strlen(expr); i++) {
        if (expr[i] == '(' || expr[i] == '{' || expr[i] == '[') {
            push(expr[i]);
        } else {
            char last = pop();
            if ((expr[i] == ')' && last != '(') || 
                (expr[i] == '}' && last != '{') || 
                (expr[i] == ']' && last != '[')) {
                return false;
            }
        }
    }
    return top == -1;
}

int main() {
    char expr[] = "{[()]}";
    printf("%s\n", isBalanced(expr) ? "Balanced" : "Not Balanced");
    return 0;
}
            

Method 2: Using Counter

#include <stdio.h>
#include <stdbool.h>

bool isBalanced(char *expr) {
    int count = 0;
    for (int i = 0; expr[i] != '\0'; i++) {
        if (expr[i] == '(') count++;
        else if (expr[i] == ')') count--;
        if (count < 0) return false;
    }
    return count == 0;
}

int main() {
    char expr[] = "(())";
    printf("%s\n", isBalanced(expr) ? "Balanced" : "Not Balanced");
    return 0;
}
            

Method 3: Recursion

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

bool checkBalance(char *expr, int index, int count) {
    if (count < 0) return false;
    if (expr[index] == '\0') 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() {
    char expr[] = "((()))";
    printf("%s\n", checkBalance(expr, 0, 0) ? "Balanced" : "Not Balanced");
    return 0;
}