This program checks whether a string of parentheses (including (), {}, and []) is balanced. A string is considered balanced if every opening parenthesis has a corresponding closing parenthesis in the correct order.

Program Explanation

The solution uses a stack to keep track of opening parentheses. The algorithm processes the string character by character:

1. If the current character is an opening parenthesis ((, {, [), push it onto the stack.
2. If the current character is a closing parenthesis (), }, ]), check if the stack is empty or the top of the stack has a matching opening parenthesis. If so, pop the stack; otherwise, the string is unbalanced.
3. At the end of the string, if the stack is empty, the string is balanced; otherwise, it is unbalanced.

C Program Code

#include <stdio.h>
#include <stdlib.h>

#define MAX 100  // Maximum size of the stack

// Stack structure
struct Stack {
    char arr[MAX];
    int top;
};

// Initialize the stack
void initStack(struct Stack *s) {
    s->top = -1;
}

// Check if the stack is empty
int isEmpty(struct Stack *s) {
    return s->top == -1;
}

// Check if the stack is full
int isFull(struct Stack *s) {
    return s->top == MAX - 1;
}

// Push an element onto the stack
void push(struct Stack *s, char value) {
    if (isFull(s)) {
        printf("Stack overflow\n");
        return;
    }
    s->arr[++(s->top)] = value;
}

// Pop an element from the stack
char pop(struct Stack *s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        return '\0';
    }
    return s->arr[(s->top)--];
}

// Peek the top element of the stack
char peek(struct Stack *s) {
    if (isEmpty(s)) {
        return '\0';
    }
    return s->arr[s->top];
}

// Function to check if two parentheses match
int isMatchingPair(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '{' && close == '}') ||
           (open == '[' && close == ']');
}

// Function to check if a string of parentheses is balanced
int isBalanced(char *expression) {
    struct Stack s;
    initStack(&s);

    for (int i = 0; expression[i] != '\0'; i++) {
        char currentChar = expression[i];

        // If it's an opening parenthesis, push it onto the stack
        if (currentChar == '(' || currentChar == '{' || currentChar == '[') {
            push(&s, currentChar);
        }
        // If it's a closing parenthesis, check for matching opening parenthesis
        else if (currentChar == ')' || currentChar == '}' || currentChar == ']') {
            if (isEmpty(&s) || !isMatchingPair(pop(&s), currentChar)) {
                return 0;  // Unbalanced if no matching pair
            }
        }
    }

    // If the stack is empty, all parentheses are balanced
    return isEmpty(&s);
}

// Main driver function
int main() {
    char expression[MAX];

    printf("Enter a string of parentheses: ");
    scanf("%s", expression);

    if (isBalanced(expression)) {
        printf("The parentheses are balanced.\n");
    } else {
        printf("The parentheses are not balanced.\n");
    }

    return 0;
}
    

Code Explanation

1. Stack Structure: A stack is used to store opening parentheses as they are encountered. It has operations to push() elements, pop() elements, and check the top element using peek().

2. Matching Parentheses: The function isMatchingPair() is used to check if two parentheses are a matching pair (e.g., ( matches )).

3. Balance Check: The function isBalanced() scans the string:

• It pushes opening parentheses onto the stack.
• For closing parentheses, it checks if the stack has a corresponding opening parenthesis. If not, the string is unbalanced.
• After the entire string is processed, the stack should be empty if the parentheses are balanced.

Sample Output

Enter a string of parentheses: {[()]}
The parentheses are balanced.
    
Enter a string of parentheses: {(])
The parentheses are not balanced.
    

Conclusion

This program efficiently checks if a string of parentheses is balanced using a stack. The algorithm processes the string in O(n) time, where n is the length of the string. The stack ensures that the program handles nested parentheses correctly and can detect mismatched or unbalanced parentheses.