Introduction to Infix, Postfix and Prefix Expressions in Data Structures written by Nischal Lal Shrestha.
Image of Nischal who is author of the post.

By Nischal Lal Shrestha

On Thu 12 April 2018

Introduction to Infix, Postfix and Prefix Expressions in Data Structures

Infix Expressions

While writing an artihmetic expression using infix expression, the operator is placed in between the operands. Consider the sum of A and B. We think of applying + operator to the operand A and B i.e A+B. Here, We clearly know that B is added to A, since + operator is between them. This type of expressions are called infix expressions because operator is always in between the operands.

Although it is quite intimading for us to write every expressions in infix expression, the computers find it difficult to parse as the computer needs a lot of information(operator precedence and associativity rules, brackets which override these rules) to evaluate the expressions.

So, the computers work more efficiently with expressions written using prefix and postfix expressions.

Postfix Expressions

As the name suggests, when the operator is placed after the operands or we can say when the operator follows the operands, we get postfix expressions. They might seem akward on first appearance but they are not. It was developed by Jan Lukasiewicz who was a Polish logician, mathematician, and philosopher.

If an expression is written as (A+B)xC in infix expression, the same expression can be written as AB+Cx in postfix expression. The order of evaluation of postfix expression is always from left to right(forget about precedence).

Postfix Example: Evaluation of AB+Cx. As noted earlier, they are evaluated from left to right. So the addition operation is performed first and Multiplication is done.

Prefix Expressions

The only difference between postfix and prefix is the position of operator. In prefix expression the operator preceeds the two operands or we can say operator is placed before the operands.

If an expression is written as (A+B)xC in infix expression, the same expression can be written as x+ABC in prefix expression.

Prefix Example: Evaluation of x+ABC. Here +AB become the first operand for the x operator and C become the second operand. This is how the expression is evaluated.

Why do Computers Prefer Prefix and Postfix over infix?

If you look above examples where we convert infix expression to prefix and postfix something very intresting has happened. Where did the parentheses go? Why we need them in infix but not in prefix and postfix. The answer is that in postfix and prefix we exactly know which operator operates on which-which operand. Postfix and Prefix expressions are evaluated from left to right which means they are solely determined by the position. So there is no need of the parentheses. Since the Computers try to be lazy and choosing Prefix and Postfix over Infix gives the computer a chance to save execution time and memory. That is why they prefer prefix and postfix over infix.

Comments