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.
Infix expressions[edit]
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)[edit]
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[edit]
Examples 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 |
Practice Questions[edit]
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) |