#include <iostream>
#include "stack.h"

using namespace std;

typedef struct {
  int n;
  char src;
  char dest;
  char spare;
} goal;

int main(void) {
  int n;
  Stack<goal> s;
  goal g;

  //get the number of discs
  cout <<"How many discs? ";
  cin >> n;

  //create the initial goal
  g.n = n;
  g.src = 'A';
  g.dest = 'C';
  g.spare = 'B';

  //put the intial goal on the stack
  s.push(g);

  while(!s.isEmpty()) {
    //pull the current goal off the stack
    g = s.pop();

    //base condition
    if(g.n==1) {
      //do something
      cout << "(" << g.src << "," << g.dest << ")" << endl;
      //skip the rest
      continue;
    }

    //recurse (reverse order)
    goal sg;
    sg.n = g.n-1;
    sg.src = g.spare;
    sg.dest = g.dest;
    sg.spare = g.src;
    s.push(sg);

    sg.n = 1;
    sg.src = g.src;
    sg.dest = g.dest;
    sg.spare = g.spare;
    s.push(sg);

    sg.n = g.n-1;
    sg.src = g.src;
    sg.dest = g.spare;
    sg.spare = g.dest;
    s.push(sg);
    
  }
}