Assignment 4

Harvey Mudd College
Computer Science 60
Assignment 4, Due Friday, Feb. 22, by midnight

Unicalc Encore! -- and writing a Queue...

This assignment consists of writing two Java files. The first is a "port" into Java of the Unit-conversion calculator that the last two assignments have developed. To do this port, you will use the OpenList class you wrote in the last assignment. The second is to write an example of a closed linked list called a Queue, which accepts items only at the back of the list and releases items only at the front.

The key ideas are that a lot of the functionality that's available in Rex is also available in Java (hence the Unicalc class, but Java makes it easier to write code that takes advantage of side effects, e.g. with "closed" lists like the Queue. In addition, this week's assignment is meant to provide enough practice with Java references and Java syntax that they will be less of an issue in the more involved algorithms and graphical programs to come.

Submitting your code

For this assignment, you will need to create two files, named Unicalc.java and Queue.java.

To submit the files, you will need to run

cs60submit Unicalc.java
cs60submit Queue.java

from the directory in which they are located. The submit script will ask you for the assignment number (#4).

Reading

This assignment continues through the book's Chapter 7. However, Chapter 6 is not completely necessary... (we will come back to Chapter 6 later in the course). Also, most (hopefully all) of the material needed to do this assignment will be presented in class.

Testing your code

You can test your code by using the main methods in the files /cs/cs60/as/a4/Unicalc.java and /cs/cs60/as/a4/Queue.java. You can simply "comment-in" tests as you wish. The expected output is in the files /cs/cs60/as/a4/Unicalc.out and /cs/cs60/as/a4/Queue.out. If you'd like you can simply start coding from these files (or you may start from scratch).

Note: You need to use the toString methods provided in those two files -- one for the Quantity class and one for the Queue class. Writing your own is dangerous because it makes testing very difficult, if your toString produces different output than ours!

Code to test each of the Java classes you're writing in this assignment also appears in the files /cs/cs60/as/a4/Test#.java , where # ranges from 1 to 20. #1 - 10 are Unicalc tests, #11 - 20 are Queue tests.

These steps guide you through the testing:

First, compile your class (Unicalc or Queue).
(Actually, compiling the test will automatically compile the files it needs in the current directory, but this is still a good idea in order to be sure your code compiles at all!)
Then, copy /cs/cs60/as/a3/Test#.java and /cs/cs60/as/a3/Test#.out to the directory in which you're working
Compile the test file it with javac Test#.java
Execute the test file with java Test#
Compare the difference between your output and the expected output in Test#.out. This can be done visually or with the unix diff command:
```
       java Test# | diff - Test#.out
       
```
If there is no output from the diff command, your output matches the expected output perfectly. If there are output lines from the diff command, those beginning with < are lines appearing in your output, but not the expected output. Lines beginning with > are lines appearing in the expected output, but not your output.

Problems (only two of them...)

Problem 1: Unicalc in Java

The first problem is to write two classes, named Quantity and Unicalc, in a file named Unicalc.java. NOTE: you should include in your Unicalc.java file the code for the OpenList class you wrote for Assignment 3. If you'd rather use the solution OpenList class, it's available in /cs/cs60/as/a4/OpenList.java and on-line from the assignments page.

Overview Your Unicalc class is an "execute-only" class. That is, no objects of type "Unicalc" will be made and so the Unicalc class will consist of only static methods. Because Quantity Lists are so central to the Unicalc application, you will also need to create a Quantity class to represent them. Following are the details of these two classes.

The `Quantity` class

The Quantity class will represent a quantity list, that is, something of the form

     [ 9.8, ["meter"], ["second", "second"] ]

The suggested data members and methods to include in your Quantity class are these:

Data members:

      private double q;    // the quantity
      private OpenList N;  // the numerator
      private OpenList D;  // the denominator

Constructor:
```
      public Quantity(double q, OpenList N, OpenList D);
    
```
Other constructors are possible, for convenience, but this is the only one you need to have.

Methods: (all nonstatic)

      public double getQ();     // returns the quantity 
      public OpenList getN();   // returns the numerator
      public OpenList getD();   // returns the denominator
      public String toString(); // creates a printable representation
                                // BE SURE TO TAKE THE PROVIDED CODE!

The `Unicalc` class

The unit-conversion calculator in rex is available from the assignments page in the solutions to assignments 2 and 3. You don't have to emulate that recursive rex code, but it does make things easier than trying to implement it without recursion. Many people avoid recursion at all costs -- in this problem those costs are high.

You will need to write six Unicalc methods. Here are their signatures:

(1)  public static Quantity simplify(Quantity L);
(2)  public static Quantity multiply(Quantity L, Quantity M);
(3)  public static Quantity divide(Quantity L, Quantity M);
(4)  public static Quantity conv_unit(String s, OpenList db);
(5)  public static Quantity norm_unit(String s, OpenList db);
(6)  public static Quantity norm(Quantity QL, OpenList db);

The other method, convert is provided in /cs/cs60/as/a4/Unicalc.java (again, to ensure consistency of output).

Keep in mind that all methods in your Unicalc class will be static. And, because you'll never create a Unicalc object, you do not need to write any constructors... .

You are free to implement additional methods in your OpenList, Quantity, or Unicalc classes: feel free to add whatever functionality you might need.

Important Notes on Unicalc

Each item in an OpenList is an Object. When you want to use those Objects as specific classes (namely, Strings or OpenLists), you will need to cast them to the appropriate type. In java this casting is explicit.

For example, suppose that N is an OpenList that is nonempty. Then, N.first() returns an Object that is really a String containing the first unit in the numerator. So, to make sure that java knows that it is a String, you need code like
```
       String unit = (String) (N.first());
       
```
A small database of unit conversions is available as an OpenList by calling the static function getDB() (provided in /cs/cs60/as/a4/Unicalc.java)
PLEASE test your code as you go along... Java offers a lot more opportunities than rex for syntax errors and other coding problems. You'll want to make sure that each function you write works before moving on... .

Problem 2: A `Queue` class

Write a java class named Queue that implements a closed-list version of a Queue. Recall that a Queue is a list in which data are added (enqueued) at the back and removed (dequeued) from the front.

As a starting point, you might want to consider the Stack class covered in class and available in /cs/cs60/as/a4/Stack.java.

In any case, you need to have the following things in your Queue class:

Use the QCell class from the notes/lecture in order to hold data. In essence, your Queue class will be a linked list of QCells.
Use the toString method provided in the file /cs/cs60/as/a4/Queue.java in your Queue class so that you can print Queues easily.
Write a zero-argument constructor that returns an empty Queue (i.e., the front and back are null):
```
       public Queue()
       
```

Write static and nonstatic versions of an enqueue method. The method signatures should be

       public static void enqueue(Object o, Queue Q);
       public void enqueue(Object o);

Write static and nonstatic versions of a dequeue method. The method signatures should be
```
       public static Object dequeue(Queue Q);
       public Object dequeue();
       
```
Both methods should return null if dequeue is called on an empty Queue.

Write static and nonstatic versions of an isEmpty method with signatures

       public static boolean isEmpty(Queue Q);
       public boolean isEmpty();

Don't forget to include toString (available in /cs/cs60/as/a4/Queue.java) and a main method (from the same place) that you can use to test your code.

The wholly optional extra credit involves extending the functionality of your Queue class.

Extra Credit

For totally optional extra credit (up to 20%), add a nonstatic method evaluate to your Queue class. The idea is to add something of a real calculator to complement the unit calculator of problem #2. The signature of the evaluate method is simply

  public double evaluate()

What evaluate does is return a double that is the "value" of the Queue that invoked the method (the "this" Queue). That is, evaluate looks through the items on its Queue one by one as if they were forming an arithmetic expression. Then it evaluates that expression. You can assume that every data element in the Queue will be either a Double or a String that is one of "+", "-", "*", or "/". (Remember that Double is a Java wrapper class so that values of type double can be treated as Objects.) The "*" and "/" should be executed immediately -- at highest priority -- and the "+" and "-" have lower priority. For example, if the Queue Q consisted of

  10 + 4 * 5 / 2 - 3

where the left is the front of the Queue and the right is the back (most recently inserted elements), then Q.evaluate() should go through these steps:

  10
  10 + 4
  10 + 4 * 5 == 10 + 20
  10 + 20 / 2 == 10 + 10
  10 + 10 - 3 == 20 -3
  20 - 3 == 17

Any implementation that provides the correct answer (17 in this case) is all right.

Harvey Mudd College Computer Science 60 Assignment 4, Due Friday, Feb. 22, by midnight