Header Ads Widget

Trending

6/recent/ticker-posts

convert infix to postfix expression

 Program to Convert Infix to Postfix Expression

Infix expressions are human-readable but it is Time consuming for machines to read. That's why we need to convert infix to postfix expression. Before going to convert infix to postfix expression we need to understand infix and postfix expressions.

What is Infix Expression?

Infix expression consists of Operators between operands. An expression is called Infix Expression if the operators are included between the operands and easily calculated by humans.

Example of Infix Expression

  • A+B+C+D
  • (A*B)+C+D
  • 1*(2+9)+8-(2+4^6)

What is Postfix Expression?

Postfix expression is the notation in which operators are placed after the operands. This notation is easily evaluated and understood by computers.


Example of Postfix Expression

  • AB+C+D+
  • AB*C+D+
  • ABC*EF-/+

Infix to postfix precedence rules

Here is the precedence and associativity of operators in the conversion of Infix to postfix expression. Here is the table representing operator precedence and associativity in C.

Precedence & Associativity    

Operator type Operators Associativity
Unary +,-,*,&,++,!,~ Right to Left
Multiplicative /,*,% Left to Right
Brackets (),[],{},-> Left to Right
Relational <<,>>,<,> Left to Right
Equality = =,!= Left to Right
Bitwise XOR & Left to Right
Bitwise AND ^ Left to Right


Rules to Convert Infix to Post Expression

To convert infix to postfix expression using stack use the following rules:

  1. Read all Characters from left to right in the given Arithmetic expression.
  2. If you get Operand then print it as it is.
  3. If the character is operator or parenthesis then push it into the stack.
  4. If you get an operator then check for the precedence of the operator.
  5. If reading characters have lower precedence over the characters in Stack, then pop out those characters and then push this into the stack.

 Precedence of Operators 

Operator type    Precedence 
ExponentiationHigh
Divide and MultiplicationMedium
Addition & SubtractionLow
NOTHigh
ANDMedium
ORLow

Let us see the code for converting infix expression to postfix expression in different programming languages.



Conversion of Infix to Postfix expression using Stack

Here is Algorithm to convert infix to postfix expression in Java and C++.

 Infix to postfix conversion in C++


#include<bits/stdc++.h>
using namespace std;

//Function to check precedence and associativity
int value(char c)
{
  if(c == '^')
        return 4;
    else if(c == '/')
        return 3;
    else if(c=='*')
        return 2;
    else if(c == '+' || c == '-')
        return 1;
    else
        return 0;

}
void infipost(string s)
{

    string postfix="";
    stack <char> st;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='('st.push(s[i]);

       else if((s[i]>='a' && s[i]<='z') ||(s[i]>='A' && s[i]<='Z') || (s[i]>='0' && s[i]<='9'))
        {
            postfix=postfix+s[i];

        }

        else if((s[i]=='/' || s[i]=='*' || s[i]=='+'||s[i]=='-' ||s[i]=='^') &&(st.size()==0))
        {
        st.push(s[i]);

        }

       else if(s[i]=='/' || s[i]=='*' || s[i]=='+'||s[i]=='-' ||s[i]=='^')
        {



            while(value(s[i])<=value(st.top()))
            {
                postfix=postfix+st.top();
                st.pop();
            }

             st.push(s[i]);


        }
       else if(s[i]==')')
        {

            while(st.top()!='(')
            {
                postfix=postfix+st.top();
                st.pop();

            }
            st.pop();


        }


    }

    cout<<"PostFix Expression is : "<<postfix<<endl;

}




int main ()
{
string s="(P/Q+(R-T)*U)";
     infipost(s);

return 0;
}


infix to postfix expression


Infix to postfix conversion in Java


import java.util.*;  
    
public class infixToPostfix  
{  
static Stack operators = new Stack();    


public static void main(String argv[]) 
{  
String infix="(P/Q+(R-T)*U)";

System.out.println("Postfix expression is :" + postfix(infix));  
}  


private static String postfix(String infix)  
 
{  
char symbol;  
String postfix = "";  
for(int i=0;i<infix.length();++i)  
{  
symbol = infix.charAt(i);  
if (Character.isLetter(symbol))  
postfix = postfix + symbol;  
else if (symbol=='(')  

{  
operators.push(symbol);  
}  
else if (symbol==')')  
  
{  
while (operators.peek() != '(')  
{  
postfix = postfix + operators.pop();  
}  
operators.pop();        
}  
else  
 
{  
while (!operators.isEmpty() && !(operators.peek()=='(') && pre(symbol) <= pre(operators.peek()))  
postfix = postfix + operators.pop();  
operators.push(symbol);  
}  
}  
while (!operators.isEmpty())  
postfix = postfix + operators.pop();  
return postfix;  
}  


static int precedence(char x)  
{  
            if(c == '^')
        return 4;
    else if(c == '/')
        return 3;
    else if(c=='*')
        return 2;
    else if(c == '+' || c == '-')
        return 1;
    else
        return 0;

}  
 


OutPut :

Postfix Expression is : P Q / R T - U * +




Solution of Infix to Postfix expression only at courpedia.com

Practice this Problem at Leetcode - Infix to postfix