Question

CS 209 Data Structure

(Postfix notation)

Postfix notation is a way of writing expressions

without using parentheses.

For example, the expression (1 + 2) * 3

would be written as 1 2 + 3 *.

A postfix expression is evaluated using a stack.

Scan a postfix expression from left to right.

A variable or constant is pushed into the stack.

When an operator is encountered, apply the operator

with the top two operands in the stack and replace

the two operands with the result.

Write a program to evaluate postfix expressions.

Pass the expression as a command-line argument

in one string.

Answer 1

import java.io.*;

class St

{

   private int[] a;

   private int t,m;

   public St(int maxim)

   {

     m=maxim;

     a=new int[m];

     t=-1;

   }

   public void push(int keys)

   {

     a[++t]=keys;

   }

   public int pop()

   {

     return(a[t--]);

   }

}

class Eval{

   public int calculate(String s)

   {

     int k,r=0;

     k=s.length();

     St a=new St(k);

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

     {

       char ch=s.charAt(i);

       if(ch>='0'&&ch<='9')

         a.push((int)(ch-'0'));

       else

       {

         int c=a.pop();

         int d=a.pop();

         switch(ch)

         {

           case '+':r=c+d;

              break;

           case '-':r=c-d;

              break;

           case '*':r=c*d;

              break;

           case '/':r=c/d;

              break;

           default:r=0;

         }

         a.push(r);

       }

     }

     r=a.pop();

     return(r);

   }

}

public class Main

{

   public static void main(String[] args)throws IOException

   {

     String input;

     while(true)

     {

       System.out.println("Type the expression");

       input=getString();

       if(input.equals(""))

         break;

       Eval e=new Eval();

       System.out.println("Answer: "+e.calculate(input));

     }

   }

   public static String getString()throws IOException

   {

     DataInputStream i=new DataInputStream(System.in);

     String s=i.readLine();

     return s;

   }

}

Program:

Output: