Postfix Expression Evaluator

How it works

1. Split the expression into tokens and start with an empty stack.
2. Number: push it.
3. Operator: pop b (the right operand, pushed last), then pop a (the left operand), compute a op b and push the result. With fewer than two values on the stack the expression is invalid.
4. At the end exactly one value must remain: that is the result. More than one means there were too few operators.

Worked example: 5 1 2 + 4 * + 3 -

• 5, 1, 2 → push each. Stack: 5 1 2
• + → b = 2, a = 1, 1 + 2 = 3. Stack: 5 3
• 4 → push. Stack: 5 3 4
• * → b = 4, a = 3, 3 × 4 = 12. Stack: 5 12
• + → b = 12, a = 5, 5 + 12 = 17. Stack: 17
• 3 → push. Stack: 17 3
• - → b = 3, a = 17, 17 − 3 = 14. Stack: 14

One value is left, so the expression equals 14. In infix it reads 5 + (1 + 2) × 4 - 3. This example is preloaded in the visualizer above, which shows the two operands lifting off the stack for every operator.

Operand order matters

Because the stack returns the most recent value first, the first pop is the right-hand operand. For + and * the order makes no difference, but for -, /, % and ^ it does:

• 10 4 - is 10 − 4 = 6, not −6.
• 10 4 - 3 / is (10 − 4) / 3 = 2.
• 2 3 2 ^ ^ is 2^(3^2) = 512, while 2 3 ^ 2 ^ is (2^3)^2 = 64 — postfix spells the grouping out explicitly.

Detecting invalid expressions

• Not enough operands — 1 +: the operator finds fewer than two values on the stack (too many operators, or one too early).
• Too many operands — 1 2 3 +: two values, 1 and 5, remain at the end (too few operators).
• Division by zero — 8 0 /: the expression has no value.
• Unknown tokens — a variable such as x has no value to push.

A quick sanity check for binary operators: a valid postfix expression has exactly one more operand than operators, and while scanning from the left the operands seen always outnumber the operators seen.

Why postfix? Where it is used

Postfix needs no parentheses and no precedence rules, so a machine can evaluate it in one pass with one stack. That is exactly how stack machines work: Java bytecode, .NET CIL, WebAssembly, CPython bytecode, PostScript and Forth all push operands and let instructions pop them.

HP calculators made Reverse Polish notation famous, and compilers turn infix source into an expression tree or postfix-like code before generating instructions. To evaluate an ordinary infix expression yourself, convert it with the shunting-yard algorithm first, then run this evaluator.

Common mistakes

• Swapping the operands — computing b - a instead of a - b.
• Integer-division surprises: in Python 7 / 2 is 3.5. LeetCode 150 wants truncation toward zero, which is int(a / b), not a // b (that floors: -7 // 2 == -4).
• Splitting multi-digit numbers into characters — separate the tokens with spaces.
• Confusing a negative number such as -3 with the operator - followed by 3: decide how negatives are written and tokenize accordingly.
• Not checking that exactly one value remains at the end.

Prefix evaluation and interview variations

Prefix (Polish) expressions are evaluated the same way but scanned right to left, and then the first value popped is the left operand. - + 5 * + 1 2 4 3 also gives 14.

• Evaluate Reverse Polish Notation (LeetCode 150): this exact algorithm with integer division that truncates toward zero.
• Postfix to infix: push strings and build "(a op b)" for every operator.
• Expression trees: push leaf nodes and let each operator pop two subtrees.
• Basic Calculator: convert infix to postfix and evaluate it, or merge both passes with two stacks.

Time and space complexity

Postfix Evaluation in Python

import math

APPLY = {
    "+": lambda a, b: a + b,
    "-": lambda a, b: a - b,
    "*": lambda a, b: a * b,
    "/": lambda a, b: a / b,
    "%": math.fmod,  # sign of a, like C++ / Java / JS
    "^": math.pow,
}


def evaluate(tokens):
    """tokens like ["5", "1", "2", "+", "4", "*", "+", "3", "-"]."""
    stack = []
    for t in tokens:
        if t not in APPLY:            # t is a number
            stack.append(float(t))
        else:                         # t is an operator
            if len(stack) < 2:
                raise ValueError("missing operand for " + t)
            b = stack.pop()           # right operand (pushed last)
            a = stack.pop()           # left operand
            stack.append(APPLY[t](a, b))
    result = stack.pop()
    if stack:
        raise ValueError("too many operands")  # the stack must now be empty
    return result


# evaluate("5 1 2 + 4 * + 3 -".split())  -> 14.0

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• Infix to Postfix ConverterConvert infix to postfix step by step with the shunting-yard algorithm: see the operator stack, precedence and associativity, and the output after every token.
• Balanced Parentheses CheckerCheck if parentheses are balanced and watch the stack algorithm step by step: push each opener, match each closer, catch crossed or unclosed brackets in O(n).
• Stack VisualizerInteractive stack visualizer: watch push, pop and peek move the top pointer of an array stack, see overflow and underflow happen, and learn why each is O(1).
• Stack & Queue VisualizerStack and queue visualizer: animate push, pop, enqueue and dequeue, compare LIFO with FIFO, and step through circular queues, deques and stack applications.