Balanced Parentheses Problem Using Stack in DSA C

Mental Model

We use a stack to keep track of opening brackets and check if each closing bracket matches the last opened one.

Analogy: Imagine stacking plates; each time you see an opening bracket, you put a plate on the stack, and each closing bracket means you remove the top plate and check if it matches.

Stack (top at right): []
Expression: ( [ { } ] )
↑ Start scanning from left to right

Dry Run Walkthrough

Input: expression: "({[]})"

Goal: Check if all parentheses are balanced and correctly nested

Step 1: Read '(' and push it onto the stack

Stack: [ '(' ]
Expression: ( { [ ] } )
           ↑

Why: We store opening brackets to match them later with closing ones

Step 2: Read '{' and push it onto the stack

Stack: [ '(' -> '{' ]
Expression: ( { [ ] } )
             ↑

Why: Keep track of nested opening brackets

Step 3: Read '[' and push it onto the stack

Stack: [ '(' -> '{' -> '[' ]
Expression: ( { [ ] } )
               ↑

Why: Add another opening bracket to stack for matching

Step 4: Read ']' and pop top '[' from stack to match

Stack: [ '(' -> '{' ]
Expression: ( { [ ] } )
                 ↑

Why: Closing bracket matches the last opening bracket

Step 5: Read '}' and pop top '{' from stack to match

Stack: [ '(' ]
Expression: ( { [ ] } )
                   ↑

Why: Closing bracket matches the last opening bracket

Step 6: Read ')' and pop top '(' from stack to match

Stack: []
Expression: ( { [ ] } )
                     ↑

Why: Closing bracket matches the last opening bracket

Result:

Stack: []
All brackets matched correctly -> Balanced

Annotated Code

DSA C

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

#define MAX 100

typedef struct Stack {
    char items[MAX];
    int top;
} Stack;

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

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

int isFull(Stack* s) {
    return s->top == MAX - 1;
}

void push(Stack* s, char c) {
    if (!isFull(s)) {
        s->items[++(s->top)] = c;
    }
}

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

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

int isBalanced(const char* expr) {
    Stack s;
    init(&s);
    for (int i = 0; expr[i] != '\0'; i++) {
        char ch = expr[i];
        if (ch == '(' || ch == '{' || ch == '[') {
            push(&s, ch); // push opening bracket
        } else if (ch == ')' || ch == '}' || ch == ']') {
            if (isEmpty(&s)) {
                return 0; // no matching opening
            }
            char topChar = pop(&s); // pop last opening
            if (!isMatchingPair(topChar, ch)) {
                return 0; // mismatch
            }
        }
    }
    return isEmpty(&s); // balanced if stack empty
}

int main() {
    const char* expr = "({[]})";
    if (isBalanced(expr)) {
        printf("Balanced\n");
    } else {
        printf("Not Balanced\n");
    }
    return 0;
}

push(&s, ch); // push opening bracket

store opening bracket on stack to match later

if (isEmpty(&s)) { return 0; }

if closing bracket found but stack empty, no match possible

char topChar = pop(&s);

pop last opening bracket to check match

if (!isMatchingPair(topChar, ch)) { return 0; }

if popped opening and current closing don't match, fail

return isEmpty(&s);

if stack empty at end, all matched correctly

Output

Balanced

Complexity Analysis

Time: O(n) because we scan the expression once, pushing and popping at most once per character

Space: O(n) because in worst case all characters are opening brackets stored in stack

vs Alternative: Compared to counting brackets without stack, this method correctly handles nested and mixed types with linear time and space

Edge Cases

Empty string

Returns balanced because no brackets means nothing to mismatch

DSA C

return isEmpty(&s);

String with only opening brackets

Returns not balanced because stack not empty at end

DSA C

return isEmpty(&s);

String with closing bracket first

Returns not balanced because stack empty when closing bracket found

DSA C

if (isEmpty(&s)) { return 0; }

When to Use This Pattern

When you see a problem asking if brackets or symbols are properly opened and closed in order, use a stack to track openings and match closings.

Common Mistakes

Mistake: Not checking if stack is empty before popping on closing bracket
Fix: Add a check to return false if stack is empty before popping

Mistake: Not verifying that popped opening bracket matches current closing bracket
Fix: Use a function to check matching pairs and return false if mismatch

Summary

Checks if every opening bracket has a matching closing bracket in correct order using a stack

Use when you need to verify balanced and properly nested parentheses or brackets

The key is to push openings on stack and pop to match when a closing bracket appears