# 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

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)