Infix to Postfix Conversion

Introduction

Depending on the position of operators and operands, there are three types of notations or ways of writing an expression containing operators, operands, and brackets - Infix Notation, Postfix Notation, and Prefix Notation. While infix notation is easier to read for us, postfix is easier to evaluate for a machine, such as in a calculator. This is because in a postfix operation operators are evaluated from left to right in a serial manner, which eliminates the need for brackets and omits any confusion regarding operator precedence. We will learn about them in more detail, in the upcoming sections.

What is Infix Notation?

Infix notation is the notation in which operators come between the required operands. It is the same as the arithmetic notation that we had learned in our school days.

Syntax of infix notation

The syntax of infix notation is X op Y.

Example - If we were to add two numbers 3 and 4, the operator that is '+' would come between the operands 3 and 4. So the infix notation will be 3 + 4.

Problem with infix notation

You might wonder, why do we need separate notations for writing expressions. Though infix notation is simple to read for us, it often brings with it some amount of ambiguity due to the following reasons- There are two main factors considered while evaluating an expression:

• Operator precedence - This refers to the priority given to each operator in an expression.
• Associativity - If two operators have the same precedence, associativity is used to determine the order of evaluation.

The only way that infix notation tackles the above factors is through the use of parenthesis.

Thus came the need to form notations that would not hold any ambiguity, eliminate the need for operator precedance and associativity rules, and would make the parsing of expressions much more simpler.

What is Postfix Expression?

Postfix Expression, also known as Reverse Polish Notation is the type of notation in which operator comes after the operand. For eg- If the infix expression is x + y, it's corresponding postfix notation is x y + . We will exlore in details the conversion of infix to postfix expressions.

Postfix expression is considered better than the infix expressions, as postfix expressions are easier to evaluate and also they don't have overhead of brackets.

Conversion of Infix to Postfix

It is important to know how to convert from one notation to the other. In this section we will go through the steps for converting infix to postfix. We will use a stack data structure for the above conversion. The expression we want to convert can contain operators, operands and also brackets ('('). We will consider all these while converting the expression.

Rules for the conversion from infix to postfix expression

Initially we have a infix expression given to us to convert to postfix notation. The infix notation is parsed from left to right, and then converted to postfix. Assume initially the postfix expression is empty, and we will fill the postfix expression out with the following steps:

1. If we have an opening parenthesis "(", we push it into the stack.

2. If we have an operand, we append it to our postfix expression.

3. If we have a closing parenthesis ")" we keep popping out elements from the top of the stack and append them to our postfix expression until we encounter an opening parenthesis. We pop out the left parenthesis without appending it.

4. If we encounter an operator:-

   4.1. If the operator has higher precedence than the one on top of the stack (We can compare ), we push it in the stack.

   4.2. If the operator has lower or equal precedence than the one on top of the stack, we keep popping out and appending it to the postfix expression.

5. When the last token of infix expression has been scanned, we pop the remaining elements from stack and append them to our postfix expression.*

Infix expression: K + L - M*N + (O^P) * W/U/V * T + Q

Let us dry run the above infix expression and find out its corresponding postfix expression.

The above string is parsed from left to right. For each token, the elements in the stack as well as the corresponding postfix expression up to that point is shown using the table below:

The final postfix expression is $K L + M N* - O P ^W * U / V / T * + Q+$

Explanation of the above table:

At step 1, since we have an operand (K), we are appending it our postfix operation. Then we encounter an operator(+), and check that our stack is empty. We push the operator in our stack. Next, we encounter another operand (L), and append it to our postfix operation. Now after step 3, our postfix expression contains KL, and stack contains +. The next element is (-), and we check that top of stack contains +, which holds equal precedence as (-). Thus we pop out (+), and append it our expression, which now looks like KL+. Since the stack is empty, (-) goes inside the stack. We continue this till the last element of our infix expression. To understand why an element is being added to the postfix expression or the stack, or popped out from the stack, refer to the rules for conversion discussed in the previous section.

Implementation of Infix to Postfix

Now let's go through the code for converting infix to postfix in some of the most commonly used languages.

How to convert infix to postfix in C++

How to convert infix to postfix in C

How to convert infix to postfix in Java

How to convert infix to postfix in Python

How to convert infix to postfix in JavaScript