Last Updated on April 25, 2023 by Prepbytes
We have been given an arithmetic expression, and we have to write a program that converts prefix to postfix. The expression is given in the form of a string that contains alphabets i.e az or AZ denotes operands and operators are ( +, β, *, / ). In short, we have to program a prefix to postfix converter.
Here are some examples, that will give you a clear understanding of what is exactly meant by prefix to postfix conversion.
Example 1:
Input: a/bc/ade Output: abc/ad/e
Example 2:
Input: ab Output: ab
Before discussing the solution of the prefix to postfix. Let us first discuss arithmetic notations in brief.
Introduction to Arithmetic Notations
Any arithmetic expression consists of operands and operators . The way we arrange our operators and operands to write the arithmetic expression is called Notation .
There are three different notations for writing the Arithmetic expression :

Infix Expression An expression is said to be in infix notation if the operators in the expression are placed in between the operands on which the operator works. For Example,
a + b * c
Infix expressions are easy to read ,write and understand by humans , but not by computer. Itβs costly , in terms of time and space , to process Infix expressions

Postfix Expression (Reverse Polish Notation) An expression is said to be in postfix notation if the operators in the expression are placed after the operands on which the operator works. For Example,
abc*+
Itβs the most used notation for evaluating arithmetic expressions

Prefix Expression (or Polish Notation ) An expression is said to be in prefix notation if the operators in the expression are placed before the operands on which the operator works. For Example,
+a*bc
Precedence Order and Associativity of Operators
The precedence order of operators is given in the below table.
Precedence  Type  Operators  Associativity 
1  Postfix  () [] > . ++ —  Left to Right 
2  Unary  + – ! ~ ++ — (type)* & sizeof  Right to Left 
3  Multiplicative  * / %  Left to Right 
4  Additive  + –  Left to Right 
5  Shift  <<, >>  Left to Right 
6  Relational  < <= > >=  Left to Right 
7  Equality  == !=  Left to Right 
8  Bitwise AND  &  Left to Right 
9  Bitwise XOR  ^  Left to Right 
10  Bitwise OR    Left to Right 
11  Logical AND  &&  Left to Right 
12  Logical OR    Left to Right 
13  Conditional  ?:  Right to Left 
14  Assignment  = += + *= /= %= >>= <<= &= ^= =  Right to Left 
15  Comma  ,  Left to Right 
In this article, we are going to see how we can convert prefix to postfix expressions. For simplicity and understanding purposes, we will consider only β+β, ββ, β/β, β*β, β(β and β)β.
Prefix to Postfix Conversion
To convert a prefix to postfix expression, we will use a stack to hold the operands. Whenever an operator is found, we pop two operands from the stack and push a new operand. The final element at the top of the stack will be our postfix expression.
Algorithm for Prefix to Postfix Converter
Here is the stepwise algorithm to convert prefix to postfix expressions.
 Step 1: Scan all symbols one by one from right to left in the given prefix expression.
 Step 2: If the reading symbol is an operand, push it into the stack.
 Step 3: If the reading symbol is an operator, then
 a. Pop two expressions from the stack, operand1, and operand2, which is the operand for the current operator
 b. Push operand1 + operand2 + operator into the stack
 Step 4: If there is no symbol left then stop the process. The top of the stack will have the required postfix expression.
NOTE : β+β denotes the concatenation of strings .
Dry Run for Prefix to Postfix Conversion
Code Implementation of Prefix to Postfix Converter
Here is the code to perform prefix to postfix conversion in C++.
#include <bits/stdc++.h> using namespace std; bool isOperand(char ch){ return (ch>='a' && ch<='z')  (ch>='A' && ch <='Z'); } string prefixToPostfix(string prefix) { stack<string> st; int len = prefix.size(); for (int i = len  1; i >= 0; i) { if(isOperand(prefix[i])){ st.push(string(1,prefix[i])); } else{ string operand1=st.top(); st.pop(); string operand2=st.top(); st.pop(); st.push( operand1 + operand2 + string(1,prefix[i])); } } return st.top(); } int main() { string prefix="*a/bc/ade"; string postfix=prefixToPostfix(prefix); cout<<"Prefix expression : "<<prefix<<endl; cout<<"Postfix expression : "<<postfix<<endl; return 0; }
Output:
Prefix expression : *a/bc/ade
Postfix expression : abc/ad/e*
Time Complexity: O(n), where n is the length of the input string in prefix notation
Space Complexity: O(n), since we are using a stack.
Conclusion In this article, we discussed the approach for prefix to postfix conversion. We have used a stack to code out prefix to postfix converter. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE  Competitive Programming at PrepBytes.
Frequently Asked Questions(FAQs)
Here are some frequently asked questions related to prefix to postfix conversion.
Ques 1. What is the difference between prefix and postfix evaluation? Ans. Prefix evaluation involves evaluating a prefix expression from right to left, while postfix evaluation involves evaluating a postfix expression from left to right.
Ques 2. What is Reverse Polish Notation? Ans. Reverse Polish Notation is another name for postfix expression.
Ques 3. What are the advantages of the stackbased approach to prefix to postfix conversion? Ans. The stackbased approach for the prefix to postfix is simple, efficient, and easy to implement. It can handle any expression and does not require any additional data structures.