Post-fix Evaluation using Stacks

  

A Stack data structure can be use to evaluate post-fix expression. The algorithm uses a

Stack used to store the operands in the expression and the post-fix expression is scanned

from left to right char by char. If the read char is an operand then it is added to operand stack otherwise i.e., if it is operator then top most two operands in the stack are popped and the operator is applied on the operands and again the result is pushed in the stack. this process is continued until all the characters in the post fix expression are processed and at the end operand stack has one value which is the result of the expression.

Algorithm to evaluate Post-fix expression

operandStack = the empty stack;

loop until  end of input

begin

{

symbol=next input character;

if (symbol is an operand)

operandStack .push(symb);

else

{

opnd2 = operandStack .pop();

opnd1 = operandStack .pop();

value = result of applying symb to opnd1 and opnd2;

operandStack .push(value);

}

}

return(operandStack.pop());

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);      

    }

}