C Program to Check Balanced Parentheses Using Stack

A C program to check balanced parentheses using stack pushes opening brackets onto the stack and pops them when matching closing brackets appear, returning balanced if the stack is empty at the end; use code like push(), pop(), and isEmpty() functions to manage the stack.

Examples

Input()[]{}

OutputBalanced

Input([)]

OutputNot Balanced

Input((()))

OutputBalanced

How to Think About It

To check if parentheses are balanced, scan the string from left to right. When you see an opening bracket like (, [, or {, push it onto a stack. When you see a closing bracket, check if the top of the stack has the matching opening bracket. If it does, pop it; if not, the parentheses are not balanced. At the end, if the stack is empty, all parentheses matched correctly.

Algorithm

1

Initialize an empty stack.

2

For each character in the input string:

3

If it is an opening bracket, push it onto the stack.

4

If it is a closing bracket, check if the stack is empty or the top does not match; if so, return not balanced.

5

If it matches, pop the top of the stack.

6

After processing all characters, if the stack is empty, return balanced; otherwise, not balanced.

Code

c

#include <stdio.h>
#include <string.h>
#define MAX 100

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

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

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

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

int isBalanced(char *expr) {
    for (int i = 0; expr[i] != '\0'; i++) {
        char ch = expr[i];
        if (ch == '(' || ch == '[' || ch == '{') {
            push(ch);
        } else if (ch == ')' || ch == ']' || ch == '}') {
            if (top == -1) return 0; // Check stack empty before pop
            char topChar = pop();
            if (!isMatching(topChar, ch)) return 0;
        }
    }
    return top == -1;
}

int main() {
    char expr[MAX];
    printf("Enter expression: ");
    fgets(expr, MAX, stdin);
    expr[strcspn(expr, "\n")] = '\0';

    if (isBalanced(expr))
        printf("Balanced\n");
    else
        printf("Not Balanced\n");

    return 0;
}

Output

Enter expression: ()[]{}
Balanced

Dry Run

Let's trace the input '()[]{}' through the code

1

Read '('

Push '(' onto stack; stack = ['(']

2

Read ')'

Pop '(' from stack; check if '(' matches ')'; yes, continue; stack = []

3

Read '['

Push '[' onto stack; stack = ['[']

4

Read ']'

Pop '[' from stack; check if '[' matches ']'; yes, continue; stack = []

5

Read '{'

Push '{' onto stack; stack = ['{']

6

Read '}'

Pop '{' from stack; check if '{' matches '}'; yes, continue; stack = []

7

End of string

Stack is empty, so expression is Balanced

Step	Stack Content	Action
1	['(']	Push '('
2	[]	Pop '(' and match with ')'
3	['[']	Push '['
4	[]	Pop '[' and match with ']'
5	['{']	Push '{'
6	[]	Pop '{' and match with '}'
7	[]	Stack empty, Balanced

Why This Works

Step 1: Use stack to track opening brackets

The stack stores opening brackets as they appear, so we can match them later with closing brackets.

Step 2: Match closing brackets with stack top

When a closing bracket appears, it must match the top of the stack; otherwise, the expression is not balanced.

Step 3: Check stack empty at end

If the stack is empty after processing all characters, all brackets matched correctly, so the expression is balanced.

Alternative Approaches

Using recursion to check balanced parentheses

c

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

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

int check(char *expr, int *index) {
    while (expr[*index] != '\0') {
        char ch = expr[*index];
        (*index)++;
        if (ch == '(' || ch == '[' || ch == '{') {
            if (!check(expr, index)) return 0;
        } else if (ch == ')' || ch == ']' || ch == '}') {
            return isMatching(expr[*index - 2], ch);
        }
    }
    return 1;
}

int main() {
    char expr[100];
    printf("Enter expression: ");
    fgets(expr, 100, stdin);
    expr[strcspn(expr, "\n")] = '\0';
    int index = 0;
    if (check(expr, &index) && expr[index] == '\0')
        printf("Balanced\n");
    else
        printf("Not Balanced\n");
    return 0;
}

Recursion can be elegant but may be less efficient and harder to understand for beginners.

Using counters for only one type of parentheses

c

#include <stdio.h>

int main() {
    char expr[100];
    int count = 0;
    printf("Enter expression: ");
    fgets(expr, 100, stdin);
    for (int i = 0; expr[i] != '\0'; i++) {
        if (expr[i] == '(') count++;
        else if (expr[i] == ')') {
            if (count == 0) {
                printf("Not Balanced\n");
                return 0;
            }
            count--;
        }
    }
    if (count == 0) printf("Balanced\n");
    else printf("Not Balanced\n");
    return 0;
}

This method only works for one type of parentheses and is simpler but limited.

Complexity: O(n) time, O(n) space

Time Complexity

The program scans the input string once, performing push or pop operations which are O(1), so total time is O(n) where n is the length of the string.

Space Complexity

In the worst case, all characters are opening brackets, so the stack stores all of them, requiring O(n) space.

Which Approach is Fastest?

The stack approach is efficient and simple; recursion is elegant but may use more call stack space; counters are fastest but only work for one bracket type.

Approach	Time	Space	Best For
Stack	O(n)	O(n)	All types of parentheses, general use
Recursion	O(n)	O(n)	Elegant code, smaller inputs
Counters (single type)	O(n)	O(1)	Only one type of parentheses