Infix, Postfix, and Prefix Conversion

Introduction

Understanding different notations for expressing mathematical expressions is fundamental in computer science and mathematics. Infix, postfix, and prefix notations each have their unique ways of representing expressions, influencing how they are evaluated and processed in algorithms and programming languages. In this blog, we will discuss about Infix, Postfix, and Prefix Conversion.

What is infix?

The typical mathematical form of expression that we encounter generally is known as infix notation. In infix form, an operator is written in between two operands.

Example:

An expression in the form of A * ( B + C ) / D is in infix form. This expression can be simply decoded as: “Add B and C, then multiply the result by A, and then divide it by D for the final answer.”

Advantages of Infix Expressions

Familiarity: Infix notation is the standard mathematical notation used in textbooks and everyday arithmetic, making it intuitive and easy to understand for most people.
Ease of Input: Infix notation requires fewer parentheses compared to prefix or postfix notations, making it more convenient for human input and manual calculation.
Operator Precedence: Infix notation naturally adheres to the conventional operator precedence rules, making it straightforward to interpret expressions without explicit instructions.

Disadvantages of Infix Expressions

Complex Parsing: Infix expressions often require complex parsing algorithms to properly evaluate them, especially when dealing with operator precedence and parentheses.
Ambiguity: Infix notation can be ambiguous when expressions involve multiple operators of the same precedence level, necessitating the use of parentheses to clarify the intended order of operations.
Evaluation Complexity: Converting infix expressions to a form suitable for evaluation, such as postfix or prefix notation, typically involves additional steps and can introduce complexity, especially in algorithmic implementations.

What is Prefix?

In prefix expression, an operator is written before its operands. This notation is also known as “Polish notation”.

Example :

The above expression can be written in the prefix form as / * A + B C D. This type of expression cannot be simply decoded as infix expressions.

Advantages of Prefix Expressions

Uniformity: Prefix notation, also known as Polish notation, offers a uniform way to represent mathematical expressions, where operators precede their operands. This uniformity simplifies parsing and evaluation algorithms.
No Parentheses: Unlike infix notation, prefix expressions do not require parentheses to indicate the order of operations. The operator precedence is inherent in the notation, reducing ambiguity and making expressions more concise.
Ease of Evaluation: Prefix expressions can be evaluated efficiently using stack-based algorithms, where operators are applied to their operands as soon as they are encountered, simplifying the evaluation process.

Disadvantages of Prefix Expressions

Non-Intuitive: Prefix notation may not be as intuitive as infix notation for humans, as it requires understanding and memorization of the order of operators and operands.
Readability: Prefix expressions can become hard to read and understand, especially when expressions involve complex arithmetic or multiple nested operators.
Conversion Overhead: Converting infix expressions to prefix notation and vice versa can introduce additional overhead and complexity, especially in algorithms and programs where expression manipulation is required.

What is Postfix?

In postfix expression, an operator is written after its operands. This notation is also known as “Reverse Polish notation”.

Example :

The above expression can be written in the postfix form as A B C + * D /. This type of expression cannot be simply decoded as infix expressions.

Refer to the table below to understand these expressions with some examples:

Infix	Prefix	Postfix
A+B	+AB	AB+
A+B-C	-+ABC	AB+C-
(A+B)*C-D	-*+ABCD	AB+C*D-

Prefix and postfix notions are methods of writing mathematical expressions without parentheses. Let’s see the infix, postfix and prefix conversion.

Advantages of Postfix Expressions

Simplified Evaluation: Postfix notation eliminates the need for parentheses and operator precedence rules, simplifying expression evaluation and making it more efficient.
Ease of Parsing: Postfix expressions have a straightforward structure where operators immediately follow their operands, making them easier to parse and evaluate using stack-based algorithms.
Reduced Ambiguity: Postfix notation reduces ambiguity in expressions by explicitly specifying the order of operations, eliminating the need for parentheses to clarify the intended evaluation order.

Disadvantages of Postfix Expressions

Non-Intuitive for Humans: Postfix notation can be less intuitive for humans compared to infix notation, requiring familiarity with the concept of Reverse Polish Notation (RPN) for understanding and manipulation.
Conversion Overhead: Converting infix expressions to postfix notation and vice versa may introduce additional complexity and overhead, especially in algorithms and programs where expression manipulation is required.
Readability Challenges: Postfix expressions can become difficult to read and understand, particularly in complex expressions or when multiple operators are involved, affecting code maintainability and readability.

Convert Infix expression to Postfix expression

In infix expressions, the operator precedence is implicit unless we use parentheses. Therefore, we must define the operator precedence inside the algorithm for the infix to postfix conversion.

The order of precedence of some common operators is as follows:

Note: For detailed information on the order of precedence, you can check out C Operator Precedence.

Points to consider:

The order of the numbers or operands remains unchanged. But the order of the operators gets changed in the conversion.
Stacks are used for converting an infix expression to a postfix expression. The stack that we use in the algorithm will change the order of operators from infix to Postfix.
Postfix expressions do not contain parentheses.

Algorithm:

Create a stack.
For each character c in the input stream:

If c is an operand 
{
Output c 
}
Else if c is a right parentheses 
{
Pop and output tokens until a left parentheses is popped  
}
Else
{          // c is an operator or left parentheses
Pop and output tokens until one of the lower priorities than c 
are encountered, or a left parentheses is encountered, or the stack is empty.
Push c
}

Pop and output tokens until the stack is empty.

For a better understanding, let’s trace out an example: A * B- (C + D) + E

Input Character	Operations on Stack	Stack	Postfix Expression
A		Empty	A
*	Push	*	A
B		*	AB
-	Check and Push	-	AB*
(	Push	-(	AB*
C		-(	AB*C
+	Check and Push	-(+	AB*C
D			AB*CD
)	Pop and Append to Postfix till ‘(’	-	AB*CD+
+	Check and Push	+	AB*CD+-
E		+	AB*CD+-E
End	Pop till Empty		*ABCD+-E+**

Implementation of the above algorithm:

C++

#include<bits/stdc++.h>

using namespace std;




//precedence of operators

int precedence(char ch) 

{

if(ch == '^')

 return 3;

else if(ch == '/' || ch =='*')

 return 2;

else if(ch == '+' || ch == '-')

 return 1;

else

 return -1;

}





string infixToPostfix(string s) 

{

    stack<char> st;

string postfix_exp;




for(int i = 0; i < s.length(); i++) 

    {

 char ch = s[i];




 // If the input character is  an operand, add it to the postfix output string. 

if((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9'))

 postfix_exp += ch;



 // If the input character is an '(', push it to the stack.

 else if(ch == '(')

 st.push('(');




 // If the input character is an ')', pop and output string from the stack until an '(' is encountered.

 else if(ch == ')') {

 while(st.top() != '(')

 {

  postfix_exp += st.top();

  st.pop();

 }

 st.pop();

 }




 //If the character is an operator

 else 

        {

 while(!st.empty() && precedence(s[i]) <= precedence(st.top())) 

            {

  postfix_exp += st.top();

  st.pop();

 }

 st.push(ch);

 }}




// Pop all the remaining elements from the stack

while(!st.empty()) 

    {

 postfix_exp += st.top();

 st.pop();

}




return postfix_exp;

}




int main() 

{

string infix_expression = "A*B-(C+D)+E";

cout<<"The postfix string is: "<<infixToPostfix(infix_expression);

return 0;

}

You can also try this code with Online C++ Compiler

Run Code

Output:

The postfix string is: AB*CD+-E+

You can check out Coding Ninjas Studio for more in-depth information on Infix To Postfix Conversion.

Convert Prefix expression to Postfix expression

Converting a prefix expression to a postfix expression is almost the same as the above conversions. The one difference is that we’ll use stack to store operands this time.

Algorithm:

Reverse the prefix string.
Create a stack.
For each character c in the input stream:

If c is an operand 
{
Push it in the stack 
}
Else
{          // c is an operator
Pop two tokens(operand) from the stack. Concatenate the operands and the operator, as (operand 1 + operand 2 + operator). And push this string back in the stack 
            }

Note: This string will now act as an operand.

Repeat until the stack is empty or the input string ends.

For a better understanding, let’s trace out an example: * + A B – C D

Reversed String: D C – B A + *

Input Character	Operation on Stack	Stack-1(Postfix)
D	Push	D
C	Push	D C
–	Concatenate and Push	(CD-)
B	Push	(CD-) B
A	Push	(CD-) B A
+	Concatenate and Push	(CD-) (AB+)
*	Concatenate and Push	(AB+) (CD-) *
End	Final Output:	AB+CD-*

Note: parentheses are only used to represent the string after concatenation.

Implementation of the above algorithm:

C++

#include <bits/stdc++.h>

using namespace std;




// To check if character is operator or not

bool check_op(char x)

{

if(x =='+'|| x== '-'|| x== '/'|| x=='*')

 return true;

else

        return false;

}




// Convert prefix to Postfix expression

string prefixToPostfix(string str)

{

    reverse(str.begin(), str.end());

stack<string> s;

int length = str.size();




    for (int i = 0; i <length; i++)

{

 if (check_op(str[i]))

 {

 string op1 = s.top();

 s.pop();

 string op2 = s.top();

 s.pop();




 string temp = op1 + op2 + str[i];




 s.push(temp);

 }




 else 

        {




 s.push(string(1, str[i]));

 }

}




return s.top();

}




// Driver Code

int main()

{

string str1 = "*+AB-CD";

string str = prefixToPostfix(str1);

cout<<"The postfix string is: "<<str<<endl;

return 0;

}

You can also try this code with Online C++ Compiler

Run Code

Output:

The postfix string is: AB+CD-*

After reading so far, don’t forget to try your hands on the problems based on infix, postfix and prefix conversions provided by Coding Ninjas Studio.

Comparison of Infix, Prefix and Postfix Expressions

Aspect	Infix Notation	Prefix Notation (Prefix)	Postfix Notation (RPN)
Operand Placement	Between Operators	Before Operators	After Operators
Operator Placement	Between Operands	Before Operands	After Operands
Parentheses Usage	Often required for clarity	Not required	Not required
Evaluation Complexity	Complex parsing algorithms	Simplified parsing algorithms	Simplified parsing algorithms
Human Readability	Intuitive for humans	Less intuitive for humans	Less intuitive for humans
Evaluation Efficiency	Requires operator precedence evaluation	Requires operator precedence evaluation	Efficient stack-based evaluation
Conversion Complexity	Moderate	Moderate	Moderate
Example	(2 + 3) * 4	* + 2 3 4	2 3 + 4 *

Frequently Asked Questions

What is infix to postfix?

In infix to postfix conversion, infix expressions are transformed into postfix notation, where operators follow their operands without parentheses, facilitating efficient evaluation algorithms.

What is infix to prefix?

In infix to prefix conversion, infix expressions are transformed into prefix notation, where operators precede their operands, simplifying parsing and evaluation algorithms.

What is postfix in data structure?

Postfix, also known as Reverse Polish Notation (RPN), is a notation in which each operator follows its operands. It's used in data structures and algorithms for efficient expression evaluation, particularly with stack-based algorithms.

Why are parentheses not required in postfix and prefix expressions?

Parenthesis is not required because the order of the operators in the postfix and prefix expressions determines the actual order of operations in evaluating the expression.

Which data structure is used in infix, postfix and prefix conversion?

Stack is used in infix, postfix and prefix conversion.

Is postfix the reverse of Prefix?

A postfix expression is merely the reverse of the prefix expression.

Conclusion

Complex expressions written in ordinary parenthesized infix notation are generally easier to read than their postfix and prefix equivalents. But, we convert those parenthesized expressions to these notations for computer processing. This article explained all those notations and how to change one notation to another.

Questions based on infix, postfix and prefix conversions are prevalent in interviews. So, you can practise it using the algorithms provided in this article. For more such questions, you can check out an interview preparation course offered by Coding Ninjas.

You can also consider our Online Coding Courses such as the DSA in Python, C++ DSA Course, DSA in Java Course to give your career an edge over others.

Happy Learning!