How to Check if a String has Balanced Parentheses in C

Check if a String has Balanced Parentheses in C

To determine if a string has balanced parentheses in C, we can use different approaches such as a simple counter for single-type parentheses or a stack-based method for multiple types and nested structures.

---

Example 1: Checking Balanced Parentheses Using a Counter

This example shows how to check if a string has balanced parentheses by using a counter. We traverse the string, incrementing the counter when we encounter an opening parenthesis ‘(‘ and decrementing it when we encounter a closing parenthesis ‘)’. If the counter becomes negative or isn’t zero at the end, the parentheses are unbalanced.

Explanation:

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

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

int main() {
    char expression[] = "((a+b) * (c-d))";
    if (isBalanced(expression))
        printf("The string has balanced parentheses.\\n");
    else
        printf("The string does not have balanced parentheses.\\n");
    return 0;
}

Explanation:

1. isBalanced() function iterates through the string using a for loop.
2. count variable is incremented for each ‘(‘ encountered and decremented for each ‘)’.
3. If count becomes negative at any point, a closing parenthesis appears without a matching opening one, so the function returns false.
4. After iterating, if count equals zero, the parentheses are balanced; otherwise, they are not.
5. The main() function tests the isBalanced() function with the expression “((a+b) * (c-d))” and prints the appropriate message.

Output:

The string has balanced parentheses.

---

Example 2: Checking Balanced Parentheses and Brackets Using a Stack

This example demonstrates a more robust method by using a stack to check for balanced parentheses as well as other types of brackets like ‘{‘, ‘}’, ‘[‘ and ‘]’. The stack helps manage nested and multiple types of brackets effectively.

Explanation:

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

#define MAX 100

// Define a Stack structure to hold characters
typedef struct {
    char items[MAX];
    int top;
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

bool isEmpty(Stack *s) {
    return s->top == -1;
}

bool push(Stack *s, char item) {
    if (s->top >= MAX - 1)
        return false;
    s->items[++(s->top)] = item;
    return true;
}

char pop(Stack *s) {
    if (isEmpty(s))
        return '\0';
    return s->items[(s->top)--];
}

bool isMatchingPair(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '{' && close == '}') ||
           (open == '[' && close == ']');
}

bool areParenthesesBalanced(const char *expr) {
    Stack s;
    initStack(&s);
    for (int i = 0; expr[i] != '\0'; i++) {
        if (expr[i] == '(' || expr[i] == '{' || expr[i] == '[')
            push(&s, expr[i]);
        else if (expr[i] == ')' || expr[i] == '}' || expr[i] == ']') {
            if (isEmpty(&s) || !isMatchingPair(pop(&s), expr[i]))
                return false;
        }
    }
    return isEmpty(&s);
}

int main() {
    char expression[] = "{[(a+b)*(c-d)] + (e/f)}";
    if (areParenthesesBalanced(expression))
        printf("The string has balanced parentheses and brackets.\\n");
    else
        printf("The string does not have balanced parentheses and brackets.\\n");
    return 0;
}

Explanation:

1. Stack structure is defined to store characters with a fixed size (MAX).
2. initStack() initializes the stack by setting top to -1.
3. push() adds an opening bracket to the stack and pop() removes the top element.
4. isMatchingPair() checks if the opening and closing characters form a valid pair.
5. areParenthesesBalanced() iterates through the string: pushing opening brackets onto the stack and checking matching pairs when encountering closing brackets.
6. If a closing bracket does not match or the stack is empty when expected to pop, the function returns false.
7. After processing the entire string, if the stack is empty, the expression is balanced.
8. The main() function tests the approach with the expression “{[(a+b)*(c-d)] + (e/f)}” and prints the corresponding message.

Output:

The string has balanced parentheses and brackets.

Conclusion

In this tutorial, we learned two different approaches to check if a string has balanced parentheses in C. The first method uses a simple counter suitable for strings containing only one type of parenthesis, while the second method employs a stack to handle multiple types and nested structures.