  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Postfix to Prefix Conversion

Last Updated on September 15, 2022 by Gokul Kannan ### Problem statement

Given an arithmetic expression in postfix notation , convert it into the equivalent prefix notation.

Sample example :

Postfix input : ab*

Prefix output : *ab

### 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 most used to notation for evaluating arithmetic expression

• 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

### Approach

For converting Postfix to Prefix we use a stack . The stack helps us store 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 prefix expression .

### Algorithm

1. Scan all symbols one by one from left to right in the given prefix expression .

2. If the reading symbol is an operand , push it into the stack .

3. If the reading symbol is an operator , then a. Pop two expression from the stack , operand1 and operand2 , which is operand for the current operator b. Push operator + operand2 + operand1 into the stack

4. If there is no symbol left then stop the process . Top of the stack will have the required infix expression .

NOTE : ‘+’ denotes the concatenation of strings .

### Postfix to Prefix conversion example with dry run ### Implementation

```#include <bits/stdc++.h>
using namespace std;

bool isOperand(char ch){
return (ch>='a' && ch<='z') || (ch>='A' && ch <='Z');
}

string postfixToPrefix(string postfix) {
stack<string> st;

int len = postfix.size();
for (int i = 0; i < len; i++) {
if(isOperand(postfix[i])){

st.push(string(1,postfix[i]));

}
else{
string operand1=st.top();
st.pop();

string operand2=st.top();
st.pop();

st.push( string(1,postfix[i]) + operand2 + operand1);
}
}
return st.top();
}

int main() {