Prefix to Infix Using Stack

by · June 8, 2020

“Prefix to Infix Using Stack” is a classic example of  stack data structure. Stack can be used to convert given prefix expression to corresponding infix 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 to convert Prefix to Infix Using Stack Expression are as follows:

  1. Scan the Prefix Expression form right to left.
  2. Initialize the 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 operator temp2) into stack.

  1. Repeat steps from 3 to 4 until we scanned all the characters.
  2. At the end, only infix string will be left into stack, pop and return it.

Example:

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

  • prefix to infix using stack
    Prefix to Infix Using Stack

Algorithm for converting Prefix to Infix Using Stack

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

C++ Program for converting Prefix to Infix Using Stack is as follows:

/* Program for converting Prefix to Infix Using Stack */
#include <iostream>
#include<string>
#define sizes 100
using namespace std;
class stack
{
    string item[sizes];
    int top;
    public:
        stack()
        {
            top=-1;
        }
        void push(string st)
        {
            if(top==sizes-1)
            {
                cout<<"stack overflow!!";
                return;
            }
            top++;
            item[top]=st;
        }
        string pop()
        {
            int i;
            string temp;
            if(top==-1)
            {
                cout<<"stack underflow!!\n";
                return "abc";
            }
            temp = item[top];
            top--;
            return temp;
        }
};
int main(int argc, char** argv)
 {
     int i;
     stack st;
    string prefix;
    cout<<"Enter valid prefix string: ";
    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+prefix[i]+op2+')';
            st.push(temp);
        }    
        else
        {
            string flag;
            flag=flag+prefix[i];
            st.push(flag);
        }
    }    
    cout<<"The resultant infix string is: "<<st.pop();
    return 0;
}

OUTPUT:
Enter valid Prefix String: +a/*bc-de
The resultant infix string: (a+((b*c)/(d-e)))

Related Posts:

  1. Prefix to Postfix Conversion
  2. Postfix to Infix Conversion
  3. Infix to Postfix Conversion
  4. Infix to Prefix Conversion
  5. Postfix to Prefix Conversion
  6. Check whether given Parentheses String are Balanced Parentheses or Not.
  7. Next Greater Element
  8. Bubble Sort on Linked List.
  9. Detect a Loop in a 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...