// From the software distribution accompanying the textbook
// "A Practical Introduction to Data Structures and Algorithm Analysis,
// Third Edition (C++)" by Clifford A. Shaffer.
// Source code Copyright (C) 2007-2011 by Clifford A. Shaffer.
// A program to generate the moves needed to solve the Towers of Hanoi
// problem.
// There are two versions. One is a simple recursive implementation.
// The other replaces the recursion with a stack.
#include "book.h"
typedef int Pole; // A simple definition for a pole type
// What to do when we "move" a disk: Print it out
#define move(X, Y) cout << "Move " << (X) << " to " << (Y) << endl
// A simple recursive function that generates the solution steps
void TOH(int n, Pole start, Pole goal, Pole temp) {
if (n == 0) return; // Base case
TOH(n-1, start, temp, goal); // Recursive call: n-1 rings
move(start, goal); // Move bottom disk to goal
TOH(n-1, temp, goal, start); // Recursive call: n-1 rings
}
// Now we show how to do this by replacing recursion with a stack.
// Include the standard stack template implementation
#include "astack.h"
// Now, we need to define the objects to be put on the stack
// TOHobj describes an operation to perform.
// It has 5 members: Operation type, number of disks to operate on,
// and the designations (start, goal, temp) for the three poles.
// There are two operation types.
// (i) DOTOH describes what originally was a recursive call.
// It defines the pole order and the number of disks to be moved.
// (ii) DOMOVE describes a move operation.
// It defines the start and goal pole for the disk to be moved.
class TOHobj { // An operation object
public:
TOHop op; // This operation type
int num; // How many disks
Pole start, goal, tmp; // Define pole order
// DOTOH operation constructor
TOHobj(int n, Pole s, Pole g, Pole t) {
op = DOTOH; num = n;
start = s; goal = g; tmp = t;
}
// DOMOVE operation constructor
TOHobj(Pole s, Pole g)
{ op = DOMOVE; start = s; goal = g; }
};
// This is the stack version of the function that solves the TOH problem
void TOH(int n, Pole start, Pole goal, Pole tmp,
Stack& S) {
S.push(new TOHobj(n, start, goal, tmp)); // Initial
TOHobj* t;
while (S.length() > 0) { // Grab next task
t = S.pop();
if (t->op == DOMOVE) // Do a move
move(t->start, t->goal);
else if (t->num > 0) {
// Store (in reverse) 3 recursive statements
int num = t->num;
Pole tmp = t->tmp; Pole goal = t->goal;
Pole start = t->start;
S.push(new TOHobj(num-1, tmp, goal, start));
S.push(new TOHobj(start, goal));
S.push(new TOHobj(num-1, start, tmp, goal));
}
delete t; // Must delete the TOHobj we made
}
}
int main(int argc, char** argv) {
Assert(argc == 2, "Usage: toh ");
int n = atoi(argv[1]);
cout << "Doing recursive version on " << n << " disks\n";
TOH(n, 1, 3, 2);
cout << endl;
AStack S(2*n+1); // Make a stack with just enough room
cout << "Now, do non-recursive version\n";
TOH(n, 1, 3, 2, S);
return 0;
}