Infix to postfix

(8 - 2) * 3 + 4 needs brackets and rules to be read. Watch a stack rewrite it in an order that needs neither.

⋯20void to_postfix(const char *in, char *out)21{22    char ops[MAX];23    int top = 0;24    size_t k = 0;25    for (size_t i = 0; in[i] != '\0'; i++) {26        char c = in[i];27        if (c >= '0' && c <= '9') {28            emit(out, &k, c);29        } else if (c == '(') {30            ops[top] = c;31            top++;32        } else if (c == ')') {33            while (ops[top - 1] != '(') {34                top--;35                emit(out, &k, ops[top]);36            }37            top--;38        } else if (c == '+' || c == '-' || c == '*' || c == '/') {39            while (top > 0 && ops[top - 1] != '(' && prec(ops[top - 1]) >= prec(c)) {40                top--;41                emit(out, &k, ops[top]);42            }43            ops[top] = c;44            top++;45        }46    }47    while (top > 0) {48        top--;49        emit(out, &k, ops[top]);50    }51    out[k] = '\0';52}⋯54int main(void)55{56    const char *exprs[3] = { "(8 - 2) * 3 + 4", "8 - 2 * 3 + 4", "8 - 2 - 1" };57    char out[MAX];58    for (int i = 0; i < 3; i++) {59        to_postfix(exprs[i], out);60        printf("%-16s-> %s\n", exprs[i], out);61    }62    return 0;63}

Three ways to write a sum

The usual way to write a sum puts each operator between its two operands: 8 - 2. That is infix. It needs rules to be read: * before +, and brackets when you want something else. 8 - 2 * 3 is 2, but (8 - 2) * 3 is 18.

Postfix puts the operator after its operands: 8 2 -. Prefix puts it before: - 8 2. In both, the order of the tokens says exactly what to do, so neither needs brackets or precedence rules:

Postfix is not the expression reversed. The digits stay in the order they were written; only the operators move, each to just after the operands it works on.

The code and its cost

The rules

Read the infix expression from left to right, with a stack for operators:

• A digit goes straight to the output.
• An operator first sends out every waiting operator of higher or equal precedence (stopping at a (), then waits on the stack itself.
• A ( waits on the stack.
• A ) sends out every operator above its (, then the ( is dropped.
• At the end, every operator still waiting goes out.

* and / have precedence 2, + and - precedence 1. An operator that must be done first leaves the stack first, so it lands in the output first.

The function

void to_postfix(const char *in, char *out)
{
    char ops[MAX];
    int top = 0;
    size_t k = 0;
    for (size_t i = 0; in[i] != '\0'; i++) {
        char c = in[i];
        if (c >= '0' && c <= '9') {
            emit(out, &k, c);
        } else if (c == '(') {
            ops[top] = c;
            top++;
        } else if (c == ')') {
            while (ops[top - 1] != '(') {
                top--;
                emit(out, &k, ops[top]);
            }
            top--;
        } else if (c == '+' || c == '-' || c == '*' || c == '/') {
            while (top > 0 && ops[top - 1] != '(' && prec(ops[top - 1]) >= prec(c)) {
                top--;
                emit(out, &k, ops[top]);
            }
            ops[top] = c;
            top++;
        }
    }
    while (top > 0) {
        top--;
        emit(out, &k, ops[top]);
    }
    out[k] = '\0';
}

ops and top are a stack of chars, as in Matching brackets. emit(out, &k, c) writes c into out at position k, with a space before it unless it is the first token, and moves k on; it takes k’s address so that it can change to_postfix’s k. prec returns 2 for * and / and 1 for the others. The input must be well formed, with single digits; spaces are skipped.

Equal precedence and left associativity

The test is >=, not >. In 8 - 2 - 1, when the second - arrives, the first is waiting with the same precedence, so it leaves first: the output is 8 2 - 1 -, which means (8 − 2) − 1 = 5. That is what 8 - 2 - 1 means in arithmetic: operators of equal precedence are done from the left, which is called left associativity.

What it costs

Each character is read once. Each operator is pushed once and popped once. So an expression of n characters takes about n steps (O(n) in the notation of lesson 3.3), and the stack never holds more than the operators and brackets.

Running it yourself

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

(8 - 2) * 3 + 4 -> 8 2 - 3 * 4 +
8 - 2 * 3 + 4   -> 8 2 3 * - 4 +
8 - 2 - 1       -> 8 2 - 1 -

In the second, * waits on top of - because its precedence is higher (2 > 1); then + sends out * and then -. At that point two operators were waiting at once.

Worked example

(1 + 2) * (3 + 4). ( waits; 1 out; + waits above (; 2 out; ) sends + out and drops (. * waits. ( waits above *; 3 out; + waits above (, which stops it from looking at *; 4 out; ) sends + out. The end sends * out: 1 2 + 3 4 + *.

With > instead of >=. For 8 - 2 - 1, the second - would not send the first out, so both wait and leave at the end: 8 2 1 - -. That means 8 − (2 − 1) = 7, not 5. One character in the condition decides which way equal operators group.

Prefix. The prefix form of (8 - 2) * 3 + 4 is + * - 8 2 3 4: the last operation done, +, comes first.

Questions. The postfix of 2 * 3 + 4 * 5 is 2 3 * 4 5 * +. For 8 - 2 * 3 + 4, at most two operators wait at once (- and *).

Where it’s used

Compilers and calculators. A compiler reading a + b * c must decide what to do first; turning the expression into postfix, or into the tree that postfix describes, is how it records that decision. The method above is the classic way to do it.

Spreadsheets. A formula such as =(B2 - B3) * 2 is parsed the same way before it is worked out.

What comes next. Evaluating postfix (8.4) works out 8 2 - 3 * 4 + with a second stack, this time of numbers. Reading an expression tree in postorder gives its postfix (12.3).

Reference card

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