\ Programming Assignment 1 Computer Science 102

Programming Assignment 1

Computer Science 102

Spring 2009

Due date: MON, FEB 09, 11:59 pm (midnight). Draft #2 is due one week after your etutor returns the first draft but start working on it as soon as possible. .

Draft #1

Please send your programs to the etutor. The URL for this is:


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

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 3.75. To get a grade of 4.0 in draft #1, your program must evaluate infix expressions containing parentheses such as (2+4)*(8-2)/(9-5). The course homepage contains explanations of how to do all of this under the category Stack programs http://cs.nyu.edu/courses/spring08/V22.0102-002/infix or for another explanation of postfix expressions, see pp 82-89 in the Weiss text. I feel the web page explanations are sufficient.

Your project for draft #1 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 generics for both (please see StackADT2 done on Jan 28, but alter it so that there is also a constructor without any parameter that intializes n to 100 i.e., super(n). This guarantees that if you forget to use a parameter, the stack array is dimensioned to 100). The primitive types, in our case double and char are not classes. However, we can use autoboxing to push onto the stack declared as Double and Character respectively.

Special consideration must be given to removing items from the stack. Since you are using generics, writing

 double ans = stack.pop(); 

will not cause an error since the stack is declared as a stack of Double.

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 StackException class to do this. As a consequence, you should do no stack checking in the driver program except when popping the stack converting from infix to postfix.

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(Object 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.
  2. Write the Converter class using a stack of Character and instead of it printing the final postfix string, it should return a String.
  3. 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

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+(2.33*456)/7890 -12/5 + 23%4. Thus blanks between delimiters (such as the blank between the 5 and the +) are allowed. Your program should handle doubles and ints just as Java does so that 12/5 is 2 and 23%4 is 3. Similarly, 5/3 + 1.0 evaluates to 2.0. Of course 12.0/5 is evaluated as 2.4 since 12.0 is a double; have 12.0%4 give an error (although this is not the case in Java). You will need two methods to calculate results, one for doubles and one for ints. Converting the results to a string and pushing them on the stack will accomodate both doubles and ints. Use the same genertic stack class used in draft 1, but declare it as a stack of String. Full credit for this part of the project is 4.0. Here are some hints:

  1. Use StringTokenizer to write a method formTokens that has a parameter that is an array of String, let's say the variable tokenArray that is an array containing the tokens, and returns another variable, let's say m which contains the number of tokens generated. A program using the StringTokenizer can be found at http://cs.nyu.edu/courses/spring09/V22.0102-002/feb4/Prog1.java
  2. Write a Converter class that has a method toPostfix() that also returns an array of String, let's say, the 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. The one for tokenArray is the same as that for the for loop. Also have a method isValid to test if the input expression has any faulty characters, and a method matching that uses a stack to check for matching parentheses (see pages 83 and 84 in the Weiss text). A non-match should throw an exception called UnmatchedException.
  3. Use the same strategy to write the Calculate class. To test for doubles and ints use regexp (see the Wikipedia regexp link) and http://cs.nyu.edu/courses/spring09/V22.0102-002/feb2/Prog9.java for the regexp for a positive or negative double. If it extends the Converter class you can use m and postfix. If either both or one of the operands are doubles, use the version of evaluate we wrote in class. If both are ints use a different version of evaluate, one that includes all the integer operations. When the answer is returned by either version of evaluate, concatenate it with the empty string and push it onto the stack.

Samuel Marateck
SAT Jan 24 22:23:14 EST 2009