A-level Computing 2009/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.
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.
Q: Write the infix expression x + y in Reverse Polish notation
Q: Write the infix expression (x - y)*7 in RPN
Q: Write the RPN expression x 2 ↑ in infix form
Q: Write the RPN expression x y + x y - * in infix form
x y + 3 /
(6 + x)*(4 + y)