Compilers: Run postfix code on a stack

Write the target machine of the tiny compiler: a stack that runs postfix code.

What to build

A program that evaluates an expression written in postfix (reverse Polish) notation.

Requirements

  • Tokens are whole numbers and the operators + - * /, separated by spaces.
  • Division is whole-number division rounded down (//). Print the result.

Input

One line of postfix tokens.

Output

One number.

Constraints

At most 50 tokens; the expression is valid; values stay below 10¹⁸.

Example

Input:

2 3 4 1 - * +

Output:

11

Why it works

In postfix, each operator comes after its operands, so a single stack evaluates it left to right: the same way a stack machine runs compiled code.

Examples

Example 1 · Input
2 3 4 1 - * +
Expected output
11
Example 2 · Input
7 2 -
Expected output
5

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

For a number, push it; for an operator, pop b, then a, and push a op b.

Hint 2

Use // for division; the inputs never divide by zero.

Solution

Show one correct solution (try it yourself first)
stack = []
for t in input().split():
    if t in "+-*/":
        b, a = stack.pop(), stack.pop()
        stack.append({"+": a + b, "-": a - b, "*": a * b, "/": a // b}[t])
    else:
        stack.append(int(t))
print(stack.pop())

Lesson: How a compiler works →