Evaluating postfix

8 2 - 3 * 4 + has no brackets and no precedence, yet it has one answer. Watch a stack work it out.

⋯6bool eval_postfix(const char *s, int *result)7{8    int stack[MAX];9    int top = 0;10    for (size_t i = 0; s[i] != '\0'; i++) {11        char c = s[i];12        if (c == ' ')13            continue;14        if (c >= '0' && c <= '9') {15            if (top == MAX)16                return false;17            stack[top] = c - '0';18            top++;19            continue;20        }21        if (top < 2)22            return false;23        top--;24        int b = stack[top];25        top--;26        int a = stack[top];27        int r;28        if (c == '+')29            r = a + b;30        else if (c == '-')31            r = a - b;32        else if (c == '*')33            r = a * b;34        else if (c == '/' && b != 0)35            r = a / b;36        else37            return false;38        stack[top] = r;39        top++;40    }41    if (top != 1)42        return false;43    *result = stack[0];44    return true;45}⋯47int main(void)48{49    const char *exprs[4] = { "8 2 - 3 * 4 +", "8 2 3 * - 4 +", "8 +", "8 2" };50    for (int i = 0; i < 4; i++) {51        int v;52        if (eval_postfix(exprs[i], &v))53            printf("%-14s= %d\n", exprs[i], v);54        else55            printf("%-14serror\n", exprs[i]);56    }57    return 0;58}

Numbers wait, operators work

Infix to postfix turned (8 - 2) * 3 + 4 into 8 2 - 3 * 4 +. Working that out needs one stack and one rule for each kind of token:

• A number is pushed.
• An operator pops two values, works on them, and pushes the result.
• At the end, exactly one value is left: the answer.

There is no precedence to look up and no bracket to match. The rewriting into postfix has already put every operator just after the two values it works on, so the order of the tokens says it all.

The code and its cost

The function

bool eval_postfix(const char *s, int *result)
{
    int stack[MAX];
    int top = 0;
    for (size_t i = 0; s[i] != '\0'; i++) {
        char c = s[i];
        if (c == ' ')
            continue;
        if (c >= '0' && c <= '9') {
            if (top == MAX)
                return false;
            stack[top] = c - '0';
            top++;
            continue;
        }
        if (top < 2)
            return false;
        top--;
        int b = stack[top];
        top--;
        int a = stack[top];
        int r;
        if (c == '+')
            r = a + b;
        else if (c == '-')
            r = a - b;
        else if (c == '*')
            r = a * b;
        else if (c == '/' && b != 0)
            r = a / b;
        else
            return false;
        stack[top] = r;
        top++;
    }
    if (top != 1)
        return false;
    *result = stack[0];
    return true;
}

The stack is an array of 32 ints with top counting the values, as in Stacks. c - '0' turns the character '8' into the number 8, because the digit characters are consecutive. The answer goes back through the pointer result; the function itself returns whether the string made sense.

Which value is on the left

The first value popped is b, the right operand, because it was pushed last. The second is a, the left one. For 8 2 - that gives 8 − 2 = 6. Pop them the other way round and - gives −6, and / goes wrong in the same way; + and * would hide the mistake, since their order does not matter.

Errors

The program in the clip checks four strings. The first two are worked out, the last two are errors:

8 2 - 3 * 4 + = 22
8 2 3 * - 4 + = 6
8 +           error
8 2           error

What it costs

Each character is read once, and each token costs a fixed few steps: a push, or two pops and a push. A string of n characters takes about n steps (O(n) in the notation of lesson 3.3). Joined to 8.3’s function, an infix expression goes in and its value comes out after two passes.

Running it yourself

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

Worked example

4 1 3 + 2 * + 5 -. The stack after each token:

The answer is 7, and the stack is never more than three deep.

Order matters. 9 3 / is 9 / 3 = 3. 3 9 / is 3 / 9, which is 0 in integer division.

Back to infix. 8.3’s second output, 8 2 3 * - 4 +, is 2 × 3 = 6, then 8 − 6 = 2, then 2 + 4 = 6: the value of 8 - 2 * 3 + 4.

Questions. 5 2 - 4 * is (5 − 2) × 4 = 12. 8 + is an error because + has too few operands; 8 2 is an error of the other kind, a value left over.

Where it’s used

Calculators. Some calculators take their input in postfix, called reverse Polish entry: you key in 8, 2, then -, and the display shows the stack.

Virtual machines. Many languages compile programs into instructions for a stack machine, where push 8, push 2, subtract works exactly as here.

Page languages. PostScript, the printer language, and the drawing instructions inside PDF files are written in postfix and run on a stack.

What comes next. Working out an expression tree in postorder (12.3) is this same evaluation, with the tree in place of the string.

Reference card

Platform: C11, gcc on x86-64 Linux: char 1 byte, int 4, little-endian. Division of ints rounds toward zero.