Using stacks: brackets and postfix

Introduction

Two classic exam problems are solved with a stack.

Calculators, compilers and spreadsheets all have to read expressions such as (2 + 3) * 4. These are classic examination questions, and also the way real tools work.

How it works

Matching brackets

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

bool balanced(const char *s) {
    char st[50];
    int top = -1;
    for (int i = 0; s[i] != '\0'; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            st[++top] = c;
        } else if (c == ')' || c == ']' || c == '}') {
            if (top == -1) return false;
            char open = st[top--];
            if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{'))
                return false;
        }
    }
    return top == -1;
}

int main(void) {
    printf("{a[(b)]} -> %d\n", balanced("{a[(b)]}"));
    printf("(a] -> %d\n", balanced("(a]"));
    return 0;
}

Read the text left to right:

• an opening bracket is pushed;
• a closing bracket must match the bracket on top, which is popped. If the stack is empty, or the top is the wrong kind, the text is not balanced;
• at the end the stack must be empty, or some bracket was never closed.

The latest unclosed bracket must close first, which is exactly last in, first out. Compilers check your code's brackets this way.

From infix to postfix

To convert a + b * c to postfix, a stack holds the operators (this is Dijkstra's shunting-yard method):

1. Operands go straight to the output.
2. Before pushing an operator, pop to the output every operator on the stack with higher or equal precedence (stop at ().
3. ( is pushed; ) pops to the output until the matching (, which is thrown away.
4. At the end, pop everything left.

Syntax

int st[20];
int top = -1;

st[++top] = value;       // push
int b = st[top--];       // pop

++top moves up before storing. top-- reads first and then moves down.

Example

In postfix (Reverse Polish) notation, the operator comes after its two operands: 2 3 * means 2 * 3, and (2*3) + (5*4) is 2 3 * 5 4 * +. Postfix needs no brackets and no precedence rules, so it is easy for a program:

#include <stdio.h>
#include <ctype.h>

int main(void) {
    char expr[] = "23*54*+";   // (2*3) + (5*4)
    int st[20];
    int top = -1;
    for (int i = 0; expr[i] != '\0'; i++) {
        char c = expr[i];
        if (isdigit(c)) {
            st[++top] = c - '0';
        } else {
            int b = st[top--];
            int a = st[top--];
            if (c == '+') st[++top] = a + b;
            else if (c == '-') st[++top] = a - b;
            else if (c == '*') st[++top] = a * b;
            else st[++top] = a / b;
        }
    }
    printf("result: %d\n", st[top]);
    return 0;
}

• a digit is pushed;
• an operator pops two values, b first and then a, and pushes a op b. The order matters for - and /;
• at the end the stack holds the answer.

Line by line

1. expr is the postfix text. It means (2*3) + (5*4), and each operand is one digit.
2. st and top make a stack of whole numbers, with top at -1 when it is empty.
3. A digit is turned into its number with c - '0' and pushed.
4. An operator pops b first and then a, so a is the left operand.
5. The chain of if statements pushes the result of a and b.
6. When the text ends, the only value left on the stack is the answer.

Expected result

result: 26

In the real world

Compilers use this idea to turn the expressions you write into machine instructions. The Java Virtual Machine, and many others, are stack machines, which evaluate nearly everything in postfix order.

Common mistakes

• Popping the operands in the wrong order: for 8 2 - the answer is 8 - 2, so the first value popped is the right operand.
• Forgetting the final check that the bracket stack is empty: ((a) would be called balanced.
• Comparing an opening bracket with the wrong closing kind, so that (] is accepted.

Best practices

• Handle the empty stack before popping an operand or a bracket.
• Write a table of the stack after each token when a result looks wrong.
• Test with operators whose order matters, such as - and /.

Summary

A stack matches brackets by remembering the unclosed ones, and evaluates postfix by holding operands until an operator needs them. The shunting-yard method uses a stack of operators to turn infix into postfix.

Mark lesson complete