Infix to Postfix Conversion in C

Back to: Data Structures and Algorithms Tutorials

Infix to Postfix Conversion in C:

In this article, I will discuss Infix to Postfix Conversion in C with Examples using Stack. Please read our previous article discussing Expressions with Balanced Brackets using Stack in C. Here; we will learn what a postfix is, why we need a postfix, what precedence is, and how we convert an infix expression to a postfix expression, as well as a prefix (with pen and paper).

Types of Notations to Write an Expression:

There are three notations for writing an expression:

Infix Notation:

The first notation is the infix expression, commonly used in mathematics. So basically, we only know one notation, which is infix notation. In this notation, if there is a binary operator (+, -, *, /), the order of the operand and operator is: Operand Operator Operand, i.e., a + b. So, the operator will be in between two operands. This is the common method used in mathematics, but in computer science, apart from this, two more methods have been introduced: prefix and postfix.

Prefix Notation:

In prefix notation, the order of the operand and operator is: Operator Operand Operand, i.e., + a b. So here, the binary operator comes before the two operands, and the operation is performed on the following two operands.

Postfix Notation:

In postfix notation, the order of the operand and operator is: Operand Operand Operator, i.e., a b +. Here, two operands are written first, followed by the binary operator.

“a + b” means ‘a’ added with ‘b’. “+ a b” means add ‘a’ and ‘b’. “a b +” means ‘a’ and ‘b’ then add. We will learn how an expression with more operations will look like in prefix and postfix notation. Before that, let’s understand why we need prefix and postfix notations.

Why do we need prefix and postfix notations?

If we give you this expression and ask you to find the answer, you will evaluate it. For evaluation, what will you do? Will you first add 8 and 3? No, you all know the BODMAS rule. We assume that you all know the BODMAS rule. In mathematics, the higher precedence is for brackets and powers. So, let’s evaluate the above expression.

First, we have to solve (9-6), then 2², then division, multiplication, and finally, addition and subtraction.

The evaluation will be done in this order. If you observe the order in which we have performed those operations, we’re jumping here and there in this expression. We have to look into the expression and find out first which one we should perform next and then next, and so on. So, to find out which one should be performed next, we have to scan this whole expression. This means we have to scan this expression multiple times; otherwise, it’s randomly moving here and there in the expression. So, can we write a program that behaves like this or that will jump directly to a specific operation in the expression? This is a random behavior, so we can’t write a program for this.

If you write a program, then you have to make it search for the highest precedence first, i.e., brackets, then powers, then division, and so on. So, one by one, it has to scan the expression for each type of object. This is time-consuming. What we want is not to scan the expression multiple times. We want the result in just one scan. So, here it is not possible in infix notation. Then, is there any other notation by which it is possible? Yes, it is possible to use postfix notation. Let us write the postfix form of the above infix notation.

Evaluating a Postfix Expression:

This is a postfix expression. Don’t worry about how we’re converting infix to postfix. We’ll learn that. Now, let us evaluate this.

As you can see, the first four are operands, so ignore all of them and move ahead. Then, the first operator we found is the subtraction. So, we have to perform subtraction first. In the above infix expression, which operation did we evaluate first? Subtraction. So, we’re also performing subtraction here first. Here, we are also doing the same thing. So, this subtraction will be performed on the previous two operands, i.e., 9 and 6.

Assume that this underlined operation is performed. Now, move ahead. We have encountered a power operation, i.e., 2². So, the second operation we will perform is the power operation.

As you can see, the second operation we performed is the power operation in both the notations. Assume that power is performed in postfix. Let’s move ahead.

Here, we will perform the division operation as marked in the image above. The division will be performed on the previous two operands, which are the result of the power operation and the subtraction operation. Next is the multiplication. In infix notation, the division was the third operation. The operators in the postfix are arranged in the order in which they are supposed to be evaluated in the infix. So, that’s why whenever we come across an operator, we perform the operation on the previous two operands. If the expression is arranged in postfix form, it can be evaluated in just a single scan.

So, we can say that the purpose of writing an expression in postfix form is that we can scan the expression only once and perform all the operations. If it is in infix form, it’s not easy to evaluate it in one single scan. However, we have to learn how to write an infix-to-postfix expression.

How to convert an infix to a postfix expression?

Here, we have a precedence table. We’ve not taken all types of operators. We’ve taken just a few, namely, addition, subtraction, multiplication, division, and brackets.

Addition and subtraction have the lowest precedence, which is 1. Both have the same precedence in programming. In mathematics, subtraction has higher precedence than addition.

Multiplication and division also have the same precedence, which is 2, but they have higher precedence than addition and subtraction. Brackets have the highest precedence of all, which is 3.

Here, we have two expressions. Now, we will learn how to convert these from infix to prefix as well as postfix expressions. For conversion, remember that whenever you write an expression, you should fully parenthesize it. You should not write an expression without parentheses. Make this the first rule of conversion. These two expressions are not parenthesized. Actually, the compiler needs a fully parenthesized expression. No operator should be left open. When an expression isn’t parenthesized, the compiler will parenthesize it, not physically, but logically. How does the compiler parenthesize the expression? By using the precedence table. This is a very important concept.

What is Precedence?

Precedence doesn’t determine the order of execution. Suppose, in the above expression, multiplication is present, but that doesn’t mean that we perform multiplication first. What operation we’ll perform is a different thing. But that multiplication has the highest precedence, which means we put it inside the bracket first. Then, we parenthesize addition or subtraction. This is the purpose of precedence. So, precedence and associativity are meant to be parenthesized. Let’s parenthesize and then convert infix to postfix and prefix.

a + b * c

In this expression, multiplication has higher precedence. Here, c is multiplying with what? With b or a+b? c is multiplying with b only. So first, we will put b * c in the bracket.

a + (b * c)

Now, there is only one operator remaining, which is a plus operator. So, put that one in the bracket.

(a + (b * c))

This means that a will be added as a result of the multiplication of b and c. This is the parenthesized expression. Parenthesization gives you a clear-cut idea of what operation we should perform on which set of operands. The precedence table gives us the same idea. Now, let us first convert this parenthesized expression into a prefix expression.

Infix to Prefix conversion:

In prefix, first, we write operator then we write operands.

(a + (b * c))

For this expression, which bracket should be evaluated first? (b * c) should be evaluated first. For that, let’s convert that into a prefix.

(a + [ * b c ] )

Here, the square brackets represent that we have converted that expression into a prefix. Let’s also convert the outer round brackets into prefix.

+ a * b c

Prefix means first operator rather than operands. Here, operands are a and (*bc). So, we have written plus, then the right-hand side operand, and then the left-hand side operator. So, this is the prefix form of that expression. Let us take one more example.

a + b + c * d

First, let’s make it parenthesized.

(a + (b + (c * d ) ) )

Let’s evaluate this step by step.

=> (a + (b + [* c d ] ) )

=> ( [+ a b] + [* c d ] )

=> + + a b * c d

This is the prefix form of that expression. Here, we encounter the same precedence operators. So, in this situation, we don’t have to evaluate randomly or as per our wish. We have to evaluate left to right when we have the same precedence operators. Now, let us write the postfix form of these expressions.

Infix to Postfix conversion:

(a + (b * c))

First, we have to evaluate (b * c). let’s convert this into postfix form.

( a + [b c *] )

We have put this into the square bracket to show that this expression is converted. So, in postfix, we write operands first and then operators. We write b & c first and then *. Next, we have to evaluate the outer round bracket.

a b c * +

This is the postfix of that expression. Here, first, we write the left-hand operand, i.e., a, then the right-hand operand, i.e., b c *, and then the operator, i.e., +. Let us take another example.

a + b + c * d

Let’s evaluate this step by step.

=> a + b + [c d *]

Now, two plus operators are there, and they have the same precedence. Which one should we take first? Left-hand side plus operator.

=> [a b +] + [c d *]

Here, only the plus operator is left. So, evaluate this one as

=> a b + c d * +

This is the postfix notation of that expression.

Let us write the procedure in simple steps:

• Step 1: First, make the expression fully parenthesized based on the precedencies.
• Step 2: Evaluation starts with high precedence brackets.
• Step 3: Evaluate all the round brackets step by step.

Note: Prefix expression is not much used. Generally, we use postfix expressions.

Now, let us take an expression consisting of multiple different operators.

(a + b) * (c – d)

This expression is already parenthesized. Let’s convert this into prefix notation. Which bracket should be evaluated first? We have to start from left to right.

=> [+ a b] * (c –d)

Let’s evaluate the remaining bracket.

=> [+ a b] * [- c d]

Here, the multiplication operator is left.

=> * + a b – c d

This is the prefix notation. Here, first write the operator i.e. +, left-hand side operand i.e. + a b, and then right-hand side operand – c d. Now, let us write the postfix form of the same expression.

(a + b) * (c – d)

=> [a b +] * (c – d)

=> [a b +] * [c d -]

=> a b + c d – *

This is the postfix notation of the same expression. Here, first write the left-hand operand a b +, then the right-hand side operand c d -, and then the operator *. We hope these examples are sufficient for you to learn how to convert expressions from infix to prefix and postfix notations.

In the next article, I will discuss Associativity and Unary Operators in C. Here, in this article, I explain Infix to Postfix Conversion using Stack in C Language with Examples. I hope you enjoy this article on Infix to Postfix Conversion.