evaluate-reverse-polish-notation

Difficulty: Medium  ·  Topic: Stack  ·  Practice it on parikshan: /practice/evaluate-reverse-polish-notation/start

The story

A team at PostgreSQL writes an internal expression-evaluator for a server-side function that compiles user-defined filters. The user submits a tree of arithmetic operations; the compiler emits a postfix sequence of tokens (operands and operators), and at runtime a tiny VM walks the sequence and computes the result. Postfix (Reverse Polish Notation, RPN) was chosen because it needs no parentheses, no precedence rules, and a single stack as its only data structure. The VM must be fast, correct, and trivially auditable for security review.

That is evaluate-reverse-polish-notation. It is the embryo of every interpreter, every spreadsheet formula engine, and every JIT's expression IR.

What's actually being asked

Given a list of n tokens, each either an integer literal or one of + - * /, evaluate the postfix expression. Division truncates toward zero (not floor). Output the single resulting integer.

Postfix means: operators come after their operands. 3 4 + means 3 + 4. 3 4 + 5 * means (3 + 4) * 5 = 35. There are no parentheses because the order of evaluation is unambiguous.

The naive approach

Convert RPN back to infix, then parse infix with precedence and parentheses. Comically over-engineered. The whole point of RPN is that it does not need parsing.

The key insight

A stack of operands. Walk left to right. For each token:

• If it is an integer, push it.
• If it is an operator, pop two operands, apply the operator, push the result. The order matters: the operand popped first is the right operand, the one popped second is the left.

At the end, the stack contains exactly one element: the result.

That is the entire algorithm. It is so short that the only interesting decisions are how to handle division (truncate toward zero, not floor) and how to make sure operand order is correct.

Operand-order subtlety

For a b -, the result is a - b, not b - a. So:

right = stack.pop()
left = stack.pop()
result = left - right   # for subtraction; analogous for division
push(result)

Addition and multiplication are commutative, so order does not matter for them. Subtraction and division are not; getting the order wrong is the most common bug on this problem.

Truncation versus floor

Python's // is floor division, which differs from C-style truncation on negative results: -7 // 2 == -4, but C's -7 / 2 == -3. The spec requires truncation toward zero. In Python use int(left / right) (with care) or int(operator.truediv(left, right)) or the formula -(-left // right) if (left < 0) != (right < 0) else left // right. The cleanest production approach: cast to a fixed-width signed integer and use the language's standard integer division if it truncates, otherwise compute int(left / right) carefully.

Step-by-step approach

1. stack = [].
2. For each token in input:
   • If token is one of + - * /:
     • right = stack.pop().
     • left = stack.pop().
     • Apply the operator (use truncation for division).
     • Push the result.
   • Else (it is an integer literal):
     • Push int(token).
3. Print stack[-1].

Worked example

tokens = ["2", "1", "+", "3", "*"]

This is (2 + 1) * 3 = 9.

Result: 9.

Another: tokens = ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]. Trace step by step and the result is 22. (Useful exam-warmup to do by hand once.)

Complexity

• Time: O(n), one pass.
• Space: O(n), the operand stack.

Common pitfalls

• Wrong operand order on - and /: the right operand is popped first. Writing left = pop(); right = pop() is the bug; the names mislead. Pop into right first.
• Using floor division for negative operands: -7 // 2 == -4 in Python, but the spec demands -3 (truncate toward zero). Use int(left / right) cautiously, or implement truncation explicitly.
• Treating negative literals as operators: a token like "-11" is an integer, not a subtraction. Parse tokens as ints when they are not in the operator set.
• Not validating the stack at the end: the spec guarantees well-formed input, but in production, asserting len(stack) == 1 at the end is a cheap correctness gate.
• Division by zero: the spec excludes it; in production code, check.

Where this shows up in the enterprise

• PostgreSQL / DuckDB / SQLite query executors: server-side expression evaluation uses stack-based VMs over postfix-like IR.
• Excel / Google Sheets / Smartsheet formula engines: every spreadsheet formula compiles to a postfix sequence executed by a stack VM.
• JavaScript V8, Java HotSpot, .NET CLR: interpreted bytecode includes operand stacks; same idea, larger instruction set.
• Forth, RPN-based scientific calculators (HP-12C, HP-48): literal RPN input.
• PostScript / PDF rendering: PostScript is a postfix language; rendering devices evaluate it with a stack.
• GraphQL / Trino / Presto query planners: predicate evaluation on a stack VM during scans.
• Cryptography (Bitcoin Script, Ethereum EVM): stack-based bytecode VMs. The EVM is essentially an RPN evaluator with a richer opcode set.
• Spreadsheet auditing tools (XL-Audit, Spreadsheet Detective): replay the postfix to detect calculation errors.

Stack VMs are the simplest, most auditable expression evaluators ever invented. The "stack discipline" makes correctness arguments and security review tractable.

Variants you'll see elsewhere

• basic-calculator and basic-calculator-ii: parse infix with +, -, *, / and parentheses, then evaluate. Often implemented as: shunting-yard to postfix, then this algorithm.
• decode-string: stack-based parser for nested encodings.
• evaluate-boolean-expression: same pattern for boolean operators.
• simplify-path: same pattern over directory components.
• tag-validator: stack of tag names.

How parikshan turns this into a learning loop

The dynamic private tests on parikshan cover:

• A single integer (no operators; the stack ends with one element, return it).
• All four operators in various orders to catch operand-order bugs.
• Negative literal operands (parse correctly as integers).
• Negative quotient with truncate-toward-zero semantics (-7 / 2 == -3, not -4).
• Deeply nested expression (stack depth approaches n / 2, tests memory).
• Large operand values (intermediate computation up to 64-bit).

If your code uses Python's //, the truncation test will fail. If your code uses int(left / right) for division you will likely pass, but it has its own edge case around floating-point precision for large integers; the safe formula is int(left / right) if abs(left) < 2**52 else (left // right if (left * right) >= 0 else -((-left) // right)). The parikshan AI sparring partner is the place, in practice mode, to explore these without burning integrity in exam mode.

In the AI-integrated workspace

When an agent generates a stack-based evaluator, your review checks:

1. Operand order: is the right operand popped first? Code reviews of agent output should always ask the agent to demonstrate "3", "1", "-" returns 2, not -2.
2. Truncation semantics: does the agent's division match the spec? Negative-divided tests catch this.
3. Token parsing: does the agent correctly distinguish operator "-" from negative literal "-11"?
4. Single-pass guarantee: no recursive descent, just a stack walk.

In production, a stack-based VM is one of the safest pieces of infrastructure you can build because the invariants are local and the state is one variable (a list). If an agent rewrites your evaluator using recursion or tree-building, push back: the postfix form already removes parsing complexity; reintroducing it is regression dressed as cleanup.

evaluate-reverse-polish-notation is where the stack metaphor becomes a computational tool, not just a matching device. The same six lines of logic underlie real interpreters. Treat the parikshan practice run as the moment that connection lands.