CS 200, Spring 2017
P1: Implementing Recursion using an explicit Run Time Stack

Due and late dates and times

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:

Testing and submitting your code

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.