Brackets validation with a stack

A string of brackets is balanced when every opening symbol ( [ { has a matching closing symbol in the right order—like nested function calls unwinding. A stack fits naturally: push each opener; on a closer, the most recent opener on the stack must pair with it. If the stack is empty when you need a match, or types do not match (( with ]), the string is invalid. After scanning, the stack must be empty. Time is O(n) for length n.

1) Matching rules

Scan the string once, left to right. Characters that are not brackets are ignored in the program below (so {a+b} is checked only on { and }).

2) Pairing table

3) Example in C

A fixed-size char array acts as the stack; top == -1 means empty. The program reads one token with scanf("%s", ...) (no spaces inside the string).

#include <stdio.h>

#define MAX 100

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

// Push opening bracket
void push(char c) {
    stack[++top] = c;
}

// Pop opening bracket
char pop(void) {
    return stack[top--];
}

// Stack empty?
int is_empty(void) {
    return top < 0;
}

// Does this open/close pair match?
int matches(char open, char close) {
    if (open == '(')
        return close == ')';
    if (open == '[')
        return close == ']';
    if (open == '{')
        return close == '}';
    return 0;
}

// 1 = valid, 0 = invalid
int is_valid(const char *s) {
    int i;

    top = -1;
    for (i = 0; s[i] != '\0'; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{')
            push(c);
        else if (c == ')' || c == ']' || c == '}') {
            if (is_empty())
                return 0;
            if (!matches(pop(), c))
                return 0;
        }
    }
    return is_empty();
}

int main(void) {
    char s[MAX];

    printf("Enter string: ");
    scanf("%s", s);

    if (is_valid(s))
        printf("Valid brackets\n");
    else
        printf("Invalid brackets\n");

    return 0;
}

Prefer scanf("%99s", s) with MAX == 100 or fgets to cap length. Check top < MAX - 1 before push to avoid overflow. To reject non-bracket characters instead of skipping them, add an else branch that returns 0.

Trace — valid ([{}])

Stack entries are listed bottom → top.

Trace — invalid ([)]

Key points

4) Trade-offs

• Pros — One pass, simple array stack, classic interview pattern.
• Cons — Fixed MAX; for Unicode or multi-char “brackets” you need a richer model.

Introductory stack ideas: Stack introduction · Stack using array.