[Lab 1] [Lab 2] [Lab 3] [Lab 4] [Lab 5] [Lab 6] [Lab 7] [Lab 8] [Lab 9] [Lab 10] [Lab 11]

COMP2100
Lab 3: Stack-based calculator

Summary

You will work on a program which uses a recursive data structure: a reverse Polish calculator. This uses STACK Version 1 from Lectures 7 and 8.

Aims

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

Preparation

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

---

Exercise 1. Getting the source code

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

2. Download the compressed archive file lab03.tar.gz into your directory.

3. Uncompress the compressed file by typing `gunzip lab03.tar.gz'.

4. Unpack the archive by typing `tar xvf lab03.tar'. This will create the files you will be working on.

5. 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 next week's lab (on expression trees). It may help to think of the expressions as trees now:

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

---

Exercise 2. Reverse Polish calculator

Compile the program from the command line by typing

compile -clean -o calculator calculator main

in the shell. The root class is CALCULATOR. It 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 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. SmallEiffel 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.

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

---

Exercise 3. 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 to_string 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'. You may assume that class `G' has a query `out' which you can use to convert each element to a string (as you can for integers, for example).

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 4 - Changing the implementation

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

This involves a little bit more than just copying the code for Stack Version 3 from Lecture 9. The caclulator uses two extra features: depth and to_string. Even though depth is implemented in class STACK in Lecture 9, I want you to do it differently (better!) now. Make both of these deferred features in class STACK and give specific implementations in the sub-classes EMPTY_STACK and NONEMPTY_STACK. There should be no need for any if...then...else instructions.

Interestingly, this leads to code that appears to break the rule for recursive routines: the implementations of depth and to_string in class NONEMPTY_STACK will have no pathway through that doesn't result in a recursive call! Think about why this is OK.

Once you have finished coding the replacement STACK classes, you will need to modify class CALCULATOR to use this new implementation. This means looking hard at the differences in the interfaces. As a hint, notice that push and pop were commands in Version 1, but are now queries in Version 3. (In fact pop is a query on a Stack, while push is a query on a Stack Factory.)

[Lab 1] [Lab 2] [Lab 3] [Lab 4] [Lab 5] [Lab 6] [Lab 7] [Lab 8] [Lab 9] [Lab 10] [Lab 11]