Reverse Polish Notation, or Postfix Notation, is a different way of writing mathematical expressions from the Infix Notation you are used to. It is called Polish because of a Polish mathematician named Jan ukasiewicz, but where he put mathematical operators before their operands (Prefix Notation), Reverse Polish puts them after.

How Reverse Polish Works

You are used to placing operators between their operands, as in 4 + 2, which of course evaluates to 6. In Reverse Polish, however, the same expression would be written as 4 2 +. This looks strange at first, but youll soon get used to it.

If you want a longer expression, such as 3 + 4 + 2, you write it 3 4 + 2 +, and solve as follows:

3 4 + 2 +

7 2 +

9

Interestingly enough, the same expression can be written as 3 4 2 + +. To solve, you find the leftmost operator, apply it to the previous two operands, and repeat. This is, of course, due to the associative property

of addition.

3 4 2 + +

3 6 +

9

Though it may not be obvious to you, this completely removes the need for parentheses and order of operations. The expression (3 + 2) x (7 - 5), which evaluates to 10 with parentheses but 12 without, is written as 3 2 + 7 5 - x in RPN.

3 2 + 7 5 - x

5 7 5 - x

5 2 x

10

A Little Context

Starting in 1968 until 1977, Hewlett-Packards calculators were entirely based on Reverse Polish Notation, in a time when calculators were expensive and important pieces of equipment. To this day, they still make RPN calculators, though they are perhaps not as popular as they once were. Interestingly, RPN calculators require no = button, as the calculator computes an answer as soon as it sees any mathematical operator.

But Why?

Why would HP choose to make RPN calculators? Because they are so easy to implement using a stack. Consider the following algorithm, written in pseudocode, taken from Wikipedia.

for each token in the postfix expression:

if token is an operator:

operand_2 pop from the stack

operand_1 pop from the stack

result evaluate token with operand_1 and operand_2

push result back onto the stack

else if token is an operand:

push token onto the stack

result pop from the stack

Now, traditionally this was done with an array-style stack, of fixed height, because it was so simple, but we can use a linked-stack with no worries.

The Actual Project

You will implement an RPN calculator, using a stack, which takes its input either from the command line or a user inputted string, with each token (operators and operands) separated by spaces. It will print the results to the console, and must work with +, -, x and /. You choose the programming language.