Tower of Hanoi C++(using recursion)

Question

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];
    }
}

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. — chris, Aug 26 '13 at 11:46
You're missing a semicolon after the class definition, that shouldn't even compile. And you indentation is, well, you have no indentation, which makes the code very hard to read. — Some programmer dude, Aug 26 '13 at 11:47
@JoachimPileborg fixed the indentation, but i did not add the semicolon — nikolas, Aug 26 '13 at 11:48
Get a modern C++ book, yours is bad. The code contains numerous errors and will be rejected by modern compilers as invalid. — Konrad Rudolph, Aug 26 '13 at 11:48
@nijansen I was wrong about the semicolon, I missread the code. — Some programmer dude, Aug 26 '13 at 11:50
Try running in a debugger, and step through the recursive calls line by line to see what happens. — Some programmer dude, Aug 26 '13 at 11:54
@chris my compiler doesn't take as a valid header somehow it does take and how would main returning int make a difference ? — Ishaan Sharma, Aug 26 '13 at 11:57
@IshaanSharma http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list See here for book recommendations — nikolas, Aug 26 '13 at 11:58
@IshaanSharma, I really, *really*, **really** suggest getting a newer compiler. And `main` is required by the standard to return an `int`. If it doesn't, it's not valid C++. — chris, Aug 26 '13 at 12:03
@chris Is DevC++ fine? also can you please elaborate on the mistakes i've made so that I can improve the program (and my skills :P). — Ishaan Sharma, Aug 26 '13 at 12:09
I found this webpage [link](http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html) It explains the algorithm which i have tried to follow closely. Any help appreciated. — Ishaan Sharma, Aug 26 '13 at 12:13
@IshaanSharma, Dev-C++ is an IDE. If you're going that route, use the newer one that got started on again and make sure the GCC compiler is the newest for best results. Anyway, just allocate variables normally instead of with pointers and `new`, use `int main`, and replace your `Stack` class usage with [`std::stack`](http://en.cppreference.com/w/cpp/container/stack), which has been tested extensively. — chris, Aug 26 '13 at 12:14
@IshaanSharma DevC++ is not a compiler but an IDE. DevC++ is using the gcc/g++ compiler and that is a really good one. Just be sure that you are using a recent version. — nikolas, Aug 26 '13 at 12:14
Work through the case with *one* disk by hand. I suggest you use pencil and paper and draw the towers as you trace the code. You should find the problem fairly quickly. — molbdnilo, Aug 26 '13 at 12:22
@molbdnilo I have edited the code and now it works! please have a look at the new `towerofhanoi` funtion — Ishaan Sharma, Aug 26 '13 at 14:23
@cpp Yes! I have changed `push()` and `pop()` . I am updating changes in the post! Also please tell me if something is wrong with the destructor — Ishaan Sharma, Aug 26 '13 at 14:56

cpp · Answer 1 · 2013-08-26T15:30:28.110

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;
}

Note that for the Tower of Hanoi, you can never put a bigger disk on top of a smaller one on any of the stacks. The stack class for ToH can, therefore, enforce this constraint, providing a more rigorous test for the algorithm. The stack class can also ensure that only the values 1..length are placed on the stack — again, a constraint specific to the ToH problem. Of course, when the algorithm is correct, the extra checking doesn't help much, but when it is broken, it can be very helpful. — Jonathan Leffler, Jan 11 '14 at 07:37

Tower of Hanoi C++(using recursion)

1 Answers1