Reverse Polish

Reverse polish notation (otherwise known as post-fix, RPN for short) is a way of representing mathematical expressions. The notation is used because the format that the expression is in is easier for machines to interpret rather than the notation we are used to, infix notation, where the operator is in between the numbers. The equation can be complex or simple. RPN doesn't require brackets as the equations are laid out in such a format that they aren't required for machines to understand.

There is no inherent reason why operators should be written between the operands, as they are with the standard arithmetic operators. The operators could come before the operands (prefix), between (infix), or after (postfix). Here is the same expression written in three formats:

Prefix notation	Infix notation	Postfix notation
× 3 4	3 × 4	3 4 ×

We are used to seeing arithmetic written infix and functions written in prefix notation, often with brackets (e.g. sqrt(9) to express the operation of taking a square root). We could write arithmetic in the same form, such as using Python's operator library:

>>> import operator
>>> operator.add(operator.mul(3, 4), 2)
14

Advantages of postfix notation

Neither prefix nor postfix notation require brackets to express grouping of operations: the order of evaluation is dictated solely by the order of operations.

Infix notation can only easily express operations that take one or two parameters (such as binary addition or square roots). Operations that take more than two parameters require typographic embellishments such as brackets.

Equivalent equations

PostFix	Infix	Answer
3 4 +	3 + 4	7
5 6 + 3 *	(5 + 6) * 3	33
2 4 / 5 6 - *	(2/4)*(5-6)	-0.5
2 3 ↑	2³	8

Extension:Stack-based programming languages Some programming languages, called stack-based programming languages, use the model of stack-based evaluation throughout. The most well-known stack-based languages are PostScript and Forth.

Evaluation of Reverse Polish expressions

Expressions stated in reverse Polish notation can be simply evaluated using a stack. As the expression is read, values are pushed onto the stack. When an operation is read, values are popped from the stack and the result pushed back on the stack. The result left on the stack is the overall value of the expression.

The use of a stack and uniform precedence rules makes it very easy to write code to calculate the results of reverse polish expressions.

An example of how a stack can be used to compute reverse Polish notation.

Example

Using a slightly more complex example than above, evaluation of "3 4 × 10 2 ÷ +" can proceed as follows:

Unread input	Stack	Comment
3 4 × 10 2 ÷ +	_	Stack is empty at the start of the evaluation
4 × 10 2 ÷ +	3	Value 3 is pushed
× 10 2 ÷ +	4 3	Value 4 is pushed
10 2 ÷ +	12	× operator pops two items off the stack, multiplies them, and pushes the result back on the stack
2 ÷ +	10 12	Value 10 is pushed
÷ +	2 10 12	Value 2 is pushed
+	5 12	÷ operator pops two items off the stack, divides one by the other, and pushes the result back on the stack
	17	+ operator pops two items off the stack, adds them, and pushes the result back on the stack

The result left on the stack, 17, is the overall value of the expression.

Practice Questions

Exercise: Infix to RPN Conversion Convert x + y into RPN. Answer: x y + Convert (x + y)*z into RPN. Answer: x y + z * Convert 3 / (5 + y * x) into RPN. Answer: 3 5 y x * + /

Exercise: RPN to Infix Conversion Convert x y * into infix. Answer: x * y Convert 5 y + z x 3 - * / into infix. Answer: (5 + y) / (z * (x - 3))

YouTube Video Example

A video example can be seen here from Computerphile on Youtube: https://www.youtube.com/watch?v=7ha78yWRDlE