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

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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
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[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)