The Problem: The Towers of Hanoi

[Yousra]

Hey,
I am working on my assignment and I tried to run the program and I get build in errors, So first this is my problem :

In the Towers of Hanoi game, there are 3 pegs (A , B , C) and N disks with varying sizes that can be stacked on a peg. The objective is to move all the disks from peg (A) to peg (C), probably by using the auxiliary peg (B). At any moment, no larger peg can be placed on top of a smaller one.

Algorithm
Obviously, this is a recursive problem that can be solved by the following recursive algorithm:

Towers (N, Source , Target , Aux)
	{
		if N = 1 move disk 1 from Source to Target directly
		else 
		{
			Call Towers to move N-1 disks from Source to Aux via Target
			Move disk N from Source to Target directly
			Call Towers to move N-1 disks from Aux to Target via Source
		}
	}

Required Implementations
Develop a program using the above algorithm to simulate the Towers of Hanoi game. Number the disks 1,2,3,…,N in ascending order of their size. Use a stack for each peg to represent its disk content at any moment. Display the stack to see each move until all disks have been moved from peg A to peg C.


And this is my Program, if you could help me figure out the errors, that would be great :

#include <iostream>
#include"Stackt.h"
#include"Stackt.cpp"
using namespace std;
//------------------------Globals--------------------------------------------------------
int count= 0; //Counter to display the number of moves.
Stackt<int> *Source ; //Pointer to each stack.
Stackt<int> *Target; 
Stackt<int> *Auxillary; 
//------------------------Functions------------------------------------------------------
void move( Stackt<int> *f,Stackt<int> *s);
void Towers (int n, Stackt<int> *s, Stackt<int> *t, Stackt<int> *a);
//---------------------------------------------------------------------------------------
void main()
{
	int N;// Number of discs.
	Stackt<int> S, T, A;// 3 pegs that are you going to use.
	cout<<"\n\t **************   TOWERS OF HANOI   **************\n"<<endl;
	cout<<" Enter the number of discs ... you want to play with? ";
	cin>>N; //Input number of disks
	if (N<0)
	{
		cout<<"The number you entered is invalid...Please reneter!"<<endl;	
		cin>>N;
	}
	cout<<endl;
	for(int i=1; i<=N; i++)//Fill the source peg with the number of discs.
	{
		S.push(i);
	}
	
    Source = &S ; // point to the source peg (stack)
    Target = &T; // point to the target peg (stack)    
    Auxillary = &A;// point to the auxillary peg (stack)
	cout<<count<<") source peg: ";
	S.display(); // display the components of the source peg at the beginning
	cout<<endl;
	cout<<" auxillary peg: ";
	A.display(); //to display the components of the auxillary peg at the beginning
	cout<<endl;
	cout<<" target peg: ";
	T.display(); //to display the components of the target peg at the beginning
	cout<<endl<<endl;
	Towers( N, Source, Target, Auxillary); //to call the recursive function that will move the disks 
	system ("PAUSE");
	
}
//-----------------------------------------------------------------------------------------------------------
void move( Stackt<int>* f,Stackt<int>* s) //This will move an element from first stack to the second stack
{ 
	int e; // element that will be removed from one stack and added to the other
	f->pop(e); //to remove the top element from the first stack
	s->push(e); //to add the removed element to the second stack
}
//-------------------------------------------------------------------------------------------------------------
void Towers (int n, Stackt<int>* s, Stackt<int>* t, Stackt<int>* a) //This is a recursive function.
{
	if(n==1) //if there is only one disk, move this disk from the source to the target directly
	{
		move(s,t); //moves the disk from the source to the target directly
		count++; //increment the number of moves
		cout<<count<<") source peg: ";
		Source->display(); //to display the source peg
		cout<<endl;
		cout<<" auxillary peg: ";
		Auxillary->display(); //to display the auxillary peg
		cout<<endl;
		cout<<" target peg: ";
		Target->display(); //to display the target peg
		cout<<endl<<endl;

	}
	else //a recurisve function in order to move the disks
	{
		Towers(n-1,s,a,t); //to move N-1 disks from the source to the auxillary with the help of the target peg
		move(s,t);//to move the last disk to the target peg directly		
		count++; //increment the number of steps before displaying
		cout<<count<<") source peg: ";
		Source->display(); //show the source peg
		cout<<endl;
		cout<<" auxillary peg: "; 
		Auxillary->display(); //show the auxillary peg
		cout<<endl;
		cout<<" target peg: ";
		Target->display(); //show the target peg
		cout<<endl<<endl;
		Towers(n-1,a,t,s); //to move N-1 disks from the auxillary to the target with the help of the source peg
	}
	
}

And this is the stack file

// File: Stackt.cpp
// Stack template class implementation

#include <iostream>
using namespace std;


// Constructor with argument, size is nelements, default is 128
template <class Type>
Stackt<Type>::Stackt(int nelements)   
{  MaxSize = nelements; stack = new Type[MaxSize];  top = -1; }  

// Copy Constructor
template <class Type>
Stackt <Type>::Stackt(const Stackt<Type> &original)
	:MaxSize(original.MaxSize), top(original.top) 
{
	stack = new Type[MaxSize];
	for (int i = 0; i <= top; i++) stack[i] = original.stack[i];
}


// Destructor
template <class Type>
Stackt<Type>::~Stackt()
{ delete [] stack;}

// Push
template <class Type>
void Stackt<Type>::push(Type v)
{ 
	if(stackIsFull()) cout << "Stack Overflow" << endl; 
	else stack[++top] = v; 
}

// Pop
template <class Type>
void Stackt<Type>::pop(Type &v)
{
	if(stackIsEmpty()) cout << "Stack Underflow" << endl; 
	else v = stack[top--]; 
}

// Retrieve stack top without removing it
template <class Type>
void Stackt<Type>::stackTop(Type &v) const
{
	if(stackIsEmpty()) cout << "Stack Underflow"; 
	else v = stack[top]; 
}

// Test for Empty stack
template <class Type>
bool Stackt<Type>::stackIsEmpty() const
{ return (top < 0); }

// Test for Full stack
template <class Type>
bool Stackt<Type>::stackIsFull() const
{ return (top >= (MaxSize-1)); }

[TheDestroyer]

Mar7aba ya Yousra :-)

Actually I don't understand the question. What kind of help are you looking for?

P.S.: Please use the wrapper [code][ /code] for your code to make it easily readable, and use indents as well.

[Yousra]

Actually my question is that I can't correct my errors so that my program would run, so if you could tell me what are the errors that would be great and thans for the ip, it is the my first time to post a question ;)

[TheDestroyer]

You didn't post your Stackt.h. So I can't really compile your code here.

OK, there are many issues in your code:

1. You don't include .cpp files; i.e., #include "Stackt.cpp" is totally wrong. You just add them to your compile argument as source files. What compiler are you using? are you compiling with Windows or Linux? are you typing your compile commands manually? or are you using an IDE to manage your files? please let me know so that I can tell you what the correct method is to pass your code to the compiler.

2. You're using templates, which means that you can't separate cpp implementations from your header Stackt.h file. You can actually do that with what's called the "separation model", but that's fairly complicated and advanced. For now, just put your implementations of your class Stackt's methods in the header file.

3. Just a hint, not really a big deal, and many compilers accept it the way you did it, but it doesn't comply to the new standard. When you use simple templates, don't use the word class, but typename. So a template has to look like this for you:

template <typename Type>

class parameters are used only in template template parameters, so you don't really need that right now.

Post your header file, after fixing those problems, and let's see if your program works :-)

[Yousra]

First I am using visual studio, and secong u have been helpful so much but I just figured out that I was trying to do it in a complicated way so I changed my whole alogrithm
First that is my header file of stack

/ File: Stackt.h
// Stack template class definition. 
// Dynamic array implementation 

#ifndef STACKT_H           
#define STACKT_H           

template <class Type>

class Stackt
{
   public:
      
      Stackt(int nelements = 128);		// Constructor
	  Stackt (const Stackt<Type> &);	// Copy Constructor
	  ~Stackt();						// Destructor

	  // Member Functions	      
      void push(Type );				// Push
      void pop(Type &);				// Pop
	  void stackTop(Type &) const;	// retrieve top
      bool stackIsEmpty() const;	// Test for Empty stack
      bool stackIsFull() const;		// Test for Full stack

   private:
      Type *stack;					// pointer to dynamic array
	  int top, MaxSize;				

}; 

#endif // STACKT_H
#include "Stackt.cpp" 

and the cpp file of stack

// File: Stackt.cpp
// Stack template class implementation

#include <iostream>
using namespace std;


// Constructor with argument, size is nelements, default is 128
template <class Type>
Stackt<Type>::Stackt(int nelements)   
{  MaxSize = nelements; stack = new Type[MaxSize];  top = -1; }  

// Copy Constructor
template <class Type>
Stackt <Type>::Stackt(const Stackt<Type> &original)
	:MaxSize(original.MaxSize), top(original.top) 
{
	stack = new Type[MaxSize];
	for (int i = 0; i <= top; i++) stack[i] = original.stack[i];
}


// Destructor
template <class Type>
Stackt<Type>::~Stackt()
{ delete [] stack;}

// Push
template <class Type>
void Stackt<Type>::push(Type v)
{ 
	if(stackIsFull()) cout << "Stack Overflow" << endl; 
	else stack[++top] = v; 
}

// Pop
template <class Type>
void Stackt<Type>::pop(Type &v)
{
	if(stackIsEmpty()) cout << "Stack Underflow" << endl; 
	else v = stack[top--]; 
}

// Retrieve stack top without removing it
template <class Type>
void Stackt<Type>::stackTop(Type &v) const
{
	if(stackIsEmpty()) cout << "Stack Underflow"; 
	else v = stack[top]; 
}

// Test for Empty stack
template <class Type>
bool Stackt<Type>::stackIsEmpty() const
{ return (top < 0); }

// Test for Full stack
template <class Type>
bool Stackt<Type>::stackIsFull() const
{ return (top >= (MaxSize-1)); }

and this my application file :

#include <iostream>
#include"Stackt.h"
using namespace std;
//------------------------Globals--------------------------------------------------------
int count= 0; //Counter to display the number of moves.
//------------------------Functions------------------------------------------------------
void move( Stackt<int> ,Stackt<int> );
void Towers (int n, Stackt<int> &, Stackt<int> &, Stackt<int> & );
void Display (int, Stackt <int> & , Stackt<int> & ,Stackt <int> &);// function to display the stacks 
//---------------------------------------------------------------------------------------
int main()
{
	
	
	Stackt<int> source;// create 3 empty stacks
	Stackt<int> target;
	Stackt<int> aux;

	int N;// Number of discs.

	cout<<"\n\t **************   TOWERS OF HANOI   **************\n"<<endl;
	cout<<" WELCOME.....:" << endl;
	cout<<" Please Enter the number of discs ... you want to play with? "<<endl<<endl;
	
	cin>>N;//Input number of disks
	cout<<endl;
	while(N<0)//to make sure that the user didnot enter an invalid number
		{
			cout<<"The number you entered is invalid...Please reneter!"<<endl;
			cin>>N;
			cout<<endl;
		}
	
	for(int i=1; i<=N; i++)//Fill the source peg with the number of discs.
	{
		source.push(i);
	}
	
	
	Towers(N, source, target, aux); //to call the recursive function that will move the discs
	Display (N, source, target,aux);

	
	cin.clear(); 
	cin.ignore(255, '\n'); 
	cin.get();
	return 0;
	
}
//-----------------------------------------------------------------------------------------------------------
void move( Stackt<int> s,Stackt<int> t) //This will move an element from first stack to the second stack
{ 
	int e; // element that will be removed from one stack and added to the other
			
	s.pop(e);//pop from source
			
	t.push(e);//and move to target
	
}
//----------------------------------------------------------------------------------------
void Display (int N, Stackt <int> & source , Stackt<int> & target ,Stackt <int> & aux)
{
	Stackt<int> S;// create temporarliy stack A
	Stackt<int> T;// create temporarliystack B
	Stackt<int> A;// create temporarliy stack C
	for(int i=1; i<=N; i++)
	{
		source.pop(i);//moves the disc from source
		S.push(i);//to the temporarily stack to dispaly it
		cout<<"Source Peg:"<<&S<<endl;

		target.pop(i);//moves the disc from source
		T.push(i);//to the temporarily stack to dispaly it
		cout<<"Target Peg:"<<&T<<endl;

		aux.pop(i);//moves the disc from source
		A.push(i);//to the temporarily stack to dispaly it
		cout<<"Auxillary Peg:"<<&A<<endl;
	}  
{
//-------------------------------------------------------------------------------------------------------------
void Towers(int N, Stackt<int> & s, Stackt<int> & t, Stackt<int> & a) //This is a recursive function.
{
	if(N==1) //if there is only one disk, move this disk from the source to the target directly
	{
		move(s,t); //moves the disk from the source to the target directly
		cout<<"You have entered one disc..."<<endl;
		cout<<"It moves direclty from the source to the target"<<endl;

		count++; //increment the number of moves

		cout<<count<<endl;
		Display (N, s, t,a);

	}
	else if (N>1) //a recurisve function in order to move the disks
	{
		Towers(N-1,s,a,t); //to move N-1 disks from the source to the auxillary with the help of the target peg
		move(s,t);//to move the last disk to the target peg directly		
		count++; //increment the number of steps before displaying
		cout<<count<<endl;
		Towers(N-1,a,t,s); //to move N-1 disks from the auxillary to the target with the help of the source peg
			
		Display ( N, source, target, aux);
	}
	
}

and when I corrected all the errors except 2 errors
First on is at the function towers C2601 : local function defintions are illegal and the second one is C107 and it appears at the first of the program

so what do you think the errors are ??

Thanks in advance

[TheDestroyer]

OK, my friend. Please read my previous resolution carefully, about templates:

You're using templates, which means that you can't separate cpp implementations from your header Stackt.h file. You can actually do that with what's called the "separation model", but that's fairly complicated and advanced. For now, just put your implementations of your class Stackt's methods in the header file.

You didn't fix this. You have to move your Stackt.cpp implementations to your header files, because you're using templates. I did it for you, anyway.

That was the first error, the second one is at line 80, where you wrote { rather than } to close your function.

The third one is the function Display at line 104. source, target and aux are not defined. Please define them to have function compile. You may define them by passing them to the function Tower. I commented that line till you fix that problem. Here's your new code:

#include <iostream>
#include "Stackt.h"
using namespace std;
//------------------------Globals--------------------------------------------------------
int count= 0; //Counter to display the number of moves.
//------------------------Functions------------------------------------------------------
void move( Stackt<int> ,Stackt<int> );
void Towers(int N, Stackt<int> & s, Stackt<int> & t, Stackt<int> & a); //This is a recursive function.
void Display (int, Stackt <int> & , Stackt<int> & ,Stackt <int> &);// function to display the stacks
//---------------------------------------------------------------------------------------
int main()
{


    Stackt<int> source;// create 3 empty stacks
    Stackt<int> target;
    Stackt<int> aux;

    int N;// Number of discs.

    cout<<"\n\t **************   TOWERS OF HANOI   **************\n"<<endl;
    cout<<" WELCOME.....:" << endl;
    cout<<" Please Enter the number of discs ... you want to play with? "<<endl<<endl;

    cin>>N;//Input number of disks
    cout<<endl;
    while(N<0)//to make sure that the user didnot enter an invalid number
        {
            cout<<"The number you entered is invalid...Please reneter!"<<endl;
            cin>>N;
            cout<<endl;
        }

    for(int i=1; i<=N; i++)//Fill the source peg with the number of discs.
    {
        source.push(i);
    }


    Towers(N, source, target, aux); //to call the recursive function that will move the discs
    Display (N, source, target,aux);


    cin.clear();
    cin.ignore(255, '\n');
    cin.get();
    return 0;

}
//-----------------------------------------------------------------------------------------------------------
void move( Stackt<int> s,Stackt<int> t) //This will move an element from first stack to the second stack
{
    int e; // element that will be removed from one stack and added to the other

    s.pop(e);//pop from source

    t.push(e);//and move to target

}
//----------------------------------------------------------------------------------------
void Display (int N, Stackt <int> & source , Stackt<int> & target ,Stackt <int> & aux)
{
    Stackt<int> S;// create temporarliy stack A
    Stackt<int> T;// create temporarliystack B
    Stackt<int> A;// create temporarliy stack C
    for(int i=1; i<=N; i++)
    {
        source.pop(i);//moves the disc from source
        S.push(i);//to the temporarily stack to dispaly it
        cout<<"Source Peg:"<<&S<<endl;

        target.pop(i);//moves the disc from source
        T.push(i);//to the temporarily stack to dispaly it
        cout<<"Target Peg:"<<&T<<endl;

        aux.pop(i);//moves the disc from source
        A.push(i);//to the temporarily stack to dispaly it
        cout<<"Auxillary Peg:"<<&A<<endl;
    }
}
//-------------------------------------------------------------------------------------------------------------
void Towers(int N, Stackt<int> & s, Stackt<int> & t, Stackt<int> & a) //This is a recursive function.
{
    if(N==1) //if there is only one disk, move this disk from the source to the target directly
    {
        move(s,t); //moves the disk from the source to the target directly
        cout<<"You have entered one disc..."<<endl;
        cout<<"It moves direclty from the source to the target"<<endl;

        count++; //increment the number of moves

        cout<<count<<endl;
        Display (N, s, t,a);

    }
    else if (N>1) //a recurisve function in order to move the disks
    {
        Towers(N-1,s,a,t); //to move N-1 disks from the source to the auxillary with the help of the target peg
        move(s,t);//to move the last disk to the target peg directly
        count++; //increment the number of steps before displaying
        cout<<count<<endl;
        Towers(N-1,a,t,s); //to move N-1 disks from the auxillary to the target with the help of the source peg

        //Display ( N, source, target, aux);
    }

}

// File: Stackt.cpp
// Stack template class implementation 

Yes, Stackt.cpp is empty, since you don't have any non-templatised functions.

And finally the header file:

// File: Stackt.h
// Stack template class definition.
// Dynamic array implementation

#ifndef STACKT_H
#define STACKT_H

template <class Type>

class Stackt
{
   public:

      Stackt(int nelements = 128);		// Constructor
      Stackt (const Stackt<Type> &);	// Copy Constructor
      ~Stackt();						// Destructor

      // Member Functions
      void push(Type );				// Push
      void pop(Type &);				// Pop
      void stackTop(Type &) const;	// retrieve top
      bool stackIsEmpty() const;	// Test for Empty stack
      bool stackIsFull() const;		// Test for Full stack

   private:
      Type *stack;					// pointer to dynamic array
      int top, MaxSize;

};

// Constructor with argument, size is nelements, default is 128
template <class Type>
Stackt<Type>::Stackt(int nelements)
{  MaxSize = nelements; stack = new Type[MaxSize];  top = -1; }

// Copy Constructor
template <class Type>
Stackt <Type>::Stackt(const Stackt<Type> &original)
    :MaxSize(original.MaxSize), top(original.top)
{
    stack = new Type[MaxSize];
    for (int i = 0; i <= top; i++) stack[i] = original.stack[i];
}


// Destructor
template <class Type>
Stackt<Type>::~Stackt()
{ delete [] stack;}

// Push
template <class Type>
void Stackt<Type>::push(Type v)
{
    if(stackIsFull()) cout << "Stack Overflow" << endl;
    else stack[++top] = v;
}

// Pop
template <class Type>
void Stackt<Type>::pop(Type &v)
{
    if(stackIsEmpty()) cout << "Stack Underflow" << endl;
    else v = stack[top--];
}

// Retrieve stack top without removing it
template <class Type>
void Stackt<Type>::stackTop(Type &v) const
{
    if(stackIsEmpty()) cout << "Stack Underflow";
    else v = stack[top];
}

// Test for Empty stack
template <class Type>
bool Stackt<Type>::stackIsEmpty() const
{ return (top < 0); }

// Test for Full stack
template <class Type>
bool Stackt<Type>::stackIsFull() const
{ return (top >= (MaxSize-1)); }

#endif // STACKT_H 

[Yousra]

Thank you so much :D
You helped me out a lot ;)

[TheDestroyer]

You're welcome :-)

Please mark the article as solved.