Postfix expression evaluation

Postfix (reverse Polish notation) lists operands before their operator: 4 2 + 3 * means “take 4 and 2, add, then multiply by 3,” i.e. infix (4 + 2) * 3. Evaluation uses a stack of values: each number is pushed; each binary operator pops the right operand then the left, applies the operation, and pushes the result. One pass over the string is O(n) time for n tokens.

1) Why a stack?

When you see an operator in postfix, its two operands are always the two most recent values not yet combined—exactly the two values on top of the stack. After combining them, you push one new value back, so the stack always represents “pending” sub-results in the correct order.

2) Evaluation rules

Assume a valid postfix expression with binary operators. Scan one character at a time (this demo uses single-digit non-negative operands with no spaces).

3) Example in C

The stack stores int values. The program reads a postfix string with scanf("%s", ...); only single digits and the four operators are handled. Division uses integer division and avoids dividing by zero in this demo.

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

#define MAX 100

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

// Push value onto stack
void push(int x) {
    stack[++top] = x;
}

// Pop value from stack
int pop(void) {
    return stack[top--];
}

// Binary operator?
int is_operator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

// Apply op to a (left) and b (right)
int eval_op(char op, int a, int b) {
    switch (op) {
    case '+':
        return a + b;
    case '-':
        return a - b;
    case '*':
        return a * b;
    case '/':
        return b != 0 ? a / b : 0;
    default:
        return 0;
    }
}

int main(void) {
    char exp[MAX];
    int i;

    printf("Enter postfix (single digits, no spaces): ");
    scanf("%s", exp);

    for (i = 0; exp[i] != '\0'; i++) {
        char ch = exp[i];
        if (isdigit((unsigned char)ch))
            push(ch - '0');
        else if (is_operator(ch)) {
            int b = pop();
            int a = pop();
            push(eval_op(ch, a, b));
        }
    }

    printf("Result: %d\n", pop());
    return 0;
}

Use scanf("%99s", exp) (with MAX == 100) or fgets to limit input length. Check top before each pop and reject invalid expressions. Multi-digit numbers, spaces, unary minus, and floats need a richer tokenizer or a different input format.

Trace for 42+3*

Infix meaning: (4 + 2) * 3 = 18. Stack entries are listed bottom → top.

Key points

4) Trade-offs

• Pros — No parentheses during evaluation; one stack, one scan; easy to implement for integers.
• Cons — Operand format must be unambiguous (here: one digit per number); error handling and floating-point need more code.

Get postfix from infix with Infix to postfix. More stack uses appear on Stack applications.