#include<iostream.h>
#define maxlen 50
void hanoi(int n,char a,char b,char c)
{
	struct stack
	{
		int no,ns;
		char x,y,z;
	}st[maxlen];
	int top=1,n1,a1,b1,c1;
	st[top].no=1;  //初值入棧
	st[top].ns=n;
	st[top].x=a;
	st[top].y=b;
	st[top].z=c;
	while(top>0)
	{
		if(st[top].no==1)
		{
			n1=st[top].ns;  //退棧hanoi(n,x,y,z)
			a1=st[top].x;
			b1=st[top].y;
			c1=st[top].z; 
			top--;
			top++;  //將hanoi(n-1,x,z,y)入棧
			st[top].no=1;
			st[top].ns=n1-1;
			st[top].x=b1;
			st[top].y=a1;
			st[top].z=c1;
			top++; //將第n個圓盤從x移到z
			st[top].no=0;
			st[top].ns=n1;
			st[top].x=a1;
			st[top].y=c1;
			top++;  //hanoi(n-1,y,x,z)入棧
			st[top].no=1;
			st[top].ns=n1-1;
			st[top].x=a1;
			st[top].y=c1;
			st[top].z=b1;
		}
		while(top>0 && (st[top].no==0 || st[top].ns==1))
		{
			if(top>0 && st[top].no==0)
			{
				cout<<"\t將第"<<st[top].ns<<"個盤片從"
					<<st[top].x<<"移動到"<<st[top].y<<endl;
				top--;
			}
			if(top>0 && st[top].ns==1) //將第n個圓盤從x移到z并退棧
			{
				cout<<"\t將第"<<st[top].ns<<"個盤片從"
					<<st[top].x<<"移動到"<<st[top].z<<endl;
				top--;
			}
		}
	}
}
void main()
{
	int n=3;
	cout<<"hanoi(3)非遞歸求解結果:"<<endl;
	hanoi(n,'x','y','z');
}