#include <iostream.h>
#include <fstream.h>
#include <malloc.h>

struct stack
{char sc[100];
int  top;
};//定義堆棧

void init(struct stack *s);//初始化堆棧
void push(struct stack *s,char a);//進(jìn)棧
char pop(struct stack *s);//出棧	
bool isempty(struct stack *s);//判堆棧是否為空
int position(char a,char *p);

void main()
{
struct stack *B,*C;
int n,k,p,p1,p2;
int max;
char a[30],b[30];
bool flag=true;
B=(struct stack *)malloc(sizeof(struct stack));
C=(struct stack *)malloc(sizeof(struct stack));
init(B);
init(C);
cout<<"please input the number of trains";
cin>>n;
cout<<"please input the seria of in"<<endl;
for (int i=0;i<n;i++)
cin>>a[i];
a[n]='\0';
cout<<"please input the seria of out"<<endl;
for (int j=0;j<n;j++)
cin>>b[j];
b[n]='\0';
ofstream myf("train.txt",ios::app);
if(myf.fail())
 {cerr<<"error opening file";
 return;}
 myf<<n<<'\n';
 myf<<a<<'\n';
 myf<<b<<'\n';//以上操作完成輸入輸出序列寫進(jìn)文件
 max=n-1;
 k=n-1;
 while (k>=0)
 {
 p=position(a[k],b);
 if (p<position(C->sc[C->top-1],b))
	 flag=false;
   if (p==max)
   {
 myf<<a[k]<<'A'<<'D'<<'\n';
 max=max-1;
if (!isempty(B)||!isempty(C))
{
 if (!isempty(B))
 {p1=position(B->sc[B->top-1],b);}
 if (!isempty(C))
 {p2=position(C->sc[C->top-1],b);}
 while (((p1==p2+1)&&!isempty(B))||(!isempty(B)&&(p1==max))||((p2==max)&&!isempty(C)))
 {
	 if ((p1==p2+1)&&(p1!=max)&&!isempty(B))
	 {
 myf<<B->sc[B->top-1]<<'B'<<'C'<<'\n';
 push(C,pop(B));
	 } 
	 else if ((p1==max)&&!isempty(B))
	 {myf<<pop(B)<<'B'<<'D'<<'\n';
	 max=max-1;
	 }
	 else if ((p2==max)&&!isempty(C))
	 {myf<<pop(C)<<'C'<<'D'<<'\n';
	 max=max-1;
	 }

if (!isempty(B))
 {p1=position(B->sc[B->top-1],b);}
 if (!isempty(C))
 {p2=position(C->sc[C->top-1],b);}

 }

}
   }//if (p==max);
   else if(((p==0)&&(k>0)&&flag)||(p==position(C->sc[C->top-1],b)+1)||((p<position(B->sc[B->top-1],b))&&(position(a[k-1],b)>p)))
   {
   myf<<a[k]<<'A'<<'C'<<'\n';
   push(C,a[k]);
   
   }
   else {push(B,a[k]);
   myf<<a[k]<<'A'<<'B'<<'\n';

   }
 k=k-1;
 /*if (a[k]=='b')
 {cout<<isempty(B)<<endl;
 cout<<isempty(C)<<endl;
 cout<<max;
 break;}*/
 }
 if (!isempty(B)||!isempty(C))
	 myf<<"error"<<'\n';
 else myf<<"success"<<'\n';
 myf<<"--------------------------------------------------------------------------------------"<<'\n';
 myf.close();
}

 void init(struct stack *s)
{s->top=0;
s->sc[s->top]='\0';
}

void push(struct stack *s,char a)
{
s->sc[s->top]=a;
s->top=s->top+1;
s->sc[s->top]='\0';
}

char pop(struct stack *s)
{s->top=s->top-1;
 return s->sc[s->top];
 s->sc[s->top]='\0';
}

bool isempty(struct stack *s)
{if (s->top==0)
return true;
else return false;
}


 
int position(char a,char *p)//如果a是'\0'或者在p中找不到a則返回-1
{int i=0;
while ((p[i]!='\0')&&(p[i]!=a))
{i=i+1;
}
if ((p[i]=='\0')||(a=='\0'))
return -1;
else return i;


}