Programming Assignment 1

Computer Science 102

Spring 2001

Due date: THUR, FEB 1, 11:59 pm (midnight). The resubmission is due one week after your etutor returns the first draft .

Please send your programs to the correct etutor determined by the first letter of your last name. The URL for this is:

http://cs.nyu.edu/courses/spring01/V22.0102-002/submitting.html

and is found on the homepage under the heading Where to submit your programs .

Introduction
Your project is to design a program to implement a calculator. The calculator will take an infix expression convert it to a postfix expression and then evaluate it. The infix expression will consist of operands that are single digits and the operators {+, -, *, /}. An example of such an expression is 2+3*4/6. This will translate to 234*6/+ and will then be evaluated as 4.0. Full credit for doing this will be a grade of 3.5. To get a grade of 4.0 your program must evaluate infix expressions containing parentheses such as (2+4)*(8-2)/(11-9). The course homepage contains explanations of how to do all of this under the category Stack programs

Your project divides into two parts:

Normally we would use a stack of char to do the conversion and a stack of double to do the evaluation. Java, however, allows us to use a stack of Object for both. Unfortunately the primitive types, in our case double and char are not classes. However, we can form a class using instance variables of these types. So for char we use

class CType
{ char token;
}

and for double we use
class DType
{ double token;
}

Since both of these are subclasses of Object, instances of both these types can be pushed on the stack. Before you push an instance on the stack, you have to assign the character or numerical value to the instance variable. For example, if primitive is an instance of DType and you want to push the double variable ans on the stack, you must use the following code:
primitive.token = ans; 
stack.push(primitive);

where stack is an instance of a stackADT class that you will define. Please note that if you do not create a new object each time you push an item on the stack, at the end every item will have the same value as the last item pushed on the stack.

Special consideration must also be given to removing items from the stack. Since the Object class is wider than the DType class, writing

primitive = stack.pop();
will cause an error since you cannnot assign an object of a wider class to an object of a narrower class with out type casting. So you must write:
primitive = (DType)stack.pop();

An Alternate approach

An alternate approach is to use the wrapper classes Character and Double. For instance, when pushing a Double use
prim = new Double(ans);
stack.push(prim );
where the instance variable is Double prim. The advantage of this approach is that it forces you to instantiate an object each time you push down the stack. When you pop the stack, use
prim = (Double)stack.pop();
System.out.println( prim.doubleValue() );
where doubleValue() is the wrapper class method that extracts the double value from the object prim. Use an analagous code for the Character wrapper class.

The Converter class


This uses the following methods

  1. The boolean method isOperator(char ch)
  2. The boolean method isOperand(char ch)
  3. The boolean method precedence(char op1, char op2) which determines if the incoming token op2 has precedence over the top of the stack op1.


The Calculator class

This uses the following methods

  1. The boolean method isOperator(char ch)
  2. The boolean method isOperand(char ch)
  3. The double method result(double op1, double op2, char op) which determines the value of the binary operator op operating on the operands op1 and op2.


Strategy for writing the program

Here is a recomended way of writing the program. If you feel comfortable skipping some steps to get to the final result, then by all means do.
  1. Write the Calculator class using a stack of double and test it using postfix input.
  2. Rewrite the Calculator class using a stack of Object.
  3. Write the Converter class using a stack of char and test it using infix input.
  4. Rewrite the Converter class using a stack of Object and instead of it printing the final postfix string, it should return a String.
  5. Have the Calculator class call the Converter class in order to get a postfix expression as input.

Pitfalls

The major source of error is not using the peek() function correctly. If you peek at an empty stack, your program will throw an IndexOutOFBoundsException . Therefore it is recommended that in your program, both peek() and pop() throw an IndexOutOFBoundsException when the empty stack condition is met. See page 305 of the text for this.

Sample input

Your output should show the converted postfix string and the result of the calculation. For instance the last sample input will produce the following in the output window:

type your infix expression
(4+8)*(6-5)/((3-2)*(2+2))

converted string is 48+65-*32-22+*/

answer is 3.0


Samuel Marateck
MON Jan 22 1 22:23:14 EST 2001