Infix to Prefix Conversion

by · June 8, 2020

“Infix to prefix conversion” is a classic example of  stack data structure. Stack can be used to convert given infix 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 for infix to prefix conversion:

  1. Scan the valid infix expression from right to left. 
  2. Initialize the empty character stack and empty prefix string.
  3. If the scanned character is an operand, add it to prefix string.
  4. If the scanned character is closing parenthesis, push it to the stack.
  5. If the scanned character is opening parenthesis, pop all the characters of the stack and concatenate to the end of the prefix string until closing parenthesis occurs.
  6. Pop the closing parenthesis.
  7. If the scanned character is an Operator and the stack is not empty, compare the precedence of the character with the element on top of the stack. If top element of the Stack has higher precedence over the scanned character, pop the stack else push the scanned character to stack. Repeat this step until the stack is not empty and top Stack has precedence over the character.
  8. Repeat steps 3 to 7 until all characters are scanned.
  9. If the stack is empty, reverse and return the prefix string.
  10. Else, pop the elements of the stack and add it to prefix string, and then reverse and return the prefix string. 

Example:

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

Algorithm for converting infix to prefix expression:

Algo infix_to_prefix (infix)
{
// input – valid infix expression.
// output- corresponding prefix expression.
1.    i= sizeof(infix)-1;
2.    Loop(i>=0)
    {
    1.If(infix[i] == ‘)’ )
       Then push infix[i] into stack.
    2.Else if(infix[i] == ‘(‘ )
    {
        a.Token = popstack();
        b.Loop (Token! = ‘)’ )
        {
        Concatenate Token to prefix string.
        Token = popstack ();
           }
                  }
    3.Else if(infix[i] is an operator)
    {
        Ch=peep ();
        Loop (stack not empty AND Priority (infix[i]) <priority (Ch)) 
        {    
            Ch=popstack ();
            Concatenate ch to prefix string
                Ch=peep ();
                       }
        push infix[i] into stack.
    }
    4.Else if(infix[i] is an operand)
        Then push infix[i] into stack.
    }
3.    Loop(stack not empty)
    {
    Ch=popstack ();
    Concatenate ch to prefix string.
    }
4.    Print the prefix string in reverse order.
}// End.

C++ Program for converting infix to prefix expression

/* C++ Program to convert infix to prefix expression */
#include<iostream>
#include<string>
using namespace std;
class stack
{
    string item;
    int top;
    public:
        stack()
        {
            top=-1;
        }
        void push(char ch)
        {
            top++;
            item[top]=ch;
        }
        char pop()
        {        
            char ele;
            if(isempty())
            {
                printf("\n stack overflow!!");
                return '@';
            }
            ele=item[top];
            top--;
            return ele;
        }
        char peep()
        {
            return(item[top]);
        }
        int isempty()
        {
            if(top==-1)
            return 1;
            return 0;
        }
        int priority(char ch)
        {        
            if(ch==')')
                return 1;
            else if(ch=='+' || ch=='-')
                return 2;
            else if(ch=='*' || ch=='/')
                return 3;
            else 
                return 4;
        }
};
int main()
{
    string infix,prefix;
    char ch,ch2,token,temp;
    int i,j=0,len;
    stack st;
    cout<<"Enter valid infix expression: ";
    cin>>infix;
    len=infix.size();
    for(i=len-1;i>=0;i--)
    {
        token=infix[i];
        if(token==')')
            st.push(token);
        else if(token=='(')
        {
            ch=st.pop();
            while(ch!=')')
            {
                prefix.push_back(ch);
                ch=st.pop();
            }
        }
        else if(token=='+' || token=='-' || token=='*' || token=='/' || token=='^')
        {
            ch2=st.peep();
            while(!st.isempty() && st.priority(token)<st.priority(ch2))
            {
                ch=st.pop();
                prefix.push_back(ch);
                ch2=st.peep();
            }
            st.push(token);
        }
        else
            st.push(token);
    }
    while(!st.isempty())
    {
        ch=st.pop();
        prefix.push_back(ch);
    }
    cout<<"\n The Corresponding Prefix Expression: ";
       for(j = prefix.size() - 1;j>=0;j--)
       {
           cout<<prefix[j];
    }
     return 0;
}


OUTPUT:
Enter valid infix expression: (a+(b*c)/(d-e))
The corresponding Prefix Expression: +a/*bc-de

Related Posts:

  1. Infix to Postfix Conversion
  2. Prefix to Infix Conversion
  3. Prefix to Postfix 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. Find Minimum number of bracket reversals required to make an expression balanced.
  9. Implement Queue Using Two Stacks.
  10. Detect a Loop in a Linked List.
  11. Find the Length of the Loop present in the Linked List.
  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...