Difficulty: Beginner | Easy | Normal | Challenging
- Some understanding of a stack (guide HERE)
Infix: The notation commonly used in mathematical formulae
Operand: The value on which an operator is performed
Operator: A symbol like minus that shows an operation
Postfix: A mathematical notation in which operators follow operands
Prefix: A mathematical notation in which operands follow operators
Reverse Polish Notation (RPN): A mathematical notation in which operators follow operands
Infix, Postfix and Prefix?
We are going to work through the basics here before we touch on
Reverse Polish Notation in detail.
Infix notation is seen a the “normal” way to create mathematical formulae. We can take a simple addition sum:
2 + 3
and name the parts of the formulae as follows:
We can see that the
Operator is sandwiched in between the
Operands for the
This is true for any mathematical formulae which uses
2 + 3
5 — 2
2 + 3 + 4
2 + 5 / 2
1 + 2 / 3
Of course, when we mix
Operands we have a precedence (that is, order of operations)issue. Which
Operator should be used first?
Yes, you can use brackets for this, but people typically use BODMAS as a system (guide HERE). This order of precedence is usually coded in computer language compilers (or at least one would hope).
Prefix notation puts the operator before all of the operands. This means that the precedence is always clear. We are going to compare the
Infix notation to this
So in an example of 2 + 3 as
Infix notation we can convert this to
The Prefix Example of 2+3
Infix: 2 + 3
this can be written with a circle where we put the
operator in a blue section:
Which is then followed by the
so to derive the
prefix equivalent we simply take the
operator then move from left to right reading off the
operands in left-to-right order.
Prefix: + 2 3
This gets a little bit tricky when we have multiple
operators in our formuale.
The Prefix Example of 2+3+4
Infix: 2 + 3 + 4
this can be represented as two of the RPN circles
Once again the same rules apply. However we move from the outer circle to the inner circle.
Prefix: + 2 + 3 4
The secret here being that each operator takes the two expressions that immediately follow it.
this is really the thing — each
operand needs to receive two fully formed
Postfix OR Reverse Polish Notation
Postfix notation puts the operator before all of the operands.
This is just like the
prefix notation, but the
operand comes at the end of the expression, and similarly removes the need for brackets within any expressions.
It is called Polish due to the nationality of Jan Łukasiewicz who invented the notation.
The same ideas as above applies. We still have the
operand at the top of the circle, but this time that goes at the end of the operators
Infix: 2 + 3
Postfix: 2 3 +
So we take the bottom two
operand first from left-to-right then append the
operator at the end.
Similarly when we have two expressions we have to remember the
operators to append to the end.
Infix: 2 + 3 + 4
Postfix: 2 3 4 + +
infix is not the only possible way to develop expressions, although it is quite easy for people to understand. Computers are likely to use a stack to evaluate expressions — and therefore
Reverse Polish Notation is often used as it is a great way to simply evaluate an expression using a stack (read more about this in the extend your knowledge section below).
Just remember — Polish here isn’t anything to do with cleaning. But it is much to do with coding.
The Twitter contact:
Any questions? You can get in touch with me here