A-level Computing/AQA/Problem Solving, Programming, Operating Systems, Databases and Networking/Problem Solving/Reverse Polish notation

Reverse Polish notation is an alternative way of writing mathematical expressions.

Infix expressions

You will already be familiar with infix expressions where the operator is between two operands. E.g. 4 + 5 where the numbers 4 and 5 are the operands and + is the operator. The operators you will need to be familiar with are + (addition), - (subtraction), * (multiplication), / (division) and ↑(exponent).

When we write expressions in infix notation it can be confusing as to which operation should be performed first. For example, in the expression 4 + 5 * 6 we only know that the multiplication operation should be performed first because we have learnt the BIDMAS (or equivalent) rules. A computer does not automatically know this and would have to be programmed with the rules in order to carry out these operations correctly.

Reverse Polish notation (RPN)

RPN is a way of getting round this and provides a way to write expressions without the need for brackets. This makes it much easier for a computer to evaluate the expressions. RPN places the operator after the operands it is to operate on. E.g. 54 + 20 would be written as 54 20 + in RPN.

Examples

Examples Q: Write the infix expression x + y in Reverse Polish notation A: x y + Q: Write the infix expression (x - y)*7 in RPN A: x y - 7 * Q: Write the RPN expression x 2 ↑ in infix form A: x2 Q: Write the RPN expression x y + x y - * in infix form A: (x + y)*(x - y)

Practice Questions

Exercise: Convert from infix to RPN Write the infix expression (x + y)/3 in RPN Answer: x y + 3 /

Exercise: Convert from RPN to infix Write the RPN expression 6 x + 4 y + * as an infix expression Answer: (6 + x)*(4 + y)