/* 

FILE:  TowersOfHanoi.c

THIS PROGRAM IS TO IMPLEMENT THE TOWERS OF HANOI 
PROGRAM PREVOUSLY DISCUSSED, BUT WITH PICTURES                   
              
 PROGRAMMER:   RiNN                        
 DATE:  Feburary 24,  1998 
 INSTRUCTOR:   Dr. Robert Sczech           
 CLASS: CS102:S98                    

*/

#include               //iostream HEADER
#include                 //stblib   HEADER
#include                 //assert   HEADER
#include                  //ctype    HEADER

struct node {
  int data;
  node *next;
};
typedef node *stack;

int Pop(stack &s);                  //pop stack s
void Push(stack &s, int value);     //push value onto stack s
void Init(stack &s);                //initialize stack s
void PrintStacks();                 //print stacks: debugging
void PrintStackPix();              //print picture in height N
int  Locate(stack s, int n);        //return nth element from top of s, 0 if n>depth(s)
int  Depth(stack s);                //return depth of s
void PrintStack(stack s);           //print stack s
void StackMove(char source, char destination); //move a single disk
void Move(int n, char source, char destination, char helper);

stack A, B, C;                       //GLOBAL stack variables

int N;                               //GLOBAL variable for total number of disks



int main()
{cout << "\t Enter number of disks to move:  ";
 cin  >> N;            //number of disks to move
 cout << N << endl;

 Init(A); Init(B); Init(C);

 for (int i=1; i <=N; i++) Push(A, i);

 PrintStackPix();       //print initial setup
 Move(N, 'A', 'B','C'); //move N disks from peg A to peg B
 return 0;
}

void Move(int n, char source, char destination, char helper)
{ if(n>1) 
     Move(n-1, source, helper, destination);
  cout <<  "Move a disk from peg " << source
       << " to peg " << destination << endl;
  StackMove(source, destination);
  PrintStackPix();
  if(n>1)
      Move(n-1, helper, destination, source);    
}

void Init(stack &s){  s = NULL; }

void PrintStackPix()
{int dA=Depth(A);
 int dB=Depth(B);
 int dC=Depth(C);

 for(int i=N; i>=1; i--){
   if (dA>=i) cout << Locate(A,(dA+1)-i) <<" ";
   else cout << "  ";
   if(dB>=i)  cout << Locate(B, (dB+1)-i) <<" ";
   else cout << "  ";
   if(dC>=i)  cout << Locate(C, (dC+1)-i) << endl;
   else cout << endl;
 }
 cout <<"A " << "B " << "C" << endl;
}

void Push(stack &s, int value){
  node *newstack = new node;

  assert (newstack != NULL); // CHECK STACK UNDERFLOW

  newstack -> data = value;
  newstack -> next = s;
  s = newstack;
}

int Depth(stack s){
  int count=0;
  while (s!=NULL){
    count ++;
    s = s ->next;
  }
  return count;
}

void PrintStacks()
{ PrintStack(A);
  cout << 'A' <Depth(s)))
    return 0;
  else
    for (int i=1;i next;
 
 return temp -> data;
}

void StackMove (char source, char destination)
{ int value;

  if (source == 'A')
   value = Pop(A);
  else if (source == 'B')
   value = Pop(B);
  else
   value = Pop(C);
  if(destination == 'A')
   Push(A,value);
  else if(destination == 'B')
   Push(B,value);
  else
   Push(C,value);
}

void PrintStack (stack s)
{ if (s!=NULL){
    for (int i =Depth(s); i>=1; i--)
      cout << Locate(s, 1+Depth(s)-i) << endl;
  }
}

int  Pop(stack &s){
  assert ( s!=NULL ); // CHECK STACK UNDERFLOW

  int value = s -> data;
  node *oldstack = s;
  s = s -> next;
  delete oldstack;
  return value;
}