CS 200, Spring 2015
P1: Implementing Recursion using an explicit Run Time Stack
Due and late dates and times
- Due: September 8, 23:59
- Late: September 10, 23:59
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 and Frame.java are given. DO NOT CHANGE THEM.
Only work on Hanoi.java.
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 getCount() and initRTS() methods and the methods implementing the stack operations: push(),
pop(), and isEmpty(), as specified in StackIF.java.
Now you are ready to implement rtsHanoi using a Run Time Stack rts.
Study lecture 2: 02-stacks slides 18 to 27.
Initially, there is one Frame [state,n,from,to] on rts. Keep popping frames until rts empty.
When popping a frame:
- if n == 0 do nothing (stack frame has already been popped)
- else if frame in state 0:
Go into state 1 by pushing [1,n,from,to]
and call hanoi(n-1,from,via) by pushing [0,n-1,from,via]
- else if in state 1
Print disk n move (see recHanoi)
and go into state 2 by pushing [2,n,from,to]
and call hanoi(n-1,via,to) by pushing [0,n-1,via,to]
- 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 Checkin webserver to exercise and submit your code. Submit your Hanoi.java file.