C++

Forum

 
 
Problem with stack

spinach999 (5)
Hello, I am trying to write a Tower of Hanoi program using exceptions. I was a little unsure about how to store the disks in each tower so I used stack/LIFO. But for some reason when I run the code, it gives me an error that says "Signal: killing". I'm assuming that I am making a mistake when creating the towers and the problem lies in lines 34 and 40. I'm quite new to the topic of stacks so I would really like to know how to fix it. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
 
#include <iostream>
#include <string>
#include <exception>
#include <stack>

using namespace std;

//exception class changes the message for each error 
class Exception 
{ 
public:
  string message;
  Exception(string message) { this->message = message; }
};

class OutOfRangeException : public Exception {
public:
  OutOfRangeException() : Exception("Disk number/Tower number is out of the range 1 - 3"){};
};

class IncorrectSizeException : public Exception {
public:
  IncorrectSizeException() : Exception("Disked moved is larger than disk in the tower"){};
};

class NoDisksException : public Exception {
public:
  NoDisksException() : Exception("There are no disks in the source tower inputted"){};
};

//tower class stores all the information of the towers 
class Tower {
public:
  stack <int> disks; 
  string name;

  Tower(string _name) 
  {
    name = _name;
  }

  int Initialize() 
  { 
  for (int i = 3; i > 0; i--) 
    disks.push(i);
  }   

 int Add(int diskNum)
  {
    disks.push(diskNum);
  }

  void Shift(int diskNum, Tower toTower) 
  {
    if (disks.empty())
      throw NoDisksException();
    else if (diskNum > disks.top())
      throw IncorrectSizeException();
    else
    {
      toTower.Add(diskNum);
      disks.pop();
    }
  }

  void Print() 
  {
     cout << name << ": ";
    while (!disks.empty())
      cout<< " "<< disks.top();
  }
};

int main() 
{
  cout << "Get the disks from tower 1 to tower 3 in only 7 moves" << endl;

  Tower t1 = Tower("tower 1");
  t1.Initialize();
  Tower t2 = Tower("tower 2");
  Tower t3 = Tower("tower 3");
  int counter = 0;
  
  t1.Print();
  t2.Print();
  t3.Print();
  try 
  {
    do
    {
      int towerNum1, towerNum2, diskNum;
      cout << "\nWhich tower do you want to move the disk from: ";
      cin >> towerNum1;
      
      cout << "\nGive disk number: ";
      cin >> diskNum;
      
      cout << "\nWhich tower do you want to move the disk to: ";
      cin >> towerNum2;

      if(3 < towerNum1 || towerNum1 < 1 || 3 < towerNum2 || towerNum2 < 1 || 3 < diskNum || diskNum < 1)
        throw OutOfRangeException();

      if(towerNum1 == 1)
      {
        if(towerNum2 == 1)
          continue;
        else if(towerNum2 == 2)
          t1.Shift(diskNum, t2);
        else if(towerNum2 == 3)
          t1.Shift(diskNum, t3);
      }
      if(towerNum1 == 2)
      {
        if(towerNum2 == 1)
          t2.Shift(diskNum, t1);
        else if(towerNum2 == 2)
          continue;
        else if(towerNum2 == 3)
          t2.Shift(diskNum, t3);
      }
      if(towerNum1 == 3)
      {
        if(towerNum2 == 1)
          t3.Shift(diskNum, t1);
        else if(towerNum2 == 2)
          t3.Shift(diskNum, t2);
        else if(towerNum2 == 3)
          continue;
      }
      counter++;
    }while (counter < 7); 
    
    t1.Print();
    t2.Print();
    t3.Print();
  }
    
  catch (IncorrectSizeException e) 
  {
    cout << e.message << endl;
  } 
  catch (OutOfRangeException e) 
  {
    cout << e.message << endl;
  } 
  catch (NoDisksException e) 
  {
    cout << e.message << endl;
  }
  
  return 0;
}
kbw (9488)
If you're going to use 3 distinct "Tower" objects, then each Tower is a stack, which is what you have.

But the initialization is to place the disks on one tower, run the algorithm, and watch them move. But you haven't done that, you've initialized each tower with 3 disks.

Think procedurally; what are the steps you need to follow, then do that. The Object Oriented thing you're doing is leading to more complexity.
seeplus (6591)
L42 Initialize() should be void.
L48 Add() should be void

function Print(). This is an infinite loop if the stack is not initially empty. If not empty then it will continuously display the top entry - as top() does not remove the entry. There are no standard methods to access a std::stack entries (eg like a vector). To display a std::stack, then something like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
...
	void Print() {
		prtStack(disks);
		std::cout << '\n';
	}

private:
	stack <int> disks;
	string name;

	static void prtStack(std::stack<int>& disks) {
		if (disks.empty()) {
			return;
		}

		const int topElement {disks.top()};

		disks.pop();
		std::cout << topElement << ' ';
		prtStack(disks);
		disks.push(topElement);
	}


which recursively gets the top element, pops it, displays it. Once all displayed, it pushes the pop-ed elements back. For a large stack this can consume excessive time.

NB If you want the elements to be printed in the other order, just switch the recursive call and the std::cout statement.
Last edited on
seeplus (6591)
However, to display a stack without changing it, there is a 'hack'.

std::stack is based upon another container. By default this is std::dequeue but an alternative can be specified when the stack is created.

The stack contents is actually a container of this type within the std::stack class as a protected member (called c). Hence any class derived from std::stack can have access to it.

See https://en.cppreference.com/w/cpp/container/stack

Thus you can do something like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
#include <stack>
#include <iostream>
#include <initializer_list>

template <typename T>
class myStack : public std::stack<T> {
public:
	using std::stack<T>::stack;

	myStack(std::initializer_list<T> il) {
		for (const auto& i : il)
			this->push(i);
	}

	void display() const {
		for (auto it {this->c.crbegin()}; it != this->c.crend(); ++it)
			std::cout << *it << ' ';

		std::cout << '\n';
	}
};

int main() {
	myStack<int> my {1, 2, 3};

	my.display();
}


which displays:


3 2 1


To display in the other order, just replace crbegin()/crend() with cbegin()/cend()
Last edited on
kigar64551 (814)
To solve the "Tower of Hanoi" problem, think about this: Moving n discs from tower "A" to tower "B" can be broken down into moving the top n-1 discs from "A" to "C", then moving the one remaining (biggest) disc from "A" to "B", and finally moving the other n-1 discs (which we previously moved to "C") back from "C" to "B".

Okay, but how exactly do we move the stack of n-1 discs from one tower (source tower) to another tower (destination tower)? Well, just recursively apply the same idea as before: First move the n-2 top discs from the source tower to the other tower, then move the one remaining disc (i.e. the n-1'th disc) from source tower to the destination tower, finally move the n-2 discs from the other tower to the destination tower. Et voilà!

This way you can break things down recursively until you only ever need to move a single disc at a time :-)
Last edited on
seeplus (6591)
Well to solve it via code, as opposed to asking for moves (as per the OP), then possibly:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
#include <iostream>

class Hanoi {
public:
	Hanoi() = default;
	Hanoi(unsigned no_) : no(no_) {}

	unsigned solve() {
		cnt = 0;
		moveDisks(no, 1, 3, 2);
		return cnt;
	}

private:
	unsigned no {3};
	unsigned cnt {};

	void moveDisks(int count, unsigned needle1, unsigned needle3, unsigned needle2) {
		if (count > 0) {
			moveDisks(count - 1, needle1, needle2, needle3);
			std::cout << "Move disk " << count << " from " << needle1 << " to " << needle3 << '\n';
			++cnt;
			moveDisks(count - 1, needle2, needle3, needle1);
		}
	}
};

int main() {
	constexpr unsigned no {4};
	Hanoi h(no);

	std::cout << "For " << no << " disks\n";

	const auto cnt {h.solve()};

	std::cout << "Took " << cnt << " moves\n";
}



For 3 disks
Move disk 1 from 1 to 3
Move disk 2 from 1 to 2
Move disk 1 from 3 to 2
Move disk 3 from 1 to 3
Move disk 1 from 2 to 1
Move disk 2 from 2 to 3
Move disk 1 from 1 to 3
Took 7 moves

For 4 disks
Move disk 1 from 1 to 2
Move disk 2 from 1 to 3
Move disk 1 from 2 to 3
Move disk 3 from 1 to 2
Move disk 1 from 3 to 1
Move disk 2 from 3 to 2
Move disk 1 from 1 to 2
Move disk 4 from 1 to 3
Move disk 1 from 2 to 3
Move disk 2 from 2 to 1
Move disk 1 from 3 to 1
Move disk 3 from 2 to 3
Move disk 1 from 1 to 2
Move disk 2 from 1 to 3
Move disk 1 from 2 to 3
Took 15 moves

Last edited on
seeplus (6591)
Without using exceptions, but displaying the 3 towers horizontal, then possibly something like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
#include <stack>
#include <iostream>
#include <iomanip>

class Tower : public std::stack<size_t> {
public:
	using std::stack<size_t>::stack;

	size_t operator[](size_t ind) const {
		return c[ind];
	}

	void init(size_t nod) {
		for (size_t d {nod}; d > 0; --d)
			push(d);
	}

	bool correct(size_t nod) {
		if (size() != nod)
			return false;

		for (size_t d {0}; d < nod; ++d)
			if (c[d] != nod - d)
				return false;

		return true;
	}
};

void display(const Tower my[3], size_t disks) {
	for (size_t d {disks}; d > 0; --d) {
		for (unsigned i {}; i < 3; ++i)
			if (my[i].size() >= d)
				std::cout << my[i][d - 1] << "  ";
			else
				std::cout << "   ";

		std::cout << '\n';
	}

	std::cout << std::setw(7) << std::setfill('-') << "-" << '\n';
	std::cout << "1  2  3\n";
}

int main() {
	constexpr size_t noDisks {3};
	Tower my[3];
	unsigned cnt {};

	my[0].init(noDisks);

	while (true) {
		unsigned from {}, to {}, disc {};

		display(my, noDisks);
		if (my[2].correct(noDisks))
			break;

		std::cout << "\nMove " << ++cnt << '\n';

		do {
			std::cout << "From which tower: ";
			std::cin >> from;
		} while ((from < 1 || from > noDisks || my[from - 1].empty()) && (std::cout << "That column is empty!\n"));

		do {
			std::cout << "Which disc to move: ";
			std::cin >> disc;
		} while (my[from - 1].top() != disc && (std::cout << "That is not the top disc\n"));

		do {
			std::cout << "To which tower: ";
			std::cin >> to;
		} while ((to < 1 || to > noDisks || !my[to - 1].empty() && my[to - 1].top() < disc) && (std::cout << "Invalid move\n"));

		const auto d {my[from - 1].top()};

		my[from - 1].pop();
		my[to - 1].push(d);
	};

	std::cout << "\nIt took " << cnt << " moves\n";
}


1
2
3
-------
1  2  3

Move 1
From which tower: 1
Which disc to move: 1
To which tower: 3

2
3     1
-------
1  2  3

Last edited on
spinach999 (5)
Thank you all for the help, but unfortunately some of the programming language used in your codes I am unfamiliar with. The only problem that remains now is that in my code, my disks aren't moving to the targeted stack tower. Currently this is the code I have, I took out the exceptions so it is a little easier to read.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
 
#include <iostream>
#include <string>
#include <stack>

using namespace std;

class Tower {
private:
	static void prtStack(stack<int>& disks)
    {
		if (disks.empty()) 
			return;

		const int topElement {disks.top()};

		disks.pop();
		prtStack(disks);
    cout << topElement << ' ';
		disks.push(topElement);
	}

public:
  stack <int> disks;
  string name;

  Tower(string _name) 
  {
    name = _name;
  }

  void Initialize() 
  { 
  for (int i = 3; i > 0; i--) 
    disks.push(i);
  }   

 void Add(int diskNum, stack<int>& disks)
  {
    //if (diskNum > disks.top())
      //throw IncorrectSizeException();
      disks.push(diskNum);
  }


  void Shift(int diskNum, Tower &toTower) 
  {
    //if (disks.empty())
      //throw NoDisksException();
      toTower.Add(diskNum, disks); //---> problem may be here
      disks.pop();
  
  }

  void Print() 
  {
     cout << name << ": ";
    prtStack(disks);
    cout << '\n';
  }
};

int main() 
{
  cout << "Get the disks from tower 1 to tower 3 in only 7 moves" << endl;

  Tower t1 = Tower("tower_1");
  t1.Initialize();
  Tower t2 = Tower("tower_2");
  Tower t3 = Tower("tower_3");
  int counter = 0;
  
  t1.Print();
  t2.Print();
  t3.Print();
  try 
  {
    do
    {
      int towerNum1, towerNum2, diskNum;
      cout << "\nWhich tower do you want to move the disk from: ";
      cin >> towerNum1;
      
      cout << "\nGive disk number: ";
      cin >> diskNum;
      
      cout << "\nWhich tower do you want to move the disk to: ";
      cin >> towerNum2;

      //if(3 < towerNum1 || towerNum1 < 1 || 3 < towerNum2 || towerNum2 < 1 || 3 < diskNum || diskNum < 1)
        //throw OutOfRangeException();

      if(towerNum1 == 1)
      {
        if(towerNum2 == 1)
          continue;
        else if(towerNum2 == 2)
          t1.Shift(diskNum, t2);
        else if(towerNum2 == 3)
          t1.Shift(diskNum, t3);
      }
      
      if(towerNum1 == 2)
      {
        if(towerNum2 == 1)
          t2.Shift(diskNum, t1);
        else if(towerNum2 == 2)
          continue;
        else if(towerNum2 == 3)
          t2.Shift(diskNum, t3);
      }
      
      if(towerNum1 == 3)
      {
        if(towerNum2 == 1)
          t3.Shift(diskNum, t1);
        else if(towerNum2 == 2)
          t3.Shift(diskNum, t2);
        else if(towerNum2 == 3)
          continue;
      }
      counter++;
    }while (counter < 7); 
    
    t1.Print();
    t2.Print();
    t3.Print();
  }

  
  return 0;
}
jonnin (11437)
if you don't understand something, try looking it up, and if you can't find it or understand the reference you found, then ask what it is. There is a lot of good stuff above, don't throw it out just because its different looking.
seeplus (6591)
Try this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
#include <iostream>
#include <string>
#include <stack>

using namespace std;

class Tower {
private:
	static void prtStack(stack<int>& disks) {
		if (disks.empty())
			return;

		const int topElement {disks.top()};

		disks.pop();
		prtStack(disks);
		cout << topElement << ' ';
		disks.push(topElement);
	}

public:
	stack <int> disks;
	string name;

	Tower(const string& _name) {
		name = _name;
	}

	void Initialize() {
		for (int i = 3; i > 0; i--)
			disks.push(i);
	}

	static void Add(int diskNum, stack<int>& todisks) {
		//if (diskNum > disks.top())
		  //throw IncorrectSizeException();
		todisks.push(diskNum);
	}

	void Shift(int diskNum, Tower& toTower) {
		//if (disks.empty())
		  //throw NoDisksException();
		Add(diskNum, toTower.disks);
		disks.pop();
	}

	void Print() {
		cout << name << ": ";
		prtStack(disks);
		cout << '\n';
	}
};

int main() {
	cout << "Get the disks from tower 1 to tower 3 in only 7 moves" << endl;

	Tower t1 = Tower("tower_1");

	t1.Initialize();

	Tower t2 = Tower("tower_2");
	Tower t3 = Tower("tower_3");
	int counter = 0;

	do {
		int towerNum1, towerNum2, diskNum;

		t1.Print();
		t2.Print();
		t3.Print();

		cout << "\nWhich tower do you want to move the disk from: ";
		cin >> towerNum1;

		cout << "\nGive disk number: ";
		cin >> diskNum;

		cout << "\nWhich tower do you want to move the disk to: ";
		cin >> towerNum2;

		//if(3 < towerNum1 || towerNum1 < 1 || 3 < towerNum2 || towerNum2 < 1 || 3 < diskNum || diskNum < 1)
		  //throw OutOfRangeException();

		if (towerNum1 == 1) {
			if (towerNum2 == 1)
				continue;
			else if (towerNum2 == 2)
				t1.Shift(diskNum, t2);
			else if (towerNum2 == 3)
				t1.Shift(diskNum, t3);
		}

		if (towerNum1 == 2) {
			if (towerNum2 == 1)
				t2.Shift(diskNum, t1);
			else if (towerNum2 == 2)
				continue;
			else if (towerNum2 == 3)
				t2.Shift(diskNum, t3);
		}

		if (towerNum1 == 3) {
			if (towerNum2 == 1)
				t3.Shift(diskNum, t1);
			else if (towerNum2 == 2)
				t3.Shift(diskNum, t2);
			else if (towerNum2 == 3)
				continue;
		}
		counter++;
	} while (counter < 7);

	t1.Print();
	t2.Print();
	t3.Print();
}

Last edited on
spinach999 (5)
Thank you so much, I was able to fix it.
deleted account xyzzy (5768)
spinach999 wrote:
unfortunately some of the programming language used in your codes I am unfamiliar with.

You can learn more of what C++ has to offer with a free online tutorial: Learn C++

https://www.learncpp.com/

You won't learn all of what C++ has to offer at Learn C++, but you will find a lot of useful information at your own pace.
Topic archived. No new replies allowed.