/*1.定義全局變量*/ 
#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   demon[MAXSIZE]; 

/*2.棧類型及其基本操作*/ 

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; 
  }/*創(chuàng)建棧*/ 
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; 
  }/*出棧*/ 

/*3.隊列類型及其基本操作*/ 

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; 
  }/*創(chuàng)建隊列*/ 
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; 
  }/*出隊*/ 

/*4.括號內(nèi)元素入棧處理函數(shù)*/ 

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

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

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

        } 
      } 
    } 
  return  flag; 
  }/*排序*/ 

status main() 
 { 
    sqstack s1; 
    linkqueue q1; 
    int k=0; 
    int flag=1; 
    clrscr(); 
    printf("\n\n\n\t\t\tWELCOME!\n"); 
    printf("\t***************************************\n");
    printf("\tPlease Input The Demon's Words:\n\t"); 
    printf("!: Less Than 30 Letters: )\n\t"); 
    printf("!: Please Stop By '#': )\n\t"); 
    printf("***************************************\n\t"); 
    printf("The Demon's Words:\n\t");
    scanf("%s",demon); 
    printf("\n\t***************************************"); 
    initstack(&s1); /*創(chuàng)建棧*/ 
    initqueue(&q1); /*創(chuàng)建隊*/ 
    tempstack(&s1); /*調(diào)用括號內(nèi)元素入棧處理函數(shù)*/ 
    while (flag==1) /*如果有大寫字母*/ 
        { 
        k=0; 
        flag=sort(&s1,&q1); 
        while(q1.front!=q1.rear) /*重寫demon[i ]*/ 
            { 
            dequeue(&q1,&e); 
            demon[k]=e; 
            k++; 
            } 
        demon[k]='#'; 
        } 
    demon[k]='\0'; 
    printf("\n\tThe Human's Words:\n\t%s",demon); 
    printf("\n\n\t***************************************");
    printf("\n\t\t\tTHANK YOU!\n\t");
    printf("Please press any key to exit...");
    if(getch()) exit(1); 
 }