A calculator has to read 3 + 4 * 2 and decide what happens first. That takes precedence rules, and parentheses to override them, and a parser that knows both.

There’s another way to write the same expression that needs none of that. Put each operator after its two operands:

3 4 2 * +

No precedence or parenthesis. The order you read it in is the order it happens in, and one simple machine can evaluate anything written this way.

That machine is a stack.

The rules

Read left to right, one token at a time:

  • A number? Push it onto the stack.
  • An operator? Pop two values, apply the operator, push the result.

When you run out of tokens, the answer is the single value left on the stack.

That’s the whole algorithm. Two rules.

Try it

Type an expression and step through it. Watch what the stack holds after each token — the presets at the bottom are the problems from the worksheet.

Two things worth noticing while you play:

Operators always take the top two values, in the order they’re sitting there. The second-from-top is the left operand. For + and * that doesn’t matter. For - and / it decides everything.

Watch how deep the stack gets. Some expressions never hold more than two values. Others hold seven. In real life the stack depth cannot be infinite!

Evaluate these

Work them out on paper first, then check with the machine above.

Question

3 7 +

10

Question

12 4 -

8

Order matters here. The stack holds 12 then 4, so - computes 12 − 4, not 4 − 12.

Question

10 3 2 + +

15

Both operators come at the end, so all three numbers are on the stack before any arithmetic happens. Stack depth reaches 3.

Question

10 2 / 5 2 + +

12

The stack goes: 10 → 10, 2 → 5 → 5, 5 → 5, 5, 2 → 5, 7 → 12.

Notice the 5 from 10 2 / just sits at the bottom, waiting, while 5 2 + is computed on top of it.

Question

9 8 7 6 5 4 3 - - - - - -

Before you compute it: how deep does the stack get?

6, and the stack gets 7 deep — every operand is pushed before a single operator runs.

It unwinds from the inside out: 9 − (8 − (7 − (6 − (5 − (4 − 3))))).

In algebraic notation you’d need six sets of parentheses to say that. Here you need none.

Question

12 4 2 + / 8 * 10 - 3 2 + /

6/5, or 1.2.

Read these as algebra

The stack doesn’t care whether it’s holding numbers. Same two rules.

Question

3 x x * *

3x²

x x * builds x · x first, then the 3 waiting underneath multiplies into it.

Question

4 x x * * 3 x * + 1 -

4x² + 3x − 1

Question

12 x * 3 y * + 5 x * 2 y * - /

(12x + 3y) / (5x − 2y)

Watch this one in the machine. The entire numerator is built and then parked at the bottom of the stack while the whole denominator gets assembled on top of it. The / doesn’t fire until both halves are finished.

The parentheses in the answer aren’t in the RPN anywhere — they only appear when you translate back into algebra.

Now go the other way

Convert each of these to RPN. Check your answer by pasting it into the machine.

Question

(3 + 4) * (2 + 3)

3 4 + 2 3 + * → 35

Question

1 + 2 + 3 + 4

1 2 + 3 + 4 + → 10

1 2 + 3 4 + + also works and also gives 10. Addition doesn’t care how you group it, so both are fine. Compare that to the next problem.

Question

5 - 4 - 3 - 2

5 4 - 3 - 2 - → −4

Only one right answer this time. Subtraction groups left to right, so this means ((5 − 4) − 3) − 2.

If you wrote 5 4 - 3 2 - - you got 0 instead, because that means (5 − 4) − (3 − 2). Both are valid RPN. Only one is the expression we asked for.

Question

1 / (1 + 2)

1 1 2 + / → 1/3

The first 1 gets pushed and then waits through the entire 1 2 + before the division happens.

Question

1 / (1 + (1 / (1 + 1 / (1 + 1))))

1 1 1 1 1 1 1 + / + / + / → 3/5

Build it from the inside out:

piece RPN
1 + 1 1 1 +
1 / (1+1) 1 1 1 + /
1 + 1/(1+1) 1 1 1 1 + / +
1 / (1 + 1/(1+1)) 1 1 1 1 1 + / + /
1 + (that) 1 1 1 1 1 1 + / + / +
1 / (that) 1 1 1 1 1 1 1 + / + / + /

Seven 1s and six operators — which is exactly the check below.