#include"stdio.h"
#include"stdlib.h"
#include <iostream.h> 

typedef struct
{
	char *base;
	char *top;
	int stacksize;
}stack;

typedef struct QNode
{
	char data;
	struct QNode *next;
}QNode,*LinkQueueNode;

typedef struct
{
	LinkQueueNode front;
	LinkQueueNode rear;
}LinkQueue;


int Initstack(stack &s)
{
  s.base=(char*)malloc(100*sizeof(char));
  if(!s.base)exit(0);
  s.top=s.base;
  s.stacksize=100;
  return 1;
}

int initQueue(LinkQueue &Q)
{
	Q.front=Q.rear=(LinkQueueNode)malloc(sizeof(LinkQueueNode));
	if(!Q.front)exit(-1);
	Q.front->next=NULL;
	return 1;
}

int IsEmpty(stack s)
{
    if(s.top==s.base)return 1;
	return 0;
}

int Isempty(LinkQueue Q)
{
	if(Q.front==Q.rear)return 1;
	return 0;
}

void push(stack &s,char e)
{
	if(s.top-s.base>=s.stacksize)
	{
		s.base=(char*)realloc(s.base,(s.stacksize+10)*sizeof(char));
		if(!s.base)exit(0);
		s.top=s.base+s.stacksize;
		s.stacksize+=10;
	}
	*s.top++=e;
}

int EnQueue(LinkQueue &Q,char e)
{
	LinkQueueNode p;
	p=(LinkQueueNode)malloc(sizeof(QNode));
	if(!p)exit(-1);
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	return 1;
}

int pop(stack &s,char &e)
{
	if(s.top==s.base)exit(0);
	e=*--s.top;
	return 1;
}

char DeQueue(LinkQueue &Q,char &e)
{
    LinkQueueNode p;
	if(Q.front==Q.rear)return 0;
	p=Q.front->next;
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p)Q.rear=Q.front;
	free(p);
	return e;
}

char gettop(stack &s)
{
	char e;
	if(s.top==s.base)exit(0);
	e=*(s.top--);
	return e;
}


void main()
{
  char a[100];
  char A[3]={'s','a','e'};
  char B[8]={'t','s','a','e','d','s','a','e'};
  char c,t,d,s,e,z,g,x,n,h,ch;
  printf("魔王說話了：");
  int i=0;
  stack S;
  LinkQueue Q,q;
  Initstack(S);
  initQueue(Q);
  initQueue(q);
  cin>>a;
  while(a[i])i++;
  for(int k=i;k>=0;k--)
	  push(S,a[k]);

 printf("魔王要說的話是：");
	  while(!IsEmpty(S))
	  {
		   pop(S,e);
		   if(e=='B')
		   {
			   printf("tsaedsae");
               for(int t=0;t<8;t++)
               EnQueue(q,B[t]);
		   }
		   else if(e=='A')
		   {
			   printf("sae");
			   for(int t=0;t<2;t++)
               EnQueue(q,A[t]);
		   }

		   else if(e=='(')
		   {
			   while(pop(S,e)&&e!=')')
			   {
                   EnQueue(Q,e);
			   }
			   push(S,e);
               DeQueue(Q,c);
              while(!Isempty(Q))
			  {
                   DeQueue(Q,e);
				   push(S,c);
				   push(S,e);
			  }
			  push(S,c);

	          while(!IsEmpty(S))
			  { 
			    pop(S,e);
			    if(e==')')break;
			    else if(e=='B')
				{
					printf("tsaedsae");
                    for(int t=0;t<8;t++)
                    EnQueue(q,B[t]);
				}
					else if(e=='A')
					{
					  printf("sae");
					  for(int t=0;t<2;t++)
                      EnQueue(q,A[t]);
					}
					    else
						{
			              printf("%c",e);
                          EnQueue(q,e);
						}
			  }
		   }
	  }
	  while(!Isempty(q))
	  {
         DeQueue(q,ch);
		 switch(ch)
		 {
			 case 't':printf("天");break;
				 case 'd':printf("地");break;
					 case 's':printf("上");break;
						 case 'a':printf("一只");break;
							 case 'e':printf("鵝");break;
								 case 'z':printf("追");break;
									 case 'g':printf("趕");break;
										 case 'x':printf("下");break;
											 case 'n':printf("蛋");break;
		                                        case 'h':printf("恨");break;
		 }
	  }
	  printf("\n");

}