Now we need to learn about Hsilop (reverse polish of course!!). Polish notation is a mathematical notation introduced in 1920 by the Polish mathematician Jan Łukasiewicz but, during the development of computer systems, various computer scientists developed Reverse Polish Notation, or simply RPN ...


RPN↗ is a mathematical notation wherein every operator follows all of its operands. It is also known as postfix notation and is written parenthesis-free i.e. take out the brackets.

We (humans / mathematicians) normally use infix notation when we write down mathematical expressions.


This notation is called infix because the operator is inbetween the operands. If we wrote the operator before the operands, this would be called prefix, or Polish Notation ...


... and finally, with the operator after the operands, we get postfix or Reverse Polish Notation ...



We can represent the previous expression in three ways ...


Even though the prefix and postfix notation may look confusing, what is missing from both expression? That's right - the brackets! There are no precedence rules required with either prefix or postfix notation. The operands are evaluated in the order they are presented in the expression.


Having said that, prefix is a bit of a pig to write since you have to present the operator before the values which it has to work on which is a bit of a head mash. Postfix is logical. You present the operands first then the operator you wish to perform on them. Nice.

Why postfix?

• Calculations occur when operators are specified;
• The whole calculation is evaluated from the middle out;
• Brackets are unnecessary;
• Reflects the way in which calculations are done on paper;
• Easier for computers to evaluate;
• Operators are usually separated by a space (or some other character like a ‘,’);
• Programming language compilers usually convert infix to postfix anway.

The important fact is that ...


When you give a computer an infix expression to evaluate it first converts it to postfix and then carries it out.

Truly, RPN became popular in the 1970's with the advent of portable electronic calculators which replaced slide rules. They did not have the facility to use brackets and therefore if you were carrying out complex calculations, you would have to manually work out the precedence yourself.


You can still get digital and physical calculators which work in RPN. For instance, you can (and should) download a copy of 'Fairwood calculator' from their homepage↗ and try out the following exercises.

To remove any ambiguity in the process, here is an algorithm for your consumption ...

WHILE there are input tokens remaining in the expression:
  READ next unread token from LHS of expression
  IF token is a value:
    PUSH onto the stack
  ELSE (token must be an operator):
    POP 'n' values from the stack
    EVALUATE the operator with 'n' values as arguments
    PUSH the result onto the stack
POP last value from stack and return as result

There is no error handling in this algorithm; it works on the basis that the RPN expression is correctly formed. 

Task 2.2 The Postfix Evaluation Algorithm Flowchart software like yEd or Raptor Convert the postfix evaluation algorithm into a flowchart OUTCOME : A nicely formatted / drawn flowchart for your notes. Copy the algorithm into your notes as well, just in case the flowchart is confusing (which it shouldn't be).

Here are some more activities related to RPN. Enjoy.

• Consider the popup ...
  
  
  
  
  You may wish to practice some conversions using this method. Is it easier?
  
  
  
• Prefix like notation is used in function calls. For instance, if I wanted to create a function which adds two values together ...
  
  mathematical expression  : result = a + b
function call            : result = add(a,b)
prefix expression        : result = + a b
  
  ... or a more complicated example ...
  
  mathematical expression  : result = (3 * (a + b)) - 4
function call            : result = subtract(multiply(3,add(a,b)),4)
prefix expression        : result = - * 3 + a b 4
  
  Can you see the connection? Every time you perform a function call in programming, you are using prefix like notation. It is the 'retracing your steps' style of evaluation which makes prefix notation more difficult to understand than postfix. Prefix evaluation is often recursive since one expression may require another expression of the same type to be carried out first before it itself can be calculated.
  
  
• Edsgar Dijkstra developed an algorithm to convert an infix expression to a postfix expression which uses a queue data structure. It's called the Shunting yard algorithm↗ and you might want to investigate it online.