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 ...
So that we can ...
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 ... - + 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?
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. 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.
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.
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.
Here are some more activities related to RPN. Enjoy.
END OF TOPIC ASSESSMENT |