Reverse Polish Notation

Reverse Polish Notation

One of the most popular pages on mathblog is the infix to postfix converter. When I realized that –  I decided it was worth diving a little more into what postfix or Reverse Polish Notation as it is better known is. Reverse Polish Notation is a mathematical notation which is functioning very well in a stack based implementation. In Reverse Polish Notation the operators follow their operands, in contrast to Polish Notation, in which operators precede their operands. One of the main benefits of Reverse Polish Notation is the fact that it does not rely on parentheses to evaluate the expression – as long as each operator has a  fixed number of operands.

In normal (also known as infix notation) an expression can be written like

3 + 4

In reverse polish notation, the operators follow the operands. Therefore, the same expression would be written as

3 4 +

In case of the infix expression

3 + 4 * 5

We have the order of the operators which state that we should multiply first. The same expression in Reverse Polish Notation would become.

3 4 5 * +

But why use reverse polish notation?

Tests have shown that reverse polish notation leads to faster calculations by humans operating a calculator for two reasons. There is no need for using parenthesis and therefore the user have fewer things to type, which is most likely also the reason for it being faster. Rather than a lower cognitive load which was first indicated. The second reason for it’s superiority is that it leads to fewer errors from the fact that the user has to write down fewer intermediate results. In general it seems that postfix notation is more difficult to learn compared to infix notation. But there is no firm evidence for it.

Postfix evaluation algorithm

The postfix notation is as mentioned rather efficient if we implement it using a stack.

Let us take the example (3 + 4) * (5 – 2). In Reverse Polish notation this would be expressed as

3 4 + 5 2 – *

To evaluate this expression we would do the following

  1. Push 3 to the stack
  2. Push 4 to the stack
  3. Pop the first two numbers from the stack (3, 4) and add them together and put the result back on the stack. The stack now contains the number 7
  4. Push 5 to the stack
  5. Push 2 to the stack. The stack now contains (7, 5, 2) if read from the bottom.
  6. Pop 5 and 2 from the stack and apply the – operator and push the resulting number 3 to the stack.
  7. Pop 3 and 7 from the stack and apply the multiplication operator and put the resulting 21 back on the stack.

The algorithm can be generalized as

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

Of course we can add unary operators such as the factorial. Then the algorithm would look like

<span data-mce-type="bookmark" style="display: inline-block; width: 0px; overflow: hidden; line-height: 0;" class="mce_SELRES_start"></span>
for each token in the postfix expression:
  if token is an binary 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 unary operator:
    operand_1 ← pop from the stack
    result ← evaluate token with operand_1
    push result back onto the stack
  else if token is an operand:
    push token onto the stack
result ← pop from the stack

The latter algorithm shows that it is paramount to the algorithm that each operator always have the same number of operands in them.

History of Reverse Polish Notation

Reverse Polish Notation have been developed several times throughout history. It was first proposed by by Arthur Burks, Don Warren and Jesse Wright in 1954. Charles Hambling did a lot of work with Reverse Polish Notation and is often called the inventor of the notation. He was the first person to show the merit and advantages of the notation when writing programs for the processing on programmable computers and algorithms to make it happen.

As you can see none of the inventors were Polish. The polish part comes from Jan Łukasiewicz who invented the Polish Notation (or prefix notation) in 1924 who showed that by writing operators in front of their operands, instead of between them, brackets were made unnecessary.

The first computers to implement architectures enabling reverse Polish notation were the English Electric Company’s KDF9 machine and the American Burroughs B5000 in the 1960s. The real popularization of the notation came with the HP calculators in 1970s and 1980s. The first version being the 9100A Desktop Calculator. And later in the very famous HP-35 and not least the financial calculator HP-12C, which have reach cult status.

 

Posted by Kristian

1 comment

Muhammad Naveed

solve 7+(8*4)/2 infix expression using stack

Leave a Reply