CS 112 Fall 2011 -- Homework Two

Due Monday, September 26th at 12 Midnight

Introduction

In this assignment we give you an ugly, ungainly piece of code that works well, and you need to organize it in good object-oriented style, following the discussion in class about multiple classes and organizing your Java code. You will then take your object-oriented code and improve one of its objects. The usual caveats apply:

Consult the textbook and the Java online documentation as needed.

For this homework, we provide you on the class web site with a program ReversePolishCalculatorMess.java that performs calculations with "reverse Polish" expressions, sometimes called "postfix" expressions. Our usual mathematical notation is infix--we the operation between the operands, such as A + B. In postfix, we would write A B +, which has the advantage that parentheses are never necessary. The rule for evaluation is to scan the expression from the left, and replace any expression "A B op" with the result of applying op to A and B. This can be easily implemented with a stack: scan the expression from left to right, push all operands you find on a stack, and when you find an operator, pop two operands off the stack, apply the operator, and then push the result back on the stack. At the end, you should have exactly one value on the stack, the result (if your stack underflowed, you had too many operators, and if you have more than one number on the stack at the end, you had too many operands). For example, instead of writing "(2 + 4 ) * (7 - 3)" we could write

2 4 + 7 3  - *
and evaluate it as follows: 
push 2, then 4:                  | 2 4     (stack grows from left to right)
pop 2 and 4, apply +, push 6:    | 6
push 7, then 3:                  | 6 7 3
pop 7 and 3, apply -, push 4:    | 6 4
pop 6 and 4, apply *, push 24:   | 24

The result is 24. The program ReversePolishCalculatorMess.java on the class web site implements this form of expression evaluation, and also allows you to make assignments to variables (which must be single letters), and stores them in an array of integers indexed by the sequence number of the letter (i.e., 'a' = 0, 'b' = 1, ..., 'z' = 25). (Initially the variables are 0.) For example, if we assigned 2 to a and 7 to c we would have the following table:


0  |  2 |           'a' is letter 0
1  [  0 |           'b' is letter 1
2  |  7 |           'c' is letter 2
3  [  0 |           'd' is letter 3
4  [  0 |           etc.
    .
    .  
    .
For now we restrict the input to variable names which are single letters.

The program takes two kinds of inputs. The first kind is a postfix expression (or portion thereof) involving numbers, single-letter variables, and operations +, -, *, /. The second kind is the "set" command, as in "set x 7". This command has no effect on the stack -- it only changes the value of the variable (in this case, x), which may be pushed onto the stack by a later command. It prints the stack after each command. For instance, the following is sequence would compute 9-(xy-x+y)/3 for x=13 and y=23: (user input in blue; the answer is, of course, 112): 

set x 13
Stack:
set y 23
Stack:
9 x y * x - y + -3 / -
Stack: 9.0
Stack: 9.0 13.0
Stack: 9.0 13.0 23.0
Stack: 9.0 299.0
Stack: 9.0 299.0 13.0
Stack: 9.0 286.0
Stack: 9.0 286.0 23.0
Stack: 9.0 309.0
Stack: 9.0 309.0 -3.0
Stack: 9.0 -103.0
Stack: 112.0

First download the program, play around with it, and understand how it works (try various errors as well).

Problem One: Infix to Postfix [10 pts]

Convert these expressions in to postfix notation: Submit a text file postfix.txt

Problem Two: Clean up the Code [35 points]

Your job is to reorganize this code using good object-oriented principles, namely:

  1. You should "divide and conquer," breaking the code up into a client (with the same name as the original file, except the word Mess) and two ADTs (named SymbolTable.java and Stack.java). Stack should have the usual methods described in class, plus a print method that returns a String containing a space-separated list of entries in the stack (note that the word "Stack: " should be output from the client code, not the Stack class; morever, the Stack class itself should never output anything to the console). SymbolTable should have a set method that takes a variable name (a char) and value (a double), and a lookup method that takes a variable name (a char) and returns a double.
  2. You should further organize each of these classes properly, using methods and fields appropriate to organize your thinking (what if you have to redo this a year from now? what if you have to reimplement it in a different way? The better organized the easier this will be!); provide appropriate comments and format your code carefully, so that it is easy to understand.
  3. Think carefully about what should be public; everything else should be private.
  4. You may make any other changes you deem necessary as long as the functionality is unchanged and your code follows good object-oriented design principles. Add appropriate comments.

Submit the files ReversePolishCalculator.java, SymbolTable.java and Stack.java.

Problem Three: Improve the Code [35 points]

Now that you have code that you can work with, improve it so that (a) variable names can be strings--specifically, any string of English letters except the word "set"; and (b) if an operator occurs when the stack has fewer than two entries, it is simply ignored and the stack remains the same. You should not need to modify Stack.java. It's up to you to figure out how modify the rest of the code; do NOT use anything from the Java libraries that will make the job trivial (i.e., implement it yourself!). Submit the files ReversePolishCalculatorImproved.java and SymbolTableImproved.java.

Problem Four: Lab (20 pts)

You will be doing an activity in lab this week which you must hand in as part of this homework; instructions will be given in the lab.