Postfix to Prefix Conversion

by · June 8, 2020

“Postfix to Prefix Conversion” is a classic example of  stack data structure. Stack 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.

The Steps required to convert Postfix to Prefix Expression are as follows: 

  1. Scan the string from left to right.
  2. Initialize an empty string stack.
  3. If the scanned character is operand, push it into stack.
  4. Else if the scanned character is operator, pop two strings from stack, namely, temp1 and temp2, and push “operator temp1 temp2” into stack.
  1. Repeat steps from 3 to 4 until all the characters of the strings are scanned.
  2. 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:

  • Postfix to Prefix Conversion

Algorithm for Postfix to Prefix Conversion

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 Postfix to Prefix Conversion is as follows:

/* Program for Postfix to Prefix Conversion */
#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;
}


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

Related Posts:

  1. Infix to Postfix Conversion
  2. Infix to Prefix Conversion
  3. Prefix to Infix Conversion
  4. Prefix to Postfix Conversion
  5. Postfix to Infix Conversion
  6. Find First Repeating Element of an Array.
  7. Find Majority Element of an Array.
  8. Check whether given Parentheses String are Balanced Parentheses or Not.
  9. Next Greater Element
  10. Find Minimum number of bracket reversals required to make an expression balanced.
  11. Implement Queue Using Two Stacks.
  12. Merge Overlapping Intervals using Stacks
  13. Implement Stack Using Linked List
  14. Largest Rectangular Area in Histogram
  15. Length of Longest Valid Substring
  16. Reverse a String using Stack
  17. Implement two stacks in a single array
  18. Print Bracket Number
  19. Next Greater Frequency Element
  20. Sort a Stack using Temporary Stack

Tags:

You may also like...