CS 200, Spring 2017
P1: Implementing Recursion using an explicit Run Time Stack
Due and late dates and times
- Due: Thursday Feb 2
- Late: Monday Feb 6
Overview
The object of this assignment is to implement recursion using an explicit Run Time Stack. Copy the following
code into an eclipse project:
StackIF.java, StackException.java are given. DO NOT CHANGE THEM. Work on Frame.java,
Stack.java, and Hanoi.java in that order. Test your classes step by step.
Frame.java
Frame.java describes the behavior of the run time stack frames for Hanoi. A frame object
contains four variables: n: the problem size, from: the source
peg position of the pile of discs to be moved, to: the destination peg position
of the pile of discs to be moved, and state: the state the Hanoi method is in (see
the Stack lecture slides). Complete this class first and test it using its main method.
Stack.java
Stack.java implements the StackIF interface. Stack objects are run time stacks of frames.
Complete the code next and test it using its main method. **NOTICE**: In this code, a Stack is
implemented using an ArrayList, and push is implemented by adding to the **END** of the ArrayList.
Hanoi.java
The recursive solution to the Hanoi problem, recHanoi(), is given. DO NOT CHANGE IT.
You need to work on the iterative, explicit stack based solution. Start implementing
the constructor and the getCount() and resetCount() methods. Then you are ready to
implement rtsHanoi using Run Time Stack rts. Study lecture 2: 02-stacks slides.
Initially, there is one Frame [state,n,from,to] on rts. Keep popping frames until rts is empty.
When popping a frame:
- if debug, print rts (see provided code)
- if n == 0 do nothing (stack frame has already been popped)
- else if frame in state 0:
go into state 1 by pushing a frame [1,n,from,to] on the run time stack
and call hanoi(n-1,from,via) by pushing frame [0,n-1,from,via] on the run time stack
- else if in state 1
print disk n move (see recHanoi)
and go into state 2 by pushing a frame [2,n,from,to] on the run time stack
and call hanoi(n-1,via,to) by pushing a frame [0,n-1,via,to] on the run time stack
- else (in state 2) do nothing (stack frame has already been popped)
Testing and submitting your code
-
resDB2 contains the result for input 2 in debug mode.
-
resDB3 contains the result for input 3 in debug mode.
Use the CS200 Checkin webserver to exercise and submit your code. Submit a P1.jar file containing your
Frame.java, Stack.java and Hanoi.java files. NOTICE: submit a jar file containing ***java files, not
class files***. If you are unsure how to do this, ask your TA in recitation.