CS36 : Witaj!


The way we do maths is not the way that computers do it. In this topic, I'll change the way you think ...

We are learning ...
  • About RPN
So that we can ...
  • Understand why RPN is better. Just better.
  • Convert simple infix expressions into RPN (postfix) and vice versa

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.

Activity 1 Isn't that how we do maths anyway? (80)

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 ...


Task 1.1
Evaluating expressions
Brain

Evaluate ... 3+4*5
  • You should get the answer 23
  • Why don't you get the answer 35?
  • What system do we use to make sure we carry out operations in the correct order?
Evaluate ... (3+(4*5))-(8/(2+2))
  • Compare your answer to one of the other students in the class. Do you all agree? Is there any chance that the answer could be different?
  • What do we use the brackets for?
OUTCOMENothing written, just a discussion


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

- + 3 * 4 5 / 8 + 2 2
Prefix

(3+(4*5))–(8/(2+2))
Infix

3 4 5 * + 8 2 2 + / -
Postfix

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.

This is the true power of prefix and postfix

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.

Task 1.2
RPN Questions
Nothing
  1. To convert degrees Fahrenheit into degrees Celcius, we usually use the infix expression ...

    (F-32)*(5/9)

    Convert this into a postfix expression thereby removing the need for the brackets.

  2. Match the following infix expressions to their postfix equivalent.  You may wish to print out the popup, stick it in your notebook and answer it there!

    https://drive.google.com/file/d/0B83yXMOilskaTXpCbGxPbXVPLTQ/view?usp=drive_web

  3. Convert these infix expressions to postfix (RPN) :

    a) 36 + 4 * 3
    b) (36 + 4) * 3
    c) 5 + ((1 + 2) * 4) - 3
    d) 5 + (1 + 2 * 4) - 3
    e) x + y
    f) (x + y) / 2 
    g) (x + y) * (x – 16) 
    h) x * y
    i)  x + y * 6

  4. Convert these postfix expressions (RPN) to infix expressions :

    a) x y + x y - /
    b) 2 x * 3 y * + 8 /
    c) x y + 2 ^ 12 x - *

  5. Why are brackets NOT required in reverse polish notation?
OUTCOME : Beautifully presented answers to all the questions!


The important fact is that ...

Computers 'do maths' using postfix and always have.

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.

https://en.wikipedia.org/wiki/HP-35

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.


Activity 2 How do computers actually carry out postfix calculations? (75)

First, read the poem in the resources called 'Jack learns the facts about stacks and queues' ...


What has this got to do with RPN? Well, computers use a data structure called a stack to evaluate postfix expressions as shown in the lovely gif.

'Push' and 'Pop' represent the stack operations of adding and removing items from the top. In practice, the evaluations are carried out using subroutines with the operands as parameters.

Task 2.1
RPN Evaluation using a stack
Brain
Paper / Book

Evaluate the following RPN expressions using a stack to trace the operation.
  • 8 4 + 3 /
  • 45 9 * 8 1 - +
  • 212 32 - 5 * 9 /
The last exercise is a Fahrenheit to Celsius conversion - without brackets

OUTCOME : Document your work using a stack frame and explanation as per the lovely gif.


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


Extension Activities 

Here are some more activities related to RPN. Enjoy.
  • Consider the popup ...

    https://drive.google.com/file/d/0B83yXMOilskaOG1pa0RvQTdweXc/view?usp=drive_web

    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.

What's next?

Before you hand your book in for checking, make sure you have completed all the work required and that your book is tidy and organised. Your book will be checked to make sure it is complete and you will be given a spicy grade for effort.

END OF TOPIC ASSESSMENT