Implementing Recursion using an explicit Run Time Stack

Objective

  • You will solve the Towers of Hanoi problem in an iterative manner by implementing recursion using an explicit runtime stack.

Getting Started

Your directory should look like this:

P5/
└── src
    ├── Frame.java
    ├── Hanoi.java
    ├── Stack.java
    ├── StackException.java
    └── StackIF.java

Do not change the files StackIF.java and StackException.java. Work on Frame.java, Stack.java, and Hanoi.java in that order. Test your classes step by step.

Description

  1. 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.

  2. Stack.java implements the StackIF interface. Stack objects are run time stacks of frames. Complete the code 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.

  3. Hanoi.java implements the iterative, explicit stack-based solution. Do not change the constructor, getCount, printMove, and itHanoi methods. You will implement rtsHanoi using runtime stack rts. Study the Stack slides.

    Initially, there is one Frame [state,n,from,to] on rts as shown in the method itHanoi. You will need to implement rtsHanoi, where you will 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
      call the printMove method to print disk n move,
      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)

    Using 2 disks, the following files show the sample outputs:

    1. resNDB2 contains the result for input 2 in non-debug mode.
    2. resDB2 contains the result for input 2 in debug mode.

Instructions

  • Work on your own, as always.

  • Create a jar file called P5.jar that contains all the five Java files and submit via Checkin.

  • Make sure your code runs on machines in the CSB 120 lab.

  • Read the syllabus for the late policy.

  • We will be checking programs for plagiarism, so please don’t copy from anyone else.

Grading Criteria

  • 100 points for perfect submission.

  • 0 points for no submission, will not compile, submitted class file, etc.

  • Preliminary Tests:

    • testCompile: Checks compilation. (0 points)

    • testFrameToString: Checks toString method of Frame class. (4 points)

    • testFrameSetSTate: Checks setState method of Frame class. (4 points)

    • testOnePush: Checks push method of Stack class. (4 points)

    • testTwoPushesOnePop: Checks push and pop methods of Stack class. (4 points)

    • testHanoi1Debug: Checks iterative Tower of Hanoi solution, with 1 disk in debug mode. (15 points)

    • testHanoi2Debug: Checks iterative Tower of Hanoi solution, with 2 disks in debug mode. (15 points)

  • Final Tests:

    • We will also test all the other methods in the Frame class (16 more points).

    • We will also test for other situations in the Stack class (8 more points).

    • Final tests for Hanoi will include the preliminary tests, and new ones with more disks (30 more points).

Important
 Submit P5.jar to Checkin