Matching brackets

Does every bracket in {[()()]} close the right one? Watch each opener wait on a stack until its closer arrives.

⋯11bool balanced(const char *s)12{13    char stack[CAP];14    int top = 0;15    for (size_t i = 0; s[i] != '\0'; i++) {16        char c = s[i];17        if (c == '(' || c == '[' || c == '{') {18            if (top == CAP)19                return false;20            stack[top] = c;21            top++;22        } else if (c == ')' || c == ']' || c == '}') {23            if (top == 0)24                return false;25            top--;26            if (!matches(stack[top], c))27                return false;28        }29    }30    return top == 0;31}⋯33int main(void)34{35    const char *cases[4] = { "{[()()]}", "([)]", "(()", "())" };36    for (int i = 0; i < 4; i++) {37        bool ok = balanced(cases[i]);38        printf("%-9s %d\n", cases[i], ok);39    }40    return 0;41}

The most recent opener

Read a string from left to right. Each closer has to close the most recent opener that is still open: in {[()()]}, the first ) closes the ( just before it, the ] closes the [, and the final } closes the { that came first of all. The opener needed next is always the last one seen and not yet closed. That is the top of a stack, as in Stacks.

So the rule is three lines:

• At an opener, push it.
• At a closer, pop the top opener and check that it is the same kind.
• At the end, the stack must be empty.

Other characters, letters, digits, spaces, are skipped.

The code and its cost

The function

bool balanced(const char *s)
{
    char stack[CAP];
    int top = 0;
    for (size_t i = 0; s[i] != '\0'; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            if (top == CAP)
                return false;
            stack[top] = c;
            top++;
        } else if (c == ')' || c == ']' || c == '}') {
            if (top == 0)
                return false;
            top--;
            if (!matches(stack[top], c))
                return false;
        }
    }
    return top == 0;
}

The stack is an array of 64 chars inside the function, with top counting the openers on it, exactly as in Stacks. matches(open, close) is true only for the three pairs (), [] and {}. A string nested deeper than 64 is reported unbalanced, because the stack is full (lines 18 and 19).

Three ways to fail

Each failure has its own line in the code, and the picture marks it on the string.

Why counting is not enough

A first idea is to count: as many ( as ), as many [ as ]. ([)] passes that test, one of each, and it is still wrong: the ) arrives while [ is the open bracket. Counting forgets the order. The stack keeps it.

What it costs

balanced reads each character once and does a fixed few steps for it, so a string of n characters takes about n steps (O(n) in the notation of lesson 3.3). The stack can grow as deep as the string is long: (((( needs four cells.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic brackets.c -o brackets
./brackets

It prints each string padded to nine characters, then a space and 1 or 0:

{[()()]}  1
([)]      0
(()       0
())       0

Worked example

a[i] = (b + c) * {d}; The letters, spaces and operators are skipped. [ goes on and ] takes it off; ( on, ) off; { on, } off. The stack is never more than one deep and ends empty: balanced, deepest 1.

if (x[0] == y)) { ( on, [ on, ] meets [, ) meets (, and the stack is empty. The second ) finds nothing to meet: unbalanced at index 14.

{"a": [1, 2, {"b": 3}]} { on, [ on, { on: three deep. Then }, ] and } each meet their own kind: balanced, deepest 3. A real checker for such data would also skip any bracket that appears inside quotes, like the ] in "a]"; this function does not.

Questions. In ((())), how deep does the stack get? Three. Where does {(}) fail? At }: the top of the stack is (.

Where it’s used

Compilers and editors. A compiler checks that every bracket in a program is closed before it goes further, and an editor uses the same stack to light up the bracket that matches the one under the cursor.

Nested data. Formats such as JSON and HTML nest one thing inside another; a reader checks that each part is closed in the right order, as here.

What comes next. Infix to postfix (8.3) uses a stack to turn 3 + 4 * 2 into an order a machine can work out.

Reference card

Platform: C11, gcc on x86-64 Linux: char 1 byte, int 4, little-endian.