We write 3 + 4 with the operator in the middle, and need brackets and precedence rules to make longer expressions unambiguous. Reverse Polish notation puts each operator after its operands, so an expression can be evaluated left to right with nothing but a stack. Learn to convert between infix and RPN and to evaluate RPN, showing the stack at every step.
In infix notation the operator is written between its operands (A + B). In Reverse Polish notation (RPN), also called postfix, the operator is written after its operands (A B +). RPN needs no brackets and no precedence rules: the order of the tokens fixes the order of the operations. It is evaluated left to right using a stack: push each operand; for each operator, pop two values, apply the operator and push the result. Compilers and interpreters convert expressions to RPN because this simple, unambiguous process is easy to turn into machine code.
Fig. 1: the expression tree for (A + B) * (C − D), its RPN form from a post-order traversal, and the stack before and after the final *
Section 01
Why Reverse Polish?
Infix expressions are easy for people but awkward for a translator: it has to look ahead, apply precedence (* and / before + and −) and match brackets. RPN removes all of that.
Infix
Reverse Polish
A + B
A B +
A + B * C
A B C * +
(A + B) * C
A B + C *
(A + B) * (C − D)
A B + C D − *
A − B − C
A B − C −
No brackets needed: compare rows 2 and 3. The brackets in infix change the RPN order instead.
Operands keep their order: A, B, C, D appear in the same left-to-right order in both forms; only the operators move.
One pass with a stack: the expression is read once, left to right, so evaluation is fast and simple to implement in machine code.
From a tree: draw the expression as a binary tree with operators at the nodes (Fig. 1). A post-order traversal (left subtree, right subtree, root) outputs the RPN.
Examiner trap
A − B − C means (A − B) − C, so its RPN is A B − C −. Writing A B C − − calculates A − (B − C), which gives a different answer.
Section 02
Evaluating with a stack.
Every RPN expression is evaluated with the same rule. In the lab, push and pop values on a stack and watch the top pointer move: evaluating RPN is just a sequence of these operations.
Read the tokens from left to right.
Operand: push its value onto the stack.
Operator: pop the top value (the right operand), pop the next value (the left operand), calculate left operator right, and push the result.
At the end, the single value left on the stack is the result.
Top ← 0
FOR Index ← 1 TO TokenCount
Token ← Tokens[Index]
IF Token = "+" OR Token = "-" OR Token = "*" OR Token = "/"
THEN
Right ← Stack[Top]
Left ← Stack[Top - 1]
Top ← Top - 1
CASE OF Token
"+" : Stack[Top] ← Left + Right
"-" : Stack[Top] ← Left - Right
"*" : Stack[Top] ← Left * Right
"/" : Stack[Top] ← Left / Right
ENDCASE
ELSE
Top ← Top + 1
Stack[Top] ← STR_TO_NUM(Token)
ENDIF
NEXT Index
OUTPUT Stack[Top]
Worked example Show the stack contents
Evaluate A B + C D − * when A = 6, B = 2, C = 7 and D = 3, showing the contents of the stack after each token.
Evaluate the RPN expression 5 3 2 * + 4 − and show the stack after each token.
5: stack 5. 3: stack 5, 3. 2: stack 5, 3, 2.
*: pop 2 and 3, 3 * 2 = 6. Stack: 5, 6.
+: pop 6 and 5, 5 + 6 = 11. Stack: 11.
4: stack 11, 4.
−: pop 4 and 11, 11 − 4 = 7. Stack: 7.
Answer: 7, which is the infix expression 5 + 3 * 2 − 4.
Examiner trap
With − and /, order matters. The first value popped is the right-hand operand. For 11 4 − the answer is 11 − 4 = 7, not 4 − 11.
Stage 1 · Learn
Check what the sim just showed you
Four quick checks. Each correct answer earns XP and records this skill on your profile.
Quick check+10 XP
What is the RPN form of (A + B) * C?
Quick check+10 XP
When evaluating RPN, what happens when an operator is read?
Quick check+10 XP
In the lab, which end of the stack do push and pop use?
Quick check+10 XP
Why does RPN need no brackets?
Section 03
Infix to RPN and back.
To convert infix to RPN by hand, apply the precedence rules (brackets first, then * and /, then + and −, equal precedence left to right) and write each operation as left operand, right operand, operator, working from the innermost operation outwards.
Worked example Convert to RPN
Convert (P − Q) / (R + S) * T to RPN, then evaluate it for P = 9, Q = 3, R = 1, S = 2, T = 5.
The brackets come first: P − Q becomes P Q −, and R + S becomes R S +.
/ and * have equal precedence, so work left to right: the division first. (P Q −) / (R S +) becomes P Q − R S + /.
Then multiply that result by T: P Q − R S + / T *.