Question

Assignment4: Evaluate Arithmetic Expressions.

Requirements:

1. Implement a concrete ArrayStack class that extends the IStack interface as we discussed in the class (any other different Stack class implementation, even if it is implemented by yourself, will not receive any credit).
2. Write a test class called Evaluate and a method that evaluates an arithmatic expression, which is given by a string.

import java.util.Scanner;

public class Evaluate {

  public static void main(String[] args) }
    // your implementation
    // obtain user's input from keyboard
    // invoke method expression() to get the result and print it out
  }

  public static int expression(String str) {
        // return the value
  }
}

public interface IStack {

abstract public int size();

//returns size of stack
   abstract public Object top();

//returns top of stack
   abstract public Object pop();

//removes top of stack and returns value
   abstract public void push(Object x) throws FullStackException;

//inserts data object to top of stack
   abstract public boolean isEmpty();

//returns true or false if stack is empty

}

1. Your implementation is required to use the IStack interface we discussed in the class.
2. provide a necessary test case to verify the result. For example,

   14-3*4+2*5-6*2 (should return 0)
   

   In another example,

   14-3*(4+2*(5-6))*2 (should return 2) 
   

   You may want to test all possible corner conditions to make sure your implement is inclusive.
3. Your implementation only considers +, - and * operators, as well as the parentheses (), and does not need to consider other operators and brackets. In particular, your code should not work with division operator "/".

Grading Criteria:

• Please make sure your program compiles, otherwise your submission will not be graded and you will receive zero.
• Point deduction rule:
  1. Compile warning: 3 points each.
  2. Minor error: such as not meeting the assignment input/output requirement, 5 points each.
  3. Major error: examples include, infinite loop, runtime errors, any runtime exception, 15 points each.
  4. Any code not compliant to the assignment requirement (e.g., not using IStack interface or ever using generic programming) will not be graded and you will receve zero.
  5. 20 point penalty if your program works with division operator "/".
• (40%) Correct implementation of IStack.java, ArrayStack.java and StackFullException.java.
• (40%) Correct implementation of Evaluate class with the expression method that correctly evaluates the expression with +, - and * operators.
• (10%) The above expression method supports the parentheses ().
• (10%) Correct README file (with the required contents).

Answer 1

CODE:

// NPrint.java

import java.util.Scanner;

public class NPrint

{

   //main method

    public static void main(String[] args)

    {

        int decimalvalue;

        Scanner sc1 = new Scanner(System.in);

        System.out.print("Enter decimal number:");

        decimalvalue = sc1.nextInt();

        if(decimalvalue==0)

            System.out.println("Binary number:"+0);

        if(decimalvalue>0)

            System.out.println("Binary number:"+binaryvalue(decimalvalue));

    }

    public static String binaryvalue(int decimalvalue)

    {

        if(decimalvalue > 0)

            return (binaryvalue(decimalvalue / 2) + "" + decimalvalue%2);

        return "";

    }

}

part 2:

// ArrayStack.java

import java.util.Scanner;

@SuppressWarnings("unchecked")

//stack interface

class ArrayStack<AnyType> implements Stack_Interface<AnyType>

{

    private static final int defaultvalue = 15;

    private int topvalue;    

    private AnyType[] A;

    public ArrayStack(int initial_Capacity)

    {

         A = (AnyType[]) new Object[initial_Capacity];

        topvalue = -1;

    }

    public ArrayStack()

    {

       this(defaultvalue);

    }

    public boolean is_Empty()

    {

       return topvalue==-1;

    }

    public AnyType peekvalue()

    {

        return A[topvalue];

    }

    public AnyType popvalue()

    {

       if(topvalue==-1)

        System.out.println("UnderFlow");

       return A[topvalue--];

    }

    public void pushvalue(AnyType e)

    {

       if (topvalue == A.length)

           System.out.println("OverFlow");

       A[++topvalue] = e;

    }

     public static int evaluateoperation(String tok)

     {

       

         ArrayStack<Integer> opr = new ArrayStack<Integer>(100);

         ArrayStack<Character> opvalue = new ArrayStack<Character>(100);

      

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

         {

          

           

             if (tok.charAt(i) == ' ')

                 continue;

            

             if (tok.charAt(i) >= '0' && tok.charAt(i) <= '9')

             {

                 String numvalue="";

                

             

   while (i < tok.length() && tok.charAt(i) >= '0' && tok.charAt(i) <= '9')

                {

                    numvalue=numvalue+tok.charAt(i);

                    i++;

                }

                i--;

                 opr.pushvalue(Integer.parseInt(numvalue));

             }

          

            

             else if (tok.charAt(i) == '(')

                 opvalue.pushvalue(tok.charAt(i));

             

             else if (tok.charAt(i) == ')')

             {

                 while (opvalue.peekvalue() != '(')

                   opr.pushvalue(do_Operation(opvalue.popvalue(), opr.popvalue(), opr.popvalue()));

                 opvalue.popvalue();

             }

        

             else if (tok.charAt(i) == '+' || tok.charAt(i) == '-' ||

                      tok.charAt(i) == '*' || tok.charAt(i) == '/')

             {

               

                 while (!opvalue.is_Empty() && has_Precedence(tok.charAt(i), opvalue.peekvalue()))

                   opr.pushvalue(do_Operation(opvalue.popvalue(), opr.popvalue(), opr.popvalue()));

                

                 opvalue.pushvalue(tok.charAt(i));

             }

          

         }

           

        

         while (!opvalue.is_Empty())

             opr.pushvalue(do_Operation(opvalue.popvalue(), opr.popvalue(), opr.popvalue()));

       

         return opr.popvalue();

     }

    

     public static boolean has_Precedence(char op1val, char op2val)

     {

         if (op2val == '(' || op2val == ')')

             return false;

         if ((op1val == '*' ) && (op2val == '+' || op2val == '-'))

             return false;

         else

             return true;

     }

    

     public static int do_Operation(char op1, int b1, int a1)

     {

         switch (op1)

         {

            case '+':

                return a1 + b1;

            case '-':

                return a1 - b1;

            case '*':

                return a1 * b1;

         }

         return 0;

     }

    

     public static void main(String[] args)

     {

        Scanner sc1=new Scanner(System.in);

        System.out.println("Enter Expression to evaluateoperation: ");

        String expression= sc1.next();

         System.out.println(evaluateoperation(expression));

     }

}

   

// Stack_Interface.java

interface Stack_Interface<AnyType>

{

  

   public boolean is_Empty();

   public AnyType popvalue() ;

   public AnyType peekvalue() ;

   public void pushvalue(AnyType e) ;

}