Infix to Postfix using Stacks

   
       
 Stack data structure can be used to convert an Infix expression to post-fix expression the algorithm uses a stack which used to store the operators in the expression and two strings one is the input string contains the given infix expression and the other string hold the output post-fix string. a function is used to check the precedence of the operators which is defined as follows 

• preceed(op1,op2) = true if op1>=op2
• preceed(op1,op2) = false if op1<op2
• preceed('(',op2)    = false for any operator  
• preceed(op1,'(')    = false for any operator other than ')'
• preceed(op1,')')    = true for any operator other than '('
• preceed (')',op2)   = is undefined 

Algorithm to convert infix expression to Postfix

opStack = the empty stack

loop until the end of the input

{

        symbol = next input character

        is symbol is an operand then

              add symbol to postfix string

         else

         {

                //check the precedence of the stack top and the adding operator

                while( stack is not empty AND preceed( stacktop >= symbol))

                {

                           topSymbol = opStack.pop()

                           add topSymbol to postfix string 

                  }

                  is  stack is empty OR symbol != ')' 

                              opStack.push(symbool)

                  else

                          opStack.pop()  //discard ')'

           }

}

end of loop

//pop remaining operators form the stack and add to post-fix string

while ( stack is not empty )

{

      topSymbol = opStack.pop()

     add topSymbol to post fix expression 

}

Implementation of Algorithm using Java 

//Program to evaluvate given postfix expression

import java.util.*;

class MyStack

{

    String stk[];

    int top;

    public MyStack(int size)

    {

        stk=new String[size];

        top=-1;

    }

    public void push(String ch)

    {

        stk[++top]=ch;

    }

    public String pop()

    {

        return stk[top--];

    }

    public String  peek()

    {

        return stk[top];

    }

    public boolean isEmpty()

    {

        return top==-1;

    }

    public void display()

    {

        System.out.print("S:{");

        for(int i=0;i<=top;i++)

            System.out.print(stk[i]+" ");

        System.out.println("}");

    }

}

class Evaluation

{

    //check whether the char is operator or not

    public  boolean isOperator(String op)

    {

        if(op=="+"||op=="-"||op=="*"||op=="/"||op=="%"||op=="$"||op=="^")

            return true;

        return false;

    }

    //check whether the char is operand or not

    public  boolean isOperand(String ch)

    {

       try{ int x=Integer.parseInt(ch); return true;}

       catch(Exception e){return false;}

    }

    //method to get value of two operands after applyingg operator

    public String getValue(String opnd1,String opnd2,String  op)

    {

        int result=0;

        int x=Integer.parseInt(opnd1);

        int y=Integer.parseInt(opnd2);

        switch(op)

        {

            case "+": result=x+y; break;

            case "-": result=x-y; break;

            case "*": result=x*y; break;

            case "/": result=x/y; break;

            case "%": result=x%y; break;

            case "$": result=(int)Math.pow(x, y); break;

            case "^": result=(int)Math.pow(x, y); break;

        }

        return result+"";

    }

    //method to evaluate the expression to post fix

    public String  eval(String postfix)

    {

        MyStack opndStack=new MyStack(50);

        String input[]=postfix.split(" ");

        //loop until the end of input

        for(int i=0;i<input.length;i++)

        {

           String symbol=input[i];

            //check whether the char is operand or not

            if(isOperand(symbol))

                opndStack.push(symbol);

            else

            {

               String  opnd1=opndStack.pop();

               String opnd2=opndStack.pop();

               String value=getValue(opnd1,opnd2,symbol);

               opndStack.push(value);

            }

        }

        return opndStack.pop();

    }

}

public class PostFixEval

{

    public static void main(String args[])

    {

        Scanner sc=new Scanner(System.in);

        System.out.println("Enter a Postfix expression seperated by spaces:");

        String postfix=sc.nextLine().trim();

        Evaluation con=new Evaluation();

        String result=con.eval(postfix);

        System.out.println("Result of "+postfix+" is: "+result);      

    }

}