#include<iostream.h>   
  #include<stdio.h>   
  #include<string.h>   
      
  class   stack                       
  {   
  public:   
	  stack();   
	  char   popStack();              //棧頂元素出棧
	  void   pushStack(char   x);     //新元素x進棧
	  void   print();                 //調試時使用   
	  bool   isEmpty();               //判斷棧空否
  private:
	  int    top;                     //棧頂指針
	  char * lan;                     //存放棧中元素的棧數組
  };       
    
  stack::stack()                      //棧的構造函數  
  {   
	  top=0;
	  lan=new char[50];
  }   
  char stack::popStack()              //退棧，并將棧頂元素附給a后返回
  {
	  char a;   
	  a = lan[--top];                 //棧頂指針退1
	  return a;   
  }   
    
  void stack::pushStack(char x)       //將x入棧
  {   
  lan[top++]=x;                       //x先進棧，再使指針加1
  }       
  void stack::print()   
  {                          //利用輔助棧將棧中元素輸出，否則會銷毀棧中的元素  
	  stack   temp=*this;    
	  while(temp.top!=0)     
	  {   
		  cout<<temp.popStack();   //輸出輔助棧中的棧頂元素  
	  }   
  } 
  
  bool stack::isEmpty ()    //判斷棧是否為空，如果為空返回false,否則返回bool
  {
	  if(top==0)
		  return true;
	  else 
		  return false;
  }
  class   queue   
  {   
  public:   
	  queue();                      //構造函數
	  char   DeQueue();            //隊頭元素出隊列
	  void   EnQueue(char   x);   //新元素x插到隊尾
	  void   print();               //打印隊列
	  bool   isEmpty();             //判斷隊列空否
  private:
	  int   front;                  //隊頭指針
	  int   rear;                   //隊尾指針
	  char * q;                     //存放隊列元素的指針
  };   
    
  queue::queue()                    //構造函數
  {   
	  q=new char[50];               //建立給定長度50的字符數組
	  front=rear=0;                 //給隊頭和隊尾指針賦初值
  }   
    
  char queue::DeQueue()  
  //退掉一個隊頭元素并由e返回
  {   
	  char   a;   
	  a=q[front++];                //隊頭元素賦給e后，隊頭指針加1
	  return   a;   
  }  
  void   queue::EnQueue(char   x)   
  //將新元素e插入到該隊列的隊尾
  {   
	  q[rear++]=x;                 //先將元素x插入隊尾，再將隊尾指針加1
  }   
    
  void   queue::print()            //利用輔助隊列輸出隊列元素
  {   
	  queue   temp=*this;    
	    
	  while(temp.front!=temp.rear)   
	  {   
		    
		  cout<<temp.DeQueue() ;
	  }  
  }
  bool queue::isEmpty ()         //判斷隊列是否為空，如果為空返回true,否則返回false
  {
	  if(front==rear)
		  return true;
	  else
		  return false;
  }
  int main()   
  {
	  stack   s,stemp;                        
	  queue   q,gz,mwyy,gztemp;   
	  int   i,n,ngz1,ngz2;   
	  char   e,a[5],temp;
	  char guize1[]="BtAdA",guize2[]="Asae";        //gz1[]和gz2[]存放規則 
	  cout<<"請輸入魔王語言：測試數據為：B(ehnxgz)B"<<endl;   
	  gets(a);                                      //將輸入的字符串賦給a
	  n=strlen(a);                                  //將字符串a的長度賦給n
	  ngz1=strlen(guize1);  
	  ngz2=strlen(guize2);                                             
	 for(i=n;i>=0;i--)                              //將魔王語言自右向左進棧
	 {                                              
		 s.pushStack(a[i]);           
	 }                                           //s棧中存儲情況：B2)zgxnhe(B1   
	 {
		 e=s.popStack();   
		 
		 do   
		 {   
			 stemp.pushStack(e);            //輔助棧,用來存放開括號以前的元素   
			 e=s.popStack();   
		 }                                       //stemp:B   
		 while(!(e=='('));   
		
		 temp=s.popStack();                //用temp記錄括號中的第一個字符   
		 e=s.popStack();   
		 do   
		 {   
			 q.EnQueue(temp);   
			 q.EnQueue(e);   
			 e=s.popStack();     
		 }   
		 while(!(e==')'));   
		 q.EnQueue(temp);   	                    //用隊列q儲存中間解釋結果ehenexegeze   
	 }
  while(!q.isEmpty())                              //將q中元素壓入棧s中
  {   
	  char c;   
	  c=q.DeQueue();   
	  s.pushStack(c);   
  }   
  while(!stemp.isEmpty())                          //將括號前的元素進入棧s中
  {   
	  char   c;   
	  c=stemp.popStack();   
	  s.pushStack(c);   
  }                                                 //s:BehenexegezeB   
  for(i=1;i<ngz1;i++)   
	  if(guize1[i]==guize2[0])   
		  for(int j=1;j<ngz2;j++)   
			  gz.EnQueue(guize2[j]);   
		  else   
			  gz.EnQueue(guize1[i]);                //用gz存放B的解釋語言tsaedsae   
		  gztemp=gz;                                  //gztemp做gz的輔助隊列
		  e=s.popStack();   
		  while(!s.isEmpty())   
		  {  
			  if(e==guize1[0])   
				  while(!gztemp.isEmpty())   
				  {   
					  char ctemp=gztemp.DeQueue();   
					  mwyy.EnQueue(ctemp);   
				  }   
				  else   
					  mwyy.EnQueue(e);   
				  gztemp=gz;   
				  e=s.popStack();   
		  }   
		  cout<<"******************************************************************"<<endl;
		  cout<<endl;
		  cout<<"翻譯后的語言為："<<endl;   
		  mwyy.print();   
		  cout<<endl;
		  cout<<"對應的漢字為:"<<endl;
          
		  while(!mwyy.isEmpty() )        //將對應的漢字輸出
		  {
			  e=mwyy.DeQueue ();
			  switch(e)
			  {
			  case 't' : cout<<"天";break;
              case 'd' : cout<<"地";break;
              case 's' : cout<<"上"; break;
              case 'a' : cout<<"一只"; break;
			  case 'e' : cout<<"鵝"; break;
              case 'z' : cout<<"追"; break;
			  case 'g' : cout<<"趕"; break;
              case 'x' : cout<<"下"; break;
              case 'n' : cout<<"蛋"; break;
              case 'h' : cout<<"恨"; break;
			  case 'B' : cout<<"天上一只鵝地上一只鵝";break;
              case 'A' : cout<<"上一只鵝";break;
              default :  cout<<"*";break;	 //遇到沒沒有漢字輸出的字符用*號表示
			  }
		  }
		  cout<<endl;
		  return 0;
  }   
    
                                         //B1ehenexegezeB2   
                                         //s:easdeastehenexegezeeasdeast