Infix, Prefix and Postfix notation

If you have been dealing with mathematical expressions, you might have heard of infix, prefix and postfix notation. If you have never heard of these kind of ways to write mathematical expressions, don’t be afraid. You already use one of them on a day-to-day basis. We’ll come back to which one later.
A short description of these kind of notations are as follows:

Infix, prefix and postfix notation are three equivalent ways of writing mathematical expressions. Despite being equivalent, they are expressed (written) in different ways.

If you already know the details, you can jump straight to the Java implementation.

Infix notation

We start off by describing infix notation, which in my opinion is the most easily understood notation of the three.
The infix notation is the notation you use in your daily life, whenever you want to write a mathematical expression / equation.  Let’s say you want to add a few numbers together, namely 2, 3 and 6. You would of course write it like this (I hope…):

Infix notation: 2 + 3 + 6

Another example of a mathematical expression with infix notation is:

Infix notation: 1 + 2 * 3⁴

This would also be evaluated the usual way. First, we take 3⁴ = 81, then 2 * 81 = 162, then 1 + 162 = 163. As you all see, this is the usual way of evaluating mathematical expressions. Note that 3⁴ is the equivalent of 3^4. This brings us to a formal definition of infix notation:

When using infix notation to write mathematical expressions, the operators (+, – etc..) are written between the operands.

Note that you can’t simply evaluate an infix expression from left to right – the normal rules for operator precedence applies. For example, in an equation without parentheses, we perform multiplication before addition – this is not new, and something we’re all familiar with.

 Prefix notation

When using prefix notation, the operators are written before their operands. The use of prefix notation is best described with an example. Assume you want to convert the infix expression 1 * ( 2 + 3 ) / 4 to prefix.

Infix notation: 1 * ( 2 + 3 ) / 4

Prefix notation: / * 1 + 2 3 4

So, how did we end up with this completely different expression? Let’s take it step by step. Note that when converting from infix to prefix, we read the expression from right to left, and use a stack to memorize the operands we have read. The basis for the algorithm is:

  • Reverse the infix expression.
  • If an operand is encountered, output it immediately.
  • An operator is encountered. Output all operators on the stack that has higher precedence than the operator read.
  • Reached end of equation, pop and output everything on the stack.

The step by step conversion of the equation above is described below. Remember that we start by outputting at the end of the prefix expression. In other words, the first operand we read will be the last operand in the prefix expression.

  • Reversing the infix expression: 4 /  ) 3 + 2 ( * 1
  • Reading ‘4’, immediately output 4. Output: 4, Stack: Empty
  • Reading ‘/’, pushing it to the stack. Output: 4, Stack: /
  • Reading ‘)’. Push it to the stack. Output: 4, Stack: ) /
  • Reading ‘3’. Immediately output. Output: 3 4, Stack: ) /
  • Reading ‘+’. Push it to the stack, since another a closing parenthesis hasn’t been read. Output: 3 4, Stack: + ) /
  • Reading ‘2’. Output: 2 3 4, Stack: + ) /
  • Reading ‘(‘. This is a closing parenthesis. Output every operator in between the parenthesis. Output: + 2 3 4, Stack: /
  • Reading ‘*’. Same precedence as the current on the stack. Push to stack. Output: + 2 3 4, Stack: * /
  • Reading ‘1’. Output: 1 + 2 3 4, Stack: * /
  • Reached the end of the equation. Output the rest on the stack. Result: / * 1 + 2 3 4

Postfix notation

With postfix notation, the operators are written after their operands. As with prefix, the use of postfix notation is also best described through an example. We continue with the same infix expression as above.

Infix notation: 1 * (2 + 3) / 4

Postfix notation: 1 2 3 + * 4 /

The basis for the algorithm to convert infix to postfix is:

  • Read the infix expression from left to right.
  • If an operand is encountered, output it immediately.
  • If an operator is encountered, there is two different scenarios. If the operator scanned has a higher precedence than the current operator on the stack, we push it to the stack. If the operator has lower precedence, we pop the stack until the current operator has less or equal precedence as the operator on top of the stack.
  • Reached end of equation, pop and output everything on the stack.

To be more concrete, the exact steps performed in the conversion from infix to postfix for the equation 1 * (2 + 3) / 4 is:

  • Reading ‘1’. Output: 1
  • Reading ‘*’. Pushing it to the stack. Output: 1, Stack: *
  • Reading ‘(‘. Pushing. Output: 1, Stack: * (
  • Reading ‘2’. Output: 1 2, Stack: * (
  • Reading ‘+’. Output: 1 2, Stack: * ( +
  • Reading ‘3’. Output: 1 2 3, Stack: * ( +
  • Reading ‘)’. Popping everything until ‘(‘ is encountered on the stack. Output: 1 2 3 +, Stack: *
  • Reading ‘/’. Same precedence as ‘*’. We pop the stack. Output: 1 2 3 + *, Stack: /
  • Reading ‘4’. Output: 1 2 3 + * 4, Stack: /
  • Reached the end of the equation, popping until the stack is empty. Result: 1 2 3 + * 4 /

Implementation in Java

No that we have gotten a basic understanding for what infix, prefix and postfix notation actually is, and how the algorithm to convert from infix to prefix / postfix works, it’s time to implement the algorithms in Java.

Tutorials will only get you so far..
If you wish to expand your Java skill-set and become an advanced Java developer, I personally recommend the Comprehensive Java Course by Edureka.
You can get 25% with the coupon code LIMITED25 😉

Leave a Reply

Your email address will not be published. Required fields are marked *