#include<stdio.h>
#include<iostream.h>
#include<malloc.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

#define STACK_INIT_SIZE 100
#define STACK_INCREMENT  10

struct Stack
{char* base;
 char* top;
 int stacksize;
};

struct Queue
{char data;
 struct Queue* next;
};

struct LinkQueue
{struct Queue* front;
 struct Queue* rear;
};

//構造空棧
void InitStack(Stack &s)
{s.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));
 s.top=s.base;
 s.stacksize=STACK_INIT_SIZE;
}

//元素入棧
void Push(Stack &s,char e)
{if(s.top-s.base>=STACK_INIT_SIZE)
 {s.base=(char*)realloc(s.base,(s.stacksize+STACK_INCREMENT)*sizeof(char));           
  s.top=s.base+s.stacksize;
  s.stacksize+=STACK_INCREMENT;
 }
 *(s.top)=e;
 s.top++;
}

//元素出棧
void Pop(Stack &s,char &e)
{e=*--s.top;
}

//判斷棧是否為空
int StackEmpty(struct Stack s)
{if(s.top==s.base){return 1;}
 else{return 0;}
}

//清空棧
void ClearStack(Stack &s)
{s.top=s.base;
}

//構造空隊列
void InitQueue(LinkQueue &q)
{q.front=q.rear=(struct Queue*)malloc(sizeof(struct Queue));
 q.front->next=NULL;
}

//元素入隊
void EnQueue(LinkQueue &q,char e)
{struct Queue* p;
 p=(struct Queue*)malloc(sizeof(struct Queue));
 p->data=e;
 p->next=NULL;
 q.rear->next=p;
 q.rear=p;
}

//元素出隊
void DeQueue(LinkQueue &q,char &e)
{struct Queue* p;
 p=q.front->next;
 e=p->data;
 q.front->next=p->next;
 if(q.rear==p){q.rear=q.front;}
 free(p);
}

//判斷隊列是否為空
int QueueEmpty(LinkQueue q)
{if(q.front==q.rear){return 1;}
 else{return 0;}
}

//把字符數組從右至左存入棧中
void InStack(Stack &s,char* ch)
{int i,L=0;
 while(ch[L]!='\0'){L++;}
 for(i=L-1;i>=0;i--){Push(s,ch[i]);}
}

int main()
{int i=0,j,mark=1,f=0;
 char A[]="sae",B[]="tsaedsae",MoWang[100]="\0",e1,key,e2,e,flag='0';//flag用來標記處理括號
 struct Stack S;
 struct Stack temp;//用來處理括號外的元素
 struct LinkQueue Q;
 InitStack(S);
 InitStack(temp);
 InitQueue(Q);
 do
 {system("cls");
  cout<<"████████████████████████████████████████";
  cout<<"█                                                                            █";
  cout<<"█                                魔王語言解釋                                █";
  cout<<"█                                                                            █";
  cout<<"████████████████████████████████████████";
  cout<<"█                                                                            █";
  cout<<"█                                1. 進行解釋                                 █";
  cout<<"█                                                                            █";
  cout<<"█                                2. 退出                                     █";
  cout<<"█                                                                            █";
  cout<<"████████████████████████████████████████";
  cout<<endl<<"請輸入你的選擇(輸入1-2以外字符將結束程序):";
  cin>>j;
  if(j==1)
  {system("cls");cout<<"請輸入你想要解釋的魔王語言(最多含有一個括號):"<<endl;
   cin>>MoWang;
   InStack(S,MoWang);//把要解釋的魔王語言存入棧中
   while(!StackEmpty(S))
   {Pop(S,e1);
    if(e1=='(')
    {if(StackEmpty(S))
     {cout<<"魔王語言錯誤,程序退出!"<<endl;
      mark=0;
      break;
     }
     while(!StackEmpty(S))
     {Pop(S,e1);
      if(e1==')'){f=1;break;}
      else if(!(e1>='a'&&e1<='z')&&!(e1>='A'&&e1<='Z'))
	  {cout<<"魔王語言錯誤,程序退出!"<<endl;
       mark=0;
       break;
	  }                
     }
     if(mark==0){break;}
     if(f!=1)
     {cout<<"魔王語言錯誤,程序退出!"<<endl;
      break;
     }            
    } 
    else if(e1==')')
    {cout<<"魔王語言錯誤,程序退出!"<<endl;
     mark=0;
     break;
    } 
    else if(!(e1>='a'&&e1<='z')&&!(e1>='A'&&e1<='Z'))
    {cout<<"魔王語言錯誤,程序退出!"<<endl;
     mark=0;  
     break;   
    }     
   }
   if(mark==1&&f==1)
   {ClearStack(S);
    InStack(S,MoWang);
    while(!StackEmpty(S))
    {Pop(S,e1);
     if(e1=='B'){Push(temp,e1);}
     else if(e1=='A'){Push(temp,e1);}
     else if(e1=='(')//用隊存儲括號中的元素
     {Push(temp,flag);//有括號的話就用flag標記               
      Pop(S,e1);
      while(e1!=')')
      {EnQueue(Q,e1);
       Pop(S,e1);
      }
      if(!QueueEmpty(Q)){DeQueue(Q,key);}            
     }
     else
     {Push(temp,e1);
      f=0;
     }
    }
    while(!StackEmpty(temp))
    {Pop(temp,e1);
     if(e1!=flag){Push(S,e1);}//把括號外的元素存入棧中
     else
     {while(!QueueEmpty(Q))//把括號中的元素存入棧
      {DeQueue(Q,e2);
       Push(S,key);
       Push(S,e2);
      }
      if(f!=0){Push(S,key);}//最后還要存一個key
     }
    }
    cout<<"解釋后的語言為:"<<endl;
    while(!StackEmpty(S))//處理后的元素依次出棧
    {Pop(S,e);
     EnQueue(Q,e);//為了輸出對應漢字,元素進隊
     if(e=='B'){cout<<B;}
     else if(e=='A'){cout<<A;}
     else{cout<<e;}
    }
    cout<<endl;
    while(!QueueEmpty(Q))//輸出對應漢字
    {DeQueue(Q,e);
     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;
   }
   getchar();
  }
 }while(i>0&&i<2);
 cout<<endl<<"此程序制作者: 黃子皇 "<<endl;
 getchar();
 exit(0);
 return 0;
}