Infix, Postfix, Prefix and Reverse Polish Notation

Before, after or in.

A simple application for a Stack in a computer application, but also a very important one in Computer Science too!

Difficulty: Beginner | Easy | Normal | Challenging

Prerequisites:

  • Some understanding of a stack (guide HERE)

Terminology

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

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:

Image for post
Image for post

We can see that the Operator is sandwiched in between the Operands for the Infix notation.

This is true for any mathematical formulae which uses Infix notation:

2 + 3

5 — 2

and

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

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

So in an example of 2 + 3 as Infix notation we can convert this to prefix notation

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:

Image for post
Image for post

Which is then followed by the operands

Image for post
Image for post

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

Image for post
Image for post

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.

Image for post
Image for post

this is really the thing — each operand needs to receive two fully formed prefix expressions.

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 +
Image for post
Image for post

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.

Image for post
Image for post
Infix: 2 + 3 + 4
Postfix: 2 3 4 + +

Conclusion:

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.

Extend your knowledge

  • You can (if you choose) read Apple’s documents HERE
  • You can read about evaluating RNP with Stacks HERE

The Twitter contact:

Any questions? You can get in touch with me here

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store