Prefix to Postfix Conversion

by · June 8, 2020

“Prefix to postfix conversion” is a classic example of  stack data structure. Stack can be used to convert given prefix expression to corresponding postfix 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 for Prefix to Postfix Conversion are as follows:

  1. Scan the prefix string in reverse order.
  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 the stack, namely, temp1 and temp2, then push

temp1 temp2 operator  into stack.

  1. Repeat steps from 3 to 4 until all the characters of the strings are scanned.
  2. Lastly, single postfix string will be left in stack, pop it and return it.

Example

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

  • Prefix to Postfix Conversion
    Prefix to Postfix Conversion

Algorithm for Prefix to Postfix Conversion

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

C++ Program for Prefix to Postfix Conversion

/* Program for Prefix to Postfix 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()
        {
            if(top==-1)
            {
                cout<<"stack underflow!!";
                return "abc";
            }
            string temp;
            temp=item[top];
            top--;
            return temp;
        }
};
int main(int argc, char** argv)
 {
     int i;
    string prefix;
    stack st;
    cout<<"Enter valid prefix expression: ";
    cin>>prefix;
    for(i=prefix.size()-1;i>=0;i--)
    {
        if(prefix[i]=='+' || prefix[i]=='-' || prefix[i]=='*' || prefix[i]=='/' || prefix[i]=='^')
        {
            string op1,op2,temp;
            op1=st.pop();
            op2=st.pop();
            temp=op1+op2+prefix[i];
            st.push(temp);
        }
        else
        {
            string flag;
            flag=flag+prefix[i];
            st.push(flag);
        }
    }
    cout<<"The equivalent postfix expression: "<<st.pop();
    return 0;
}


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

Related Posts:

  1. Prefix to Infix Conversion
  2. Infix to Postfix Conversion
  3. Infix to Prefix Conversion
  4. Postfix to Infix Conversion
  5. Postfix to Prefix Conversion
  6. Check whether given Parentheses String are Balanced Parentheses or Not.
  7. Next Greater Element
  8. Delete Alternate Nodes of the Linked List.
  9. Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.
  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...