#include<malloc.h>
#include <stdlib.h>
#include<string.h>
#include <iostream.h>
      
#define TRUE       1
#define FALSE       0
#define  OK         1
#define ERROR       0
#define NULL        0
#define OVERFLOW     -2
#define MAXSIZE       100
#define stack_init_size  100
#define stackincrement   10

typedef char   selemtype;
typedef char   qelemtype;
typedef char   elemtype;
typedef int   status;

char   e;
char   mowang[MAXSIZE];



typedef struct
  {
  selemtype   *base;
  selemtype   *top;
  int     stacksize;
  }sqstack;

status initstack (sqstack *s)
  {
  s->base=(selemtype *)malloc(stack_init_size*sizeof(selemtype));
  if(!s->base) exit (OVERFLOW);
  s->top=s->base;
  s->stacksize=stack_init_size;
  return OK;
  }

status push (sqstack *s,selemtype e)
  {
  if(s->top-s->base>=s->stacksize)
    {
    s->base=(elemtype *) realloc(s->base,(s->stacksize+stackincrement)*sizeof(elemtype));
    if(!s->base) exit(OVERFLOW);
    s->top=s->base+s->stacksize;
    s->stacksize+=stackincrement;
    }
  *(s->top++)=e;
  return OK;
  }

status pop(sqstack *s,selemtype *e)
  {
  if(s->top==s->base) return ERROR;
  *e=*(--(s->top));
  return OK;
  }


typedef struct qnode
  {
  qelemtype   data;
  struct qnode   *next;
  }qnode,*queueptr;
typedef struct
  {
  queueptr front;
  queueptr rear;
  }linkqueue;

status initqueue(linkqueue *q)
  {
  q->front=q->rear=(queueptr)malloc(sizeof(qnode));
  if(!q->front) exit(OVERFLOW);
  q->front->next=NULL;
  return OK;
  }

status enqueue(linkqueue *q,qelemtype e)
  {
  queueptr p;
  p=(queueptr)malloc(sizeof(qnode));
  if(!p) exit(OVERFLOW);
  p->data=e;
  p->next=NULL;
  q->rear->next=p;
  q->rear=p;
  return OK;
  }

status dequeue(linkqueue *q,qelemtype *e)
  {
  queueptr p;
  if(q->front==q->rear) return ERROR;
  p=q->front->next;
  *e=p->data;
  q->front->next=p->next;
  if(q->rear==p)
    {
    q->rear=q->front;
    }
  free(p);
  return OK;
  }


void lishistack(sqstack  *temps)//臨時(shí)棧
  {
  int  i=0;
  char   t;
  char   c;
  c=mowang[i ];
  for(i=0;c!='#';i++)/*遍歷數(shù)組*/
    {
    c=mowang[i ];
    if(c=='(')/*遇到開(kāi)括號(hào)*/
      {
      t=mowang[i+1];/*取括號(hào)中的首字母*/
      push(temps,t);/*入棧*/
      i++;/*指向首字母*/
      do
        {
        i++;
        c=mowang[i ];
        push(temps,c)/*第一次循環(huán)將次字母入棧*/;
        push(temps,t);/*再將首字母進(jìn)棧*/
        }
      while(c!=')');/*直到括號(hào)中元素全部進(jìn)棧*/
      pop(temps,&t);/*將多余進(jìn)棧的首字母t出棧*/
      pop(temps,&t); /*將多余進(jìn)棧的’)’出棧*/
      }
    }
  }


void spenqueue(linkqueue *q,char key)
  {
  int j=0;
  char a[5];
  switch(key) /*判斷大寫字母對(duì)應(yīng)的字符串*/
    {
    case'A':strcpy(a,"sae");break;
    case'B':strcpy(a,"tAdA");break;
   
    default:strcpy(a,"???"); /*不能翻譯的魔王語(yǔ)言以”???”輸出*/
    }
  while(a[j]!='\0') /*如果數(shù)組還有字母*/
    {
    enqueue(q,a[j]);/*進(jìn)隊(duì)*/
    j++;
    }
  }

void chinese(char key2)
{
	
	switch(key2)
	{
	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;
	default:cout<<'?';
	}
}

status sort(sqstack *s,linkqueue *q)
  {
  qnode   b;
  int  t1=0;/*大寫字母監(jiān)視哨置零*/
  int i;
  for(i=0;mowang[ i]!='#';i++)/*遍歷數(shù)組*/
    {
    b.data=mowang[ i];
    if( ('a'<=b.data&&b.data<='z') || b.data=='?') /*如果是小寫字母或者’?’則直接進(jìn)棧*/
      {
      enqueue(q,b.data);
      }
    else
      {
      if('A'<=b.data&&b.data<='Z') /*如果是大寫字母,則調(diào)用特殊進(jìn)棧函數(shù),*/
        {
        spenqueue(q,b.data);
        t1=1; /*發(fā)現(xiàn)大寫字母監(jiān)視哨置1*/
        }
      else
        {
        if(b.data=='(')/*如果是括號(hào)*/
          {
          do
            {
            pop(s,&e);
            enqueue(q,e);
            }
          while(!(s->top==s->base)); /*只要棧不為空,則出棧進(jìn)隊(duì)*/
          while (b.data!=')') /*只要還指向括號(hào)內(nèi)元素,就繼續(xù)往后移,保證原括號(hào)內(nèi)的元素不再進(jìn)棧*/
            {
            i++;
            b.data=mowang[ i];
            }
          }

        }
      }
    }
  return  t1;
  }

void PrintInterface()
{//打印用戶辦面
	cout<<"                  *************************************"<<endl;
	cout<<"                  *  魔王語(yǔ)言解釋                     *"<<endl;
	cout<<"                  *                                   *"<<endl;
	cout<<"                  *         設(shè)計(jì)者；                  *"<<endl;
	cout<<"                  *         班級(jí)：                    *"<<endl;
	cout<<"                  *         學(xué)號(hào)：                    *"<<endl;
   	cout<<"                  *                                   *"<<endl;
	cout<<"                  *                                   *"<<endl;
	cout<<"                  *************************************"<<endl;
}

void main()
    {
    sqstack s;
    linkqueue q;
    int k=0;
    int t1=1;
	PrintInterface();
	cout<<"                                               "<<endl;
    cout<<"請(qǐng)輸入魔王語(yǔ)言,并以#號(hào)結(jié)束：(例如：B(ehnxgz)B#)"<<endl;
    cin>>mowang;
    
    initstack(&s); /*創(chuàng)建棧*/
    initqueue(&q); /*創(chuàng)建隊(duì)*/
    lishistack(&s); /*調(diào)用函數(shù)*/
    while (t1==1) /*如果有大寫字母*/
        {
        k=0;
        t1=sort(&s,&q);
        while(q.front!=q.rear) /*重寫mowang[i ]*/
            {
            dequeue(&q,&e);
            mowang[k]=e;
            k++;
            }
        mowang[k]='#';
        }
    mowang[k]='\0';
	cout<<"              "<<endl;
	cout<<"人類的語(yǔ)言是:"<<endl;
    cout<<mowang<<endl;
	cout<<"                  "<<endl;
	cout<<"人類的語(yǔ)言解釋是："<<endl;
	for(int i=0;mowang[i]!='\0';i++)
	{ chinese(mowang[i]);
	}
	cout<<"  "<<endl;
	cout<<"              "<<endl;

}