(Mondays 2 PM)
(Fridays 2 PM)
Due to Passover, Triduum, and Easter, a special no-cost extension on this lab is granted.
The code portion of this assignment can be turned in before
2 PM, Monday 5 April 1999
and still be counted on-time.
Late-lab coupons cannot be used to extend the deadline further.
Meanwhile, and apparently (but actually not) unrelated,
Java programs are translated into
.class files which contain
instructions (bytecodes) for a
Java Virtual Machine (JVM).
The Java program is then executed by interpreting the
bytecodes, and doing what they say. It turns out that arithmetic in Java is
performed on a stack. For example, addition is accomplished by popping the
stack's top two elements, adding them together, and then pushing the result
back on the stack. The instruction that does this is called
In this lab, you will design a generic
Stack class, which
will then be extended into two subclasses.
RoomStackrepresents a stack of rooms. Suppose Hansel and Gretel were wandering through a maze. The stack would represent how they would find their way back to the starting point, with a bread crumb dropped in each room. You will use the stack of rooms as you explore a maze, starting at its upper-left corner and looking for its lower-right corner.
IntStackrepresents a stack of integers and offers methods for simple calculations based on the stack's top elements.
The design will be discussed Monday in class. In Lab, your graded design will be returned. No other handouts or code will be issued. So, think carefully about your design!
Note: for this lab you will need your solution to Lab 7. Copy those files into your Lab8 subdirectory, and then add the files from the zip.
Remember to type the following lines at the top of any files that use the terminal or canvas classes.
import cs101.terminal.*; import cs101.canvas.*;
Because of your work on Lab 7, the new, robot-occupied, loop-free building has been successfully constructed. It is now time to simulate the progress of a robot through the rooms, as it starts in the upper-left room and tries to find the lower-right room.
The robot, being a methodical creature, will eseentially do two things:
|The maze is formed. There is a unique path between any pair of rooms. In particular, it is possible to traverse the maze, moving from the upper-left corner to the lower-right corner.|
|Above, you see the robot beginning to explore the rooms. As the robot makes progress through a room, the room is brightened (the robot turns the lights on).||When the robot is done with a room, knowing it cannot be on a path to its final destination, the room is darkened.|
|The robot has found the destination. The dark rooms are abandoned and the bright rooms are on the path from the source to the destination.||The robot uses the room stack to trace its steps back to the beginning, making each room red as it goes.|
The easiest way for us to simulate the robot is to use the
Your task for this lab is to insert a method in
void explore(Room stop). When this method is called
on a given room, the maze is traversed as described above.
Our stack calculator is able to perform the following operations:
|| Returns |
|| Pushes the supplied integer onto the stack.
Design issue: Because
|| Pops the stack's top element, returning the answer as an
Design issue: What should happen when the stack is already empty?
|| Returns the stack's top cell as an
Design issue: What should be done if the stack is empty? There is no value that we can return to show that an error has occurred. We need to throw an error. Your design should call for this behavior. In class, you will learn how to do this.
|| Pops the stack's top two integers, computes their sum, and pushes
Design issue: What happens if the stack underflows during this operation (i.e., there are not at least two elements on the stack)? This same issue arises in most of the operations below.
|| Pops the stack's top two integers, computes their product, and pushes
Design issue: By now, it seems
that a common thing to do is to pop the stack and receive the
value as an
||Pops the stack's top integer, negates its value, and pushes the result.|
|| Pops the stack's top two integers, computes their difference, and pushes
|| Duplicates the stack's top integer. After this operation, the stack
has grown by one value and the top two values are identical.
Design issue: Should the duplicated
|| Shows the contents of the stack using
Big design issue: Should
IntStack contain a
Think about the operations that your generic
Stack can do, and
see if they are appropriate for the
IntStack. If so, extension
should be done so you don't have to duplicate function.
By contrast, consider that
did not extend List in
Lab 7, because many functions of
List, such as
exchange, were inappropriate for a set.
Mazeof maze of 5x7 rooms is generated using your code from Lab 7. Each time, the
exploremethod is called on the upper-left corner room.
void explore(Room stop)
Stackclass. Be sure to indicate what is
IntStack. Turn in your decisions for the design issues. The API is really given to you above---no need to turn an API in for
Room. That is, describe what will happen when your
public void explore(Room).
(The files contain some more specific instructions.)