# Postfix to Prefix Conversion

“** Postfix to Prefix Conversion**” is a classic example of stack data structure. Stacks can be used to convert given postfix expression to corresponding prefix expression.

**Operator**: Operator are symbols that instruct the computer to perform simple and single tasks. Examples of operators includes + (Addition), – (Subtraction), * (multiplication),… and many more.

**Operand**: Operands are values or variable on which operator works its tasks. Examples of Operand includes “a”, “b”, 23, 12,.. and many more.

**Steps to convert Postfix to Prefix Expression **

**Scan the string from left to right.****Initialize an empty string stack.****If the scanned character is operand, push it into stack.****Else if the scanned character is operator, pop two strings from stack, namely, temp1 and temp2, and push**__operator temp2 temp2__into stack.

**Repeat steps from 3 to 4 until all the characters of the strings are scanned.****In the last only a single valid prefix string will be in the stack, pop it and return it.**

**Example**

Suppose, we want to convert the following postfix expression to prefix expression:

**Algorithm for converting postfix expression to prefix expression**

Algo postfix_2_prefix (postfix) { // input- valid postfix expression //output- equivalent prefix expression 1. Createstack (stack). 2. i=0 3. loop(i<sizeof(postfix)) { a.if postfix[i] is an operator { operand2=popstack(). operand1=popstack(). temp= concatenate postfix[i]+ operand1 + operand2 . pushstack (temp). } b.else if postfix[i] is an operand Then push postfix[i] into stack. c.Increment i with 1. } 4. prefix= popstack(). 5. Return prefix. }// END OF ALGO.

**C++ Program for converting postfix expression to prefix expression**

#include <iostream> #include<string> #define sizes 100 using namespace std; class stack { string item[sizes]; int top; public: stack() { top=-1; } void push(string str) { if(top==sizes-1) { cout<<"stack overflow!!"; return; } top++; item[top]=str; } string pop() { string temp; if(top==-1) { cout<<"stack underflow!!"; return "abc"; } temp= item[top]; top--; return temp; } }; int main(int argc, char** argv) { stack st; string postfix; int i; cout<<"Enter the valid postfix string:\n"; cin>>postfix; for(i=0;i<postfix.size();i++) { if(postfix[i]=='+' || postfix[i]=='-' || postfix[i]=='*' || postfix[i]=='/' || postfix[i]=='^') { string op1,op2,temp; op2=st.pop(); op1=st.pop(); temp=postfix[i]+op1+op2; st.push(temp); } else { string flag; flag=flag+postfix[i]; st.push(flag); } } cout<<"The equivalent prefix expression:\n"<<st.pop(); return 0; }

Enter valid postfix expression: abc*de-/+ The equivalent prefix expression: +a/*bc-deOUTPUT:

**Related Posts:**

**Infix to Postfix Conversion****Infix to Prefix Conversion****Prefix to Infix Conversion****Prefix to Postfix Conversion****Postfix to Infix Conversion****Check whether given Parentheses String are Balanced Parentheses or Not.****Next Greater Element****Find Minimum number of bracket reversals required to make an expression balanced.****Implement Queue Using Two Stacks.****Merge Overlapping Intervals using Stacks****Implement Stack Using Linked List****Largest Rectangular Area in Histogram****Length of Longest Valid Substring****Reverse a String using Stack****Implement two stacks in a single array****Print Bracket Number****Next Greater Frequency Element****Sort a Stack using Temporary Stack****Program to check Palindromic Anagram.****Program to print all the Palindromic Substring of the String.**