[ANU] [DCS] [COMP2100/2500] [Description] [Schedule] [Lectures] [Labs] [Homework] [Assignments] [COMP2500] [Assessment] [PSP] [Java] [Reading] [Help]

COMP2100/2500
Lab 2a: Stack-based calculator

Summary

You will work on a program which implements a reverse Polish (or stack-based) calculator. This uses Stack Version 1 from Lectures 7 and 8.

Aims

• To give you practical experience building and traversing recursive data structures.

• To prepare you for Lab 2 on the expression parser and evaluator.

Preparation

Read through your lecture notes from Lecture 7 and Lecture 8 on Recursive Data Structures.

---

Exercise 1. Getting started

1. Use the mkdir command to create a directory for this lab, and the cd command to move there.

2. Download the Jar file StackCalculator.jar into your directory.

3. Unpack the archive by typing ‘jar xvf StackCalculator.jar’. This will create the files you will be working on.

4. Take a few minutes to read through the code and try to understand how it fits together.

This program deals with simple integer expressions, which it evaluates using a stack.

In the exercises, we will use the expressions (1 + 2) * 3 and 1 + (2 * 3) as examples. We will use the same expressions in Lab 2 (on expression trees). It may help to think of the expressions as trees now:

         *             +
        / \           / \
       +   3         1   *
      / \               / \
     1   2             2   3

Compile and run the program. The root class is CALCULATOR. The program keeps a stack of integers. On each line you can either type an integer or an operator.

• If you type an integer, then it is pushed onto the top of the stack.

• If you type "+", then the top two integers are popped off the stack and added together, and their sum is pushed onto the top of the stack.

• If you type "*", then the same thing happens, except that they are multiplied together.

• If you type "t" (for top) then the number on top of the stack is printed.

• If you type "q" (for quit) then the program stops.

Here are two sample sessions, using the two example expressions shown above:

1                             1
2                             2
+                             3
3                             *
*                             +
t                             t
9                             7
q                             q

In the version you have, the "*" and "t" commands have not been implemented. Your first task is to implement them.

When you have made your modifications, recompile and test the system until it works. If you get an error message from the compiler, read it carefully and try to figure out what it means before you ask your tutor. The Java compiler tells you exactly where it found an error: which class, which line and which column. In Emacs, if you type M-x column-number-mode then the column as well as the line that the cursor is on will be displayed in the bar at the bottom of the window. You can use this to find the place the error was detected. In DrJava it is even easier: compiler errors are displayed in a pane at the bottom of the main window, and when you click on one, the relevant part of the code is highlighted in the main editing pane above.

Similarly if your program crashes while running, take time to read carefully through the stack dump. The information here is extremely useful, and in many cases is enough to let you figure out what went wrong.

---

Exercise 2. Extending the stack-based calculator

Once you have the basic calculator working, implement the following new commands. These add extra functionality to the calculator.

• If you type "p" (for print) then the whole stack is printed.

• If you type "r" (for roll or rotate) then the stack is rotated: the number on top moves to the bottom, and all the other numbers move up one place.

Here is an example of how they work:

1
2
3
p
1 2 3
r
p
3 1 2
q

The "p" command is implemented by adding a new query toString() to class Stack. This is an example of a recursive routine for traversing a recursive data structure. If you're stuck, you might find it helpful to look at the code for the query ‘depth’.

The "r" command is implemented on the client side, in class Calculator. You'll probably want to declare a local stack for temporary storage, also a local integer for storing the top element. It might help to think about how to move all the elements from one stack to another, reversing their order.

---

Exercise 3 - Changing the implementation

The program now uses Stack Version 1 from Lecture 7. Replace that with Stack Version 3 from Lecture 8 and the related Stack Factory. You will need to replace class Stack and then modify class Calculator to use the new implementation.

[ANU] [DCS] [COMP2100/2500] [Description] [Schedule] [Lectures] [Labs] [Homework] [Assignments] [COMP2500] [Assessment] [PSP] [Java] [Reading] [Help]