Tower of Hanoi C++(using recursion)

18,793

This works:

//Tower of Hanoi using Stacks!
#include<iostream>
//#include<conio.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
using namespace std;

void print_elem(int elem)
{
    cout << elem << endl;       
}

class Stack{
public:
    void push(int d){t.push_back(d);}
    int pop()
    {
        int d=t.back();
        t.pop_back();
        return d;
    }
    void printstack()
    {
        for_each(t.rbegin(),t.rend(),print_elem);
    }
private:
    vector<int> t;

};

void MoveTowerofHanoi(int disk, Stack *source, Stack *temp, Stack *destination)
{
    if (disk==1)
    {
        destination->push(source->pop());
    }
    else
    {
        MoveTowerofHanoi(disk-1,source,destination,temp);
        destination->push(source->pop());
        MoveTowerofHanoi(disk-1,temp,source,destination);
    }
}

int main()
{
    int disks;
    cout<<"Enter the number of disks!"<<endl;
    cin>>disks;
    Stack* source = new Stack();
    for(int i=disks; i>0; --i) {
        source->push(i);
    }

    cout<<"Printing Source!"<<endl;
    source->printstack();
    Stack* temp = new Stack();
    Stack* destination = new Stack();
    MoveTowerofHanoi(disks,source,temp,destination);
    cout<<"Printing Destination!"<<endl;
    destination->printstack();
    delete source;
    delete temp;
    delete destination;
}
Share:
18,793

Related videos on Youtube

Ishaan Sharma
Author by

Ishaan Sharma

Updated on June 04, 2022

Comments

  • Ishaan Sharma
    Ishaan Sharma almost 2 years

    I wrote the following code as a practice exercise.
    I'm getting incorrect output when I print the destination stack.
    Can anyone please point out where I'm going wrong ?

    //Tower of Hanoi using Stacks!
    #include<iostream.h>
    #include<conio.h>
    #include<stdlib.h>
    
    class Stack
    {
    private:
        int *t;
        int length, top;
    
    public:
        Stack(int len)
        {
            length=len;
            t= new int[len];
            top=-1;
        }
    
        ~Stack()
        {
            delete []t;
        }
    
        void push(int d)
        {
            top++;
            t[top]=d;
        }
    
        int pop()
        {
            top--;
            return t[top+1];
        }
    
        void printstack()
        {
            int cur=top;
            while(cur>-1)
            {
                cout<<t[cur]<<endl;
                cur--;
            }
        }
    };
    
    void MoveTowerofHanoi(int disk, Stack *source, Stack *temp, Stack *destination)
    {
        if (disk==0)
        {
            destination->push(source->pop());
        }
        else
        {
            MoveTowerofHanoi(disk-1,source,temp,destination);
            destination->push(source->pop());
            MoveTowerofHanoi(disk-1,temp,destination,source);
        }
    }
    
    void main()
    {
        clrscr();
        int disks;
        cout<<"Enter the number of disks!"<<endl;
        cin>>disks;
        Stack* source=new Stack(disks);
        for(int i=0; i<disks; i++) {
            source->push(disks-i);
        }
        cout<<"Printing Source!"<<endl;
        source->printstack();
        Stack* temp=new Stack(disks);
        Stack* destination=new Stack(disks);
        MoveTowerofHanoi(disks,source,temp,destination);
        cout<<"Printing Destination!"<<endl;
        destination->printstack();
        getch();
    }
    

    Here's the output I'm getting:

    Enter the no. of disks!  
    3  
    Printing Source!  
    1  
    2  
    3  
    Printing Destination!  
    -4
    

    After editing, the code looks like this:

        void MoveTowerofHanoi(int disk, Stack *source, Stack *destination, Stack *temp)
    {
        if (disk==1)
        {
            destination->push(source->pop());
        }
        else
        {
            MoveTowerofHanoi(disk-1,source,temp,destination);
            destination->push(source->pop());
            MoveTowerofHanoi(disk-1,temp,destination,source);
        }
    }
    

    the first mistake was:

    void MoveTowerofHanoi(int disk, Stack *source, Stack *temp, Stack *destination)
    

    the second was:

    if (disk==0)
    

    Many thanks to all for helping!


    Changes made to stack class:

    void push(int d)
    {
         if(top<length-1)
        {
        top++;
        t[top]=d;
        }
    
    }
    
    int pop()
    {
        if(top>-1)
        {
        top--;
        return t[top+1];
        }
    }
    
    • chris
      chris over 10 years
      You definitely don't need any pointers in main, which must return int, not void, and if the point is the Towers of Hanoi, why can't you just use std::stack? Also, iostream.h is not, and has never been, a standard header.
    • Konrad Rudolph
      Konrad Rudolph over 10 years
      Get a modern C++ book, yours is bad. The code contains numerous errors and will be rejected by modern compilers as invalid.
    • Some programmer dude
      Some programmer dude over 10 years
      Try running in a debugger, and step through the recursive calls line by line to see what happens.
    • nikolas
      nikolas over 10 years
      @IshaanSharma stackoverflow.com/questions/388242/… See here for book recommendations