Programming Assignment 1

Computer Science 102

Spring 2002

Due date: THUR, FEB 7, 11:59 pm (midnight). Draft #2 is due one week after your etutor returns the first draft .

Draft #1

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/spring02/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. In draft #1, 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 2.75. To get a grade of 3.0 in draft #1, 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 for draft #1 divides into two parts:


Both of these classes are called drivers.

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 use wrapper classes Character and Double to accomplish our goal. Since both of these are subclasses of Object, instances of both these types can be pushed on the stack. Its like assigning an instance of a smaller class to an instance of a wider class. For instance, when pushing ans make it a field of a Double instance variable and push that instance variable on the stack by using

prim = new Double(ans);
stack.push(prim );
Here the Double instance variable is prim. The advantage of this approach over creating your own wrapper class is that it forces you to instantiate an object each time you push down the stack.

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

prim = 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:
prim = (Double)stack.pop();
To get the primitive double value, use
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, i.e. use charValue().

In both the Converter and Calculator classes, use a StackADT that checks for an empty stack when popping and a full stack when pushing. You should write your own MTstackException and FullStackException classes to do this. As a consequence, you should do no stack checking in the driver program except as indicated in the infix to postfix conversion program on the web.

The Converter class


This uses the following methods

  1. The boolean method isOperator(char ch)
  2. The boolean method isOperand(char ch)
  3. The booleanmethod 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.

For draft #1, write your program so that there are three files. That way it is easier to compile (one file at a time). Here are the steps:

  1. A Converter class written so that the main method is rewritten as a method that returns a string. Let's call it toPostfix() with the signature: public String toPostfix()
  2. A Calculator class that instantiates the Converter class so that it can access method toPostfix().
  3. A StackADT class and the exception classes in one file.

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

Draft #2

In this draft, your program should be able to handle input with multiple digit input, e.g., 1+23*456/7890. Full credit for this part of the project is 1.0. Here are some hints. It's OK if you do this another way; but it must be clear to the reader what you have done.

  1. Write a Scanner class that has a method toArray that returns an array of String, let's say the instance variable qtokenArray that is an array containing the tokens and another instance variable, let's say m which contains the number of tokens generated. This way, if your altered Converter class extends Scanner, it will inherit m and tokenArray. It will also inherit isOperator and isOperand from Scanner. One way of implementing the scanner is to write a program that inserts a blank between each token in the input string and then run the resulting string through the stringTokenizer.
  2. Write a Converter class that has a method toPostfix() that also returns an array of String, let's say, the instance variable postfix. Instead of concatenating, add each new token as the next element of the array postfix. To use isOperator and isOperand check the first character of the string that is an element of tokenArray. Note that tokenArray and postfix have different indices.
  3. Use the same strategy to write the Calculate class. If it extends the Converter class you can use m and postfix.

Another way of designing the program is to not write a scanner, but to have the converter class insert a blank as a delimiter (separator) between each token. The calculator class then takes this altered string and evaluates it.


Samuel Marateck
MON Jan 29 1 22:23:14 EST 2002