Balancing Parenthesis

A program to check if the parenthesis are balanced in an equation.

Procedure :

• Iterate through the input equation character by character.

• If an opening bracket is found, push it to stack.

• If a closing bracket is found, pop from the stack and check if the popped bracket and the closing bracket match (are of the same type).

• If stack is empty and a closing bracket is found, the parenthesis are not balanced.

• If the stack is empty after iterating through all the characters, the parenthesis are balanced. Else, they are not balanced.

C Function :

// Function to check if pair is matching

int isMatchingPair(char a, char b) {

    if ( (a == '(' && b == ')') || (a == '[' && b == ']') || (a == '{' && b == '}') ) {
        return 1;
    } 
    return 0;

}

int isBalanced(char *equation) {

    // Creating a stack of max size equal to string length
    int len = strlen(equation);
    char stack[len];
    int top = -1;
    
    // Iterating through each character
    for (int i = 0; equation[i] != '\0'; i++) {
        // Push to stack if opening bracket
        if (equation[i] == '(' || equation[i] == '[' || equation[i] == '{') {
            top++;
            stack[top] = equation[i];
        } 
        // Pop from stack if closing bracket
        else if (equation[i] == ')' || equation[i] == ']' || equation[i] == '}') {
            char poppedBracket = stack[top];
            top--;
            // If pairs are not matching, return false.
            if (!isMatchingPair(poppedBracket, equation[i])) {
                return 0;
            }
        }
    }

    // If stack is empty, parenthesis are balanced.    
    if (top == -1) {
        return 1;
    }
    return 0;

}

Contributed by Nitin Ranganath