Assignment 1

Due Date : midnight of Jan 29, 2013

Implementation of a calculator

(1) Implement the following interface for a stack.

  public interface Stack { 

    public void push( Object O) ; 

    public Object pop(); 

    public boolean isEmpty(); 

    public Object top(); 

  } 

(2) Implement a RPN Calculator.

  The RPN (Reverse Polish Notation) for writing arithmetic expressions was invented   by the Polish mathematician Jan Lukasiewicz. In this notation, the operator appears after   the operands. For example, the RPN expression for 

    7 + 9 

  is 

    7 9 + 

  Similarly, the RPN expression for 

    ((4+6)*9+5*7)*3 

  is 

    4 6 + 9 * 5 7 * + 3 * 

  The nice feature about RPN notation is that we can write any arithmetic expression without using brackets. 

  More formally, here is how to evaluate an RPN expression. Scan the expression from left to right. Whenever we encounter an operator, we look at the two operands to the left of it. We replace the operator and the two operands by the value of the operator on these two operands. We continue scanning till we reach the end of the expression. For example, consider the expression 

  4 6 + 9 * 5 7 * + 3 * We first replace 4 6 + by 10 to get 10 9 * 5 7 * + 3 * Then we replace 10 9 *  by 90 to get 90 5 7 * + 3 * After this we get 90 35 + 3 *, 105 3 * and finally 315. So the value of the expression is 315. 

  Implement a class RPNCalculator which has the following method 

    public void evaluateRPN( String s); 

  This method takes as input an RPN expression in the form of a String. The method should analyze the String, and use the implementation of the Stack interface to print the value of the RPN expression. You can assume that the only allowed operators are   + ,   -  ,   * and the operands are positive integers. 

(3) Implement a calculator for arithmetic expressions.

  We would now like to have a calculator which evaluates expressions written in the notation we normally use, which we call the standard notation. Implement a class Calculator which contains the following method 

    public String convertExpression ( String s); 

  This method should take as input a String representing an arithmietic expression written (the string could have spaces between numbers or operators)   in the standard notation, and return a String representing the expression in RPN notation. Again you can assume that the expression in the standard notation contains 

  +  ,   -   ,   *  ,   (  ,   )   and positive integers only. 

  The method should print appropriate error messages if the input string is not a valid arithmetic expression. 

  The main method in this class should take an arithmetic expression in the standard notation  as input, call the convertExpression method to convert this into an RPN expression,  print this RPN expression and then call the evaluateRPN method to print the value of the expression. 

  Note In the standard notation, multiplication has precedence over addition or subtraction. 

    For example, the value of 6+3*4 is 18. 

Submission Instructions