??? 設計并實現魔王語言的解釋器，具體要求如下：大寫字母表示魔王語言的詞匯；小寫字母表示人的詞匯語言；魔王語言中可包含括號。

??? 如：我們有魔王語言的解釋規則：B－>tAdA；A->sae；則魔王語言 B(ehnxgz)B解釋成tsaedsaeezegexenehetsaedsae。

實現代碼如下：

#include<stdlib.h>
#include<stdio.h>
#define STACK_INIT_SIZE 100 //存儲空間初始分配量
#define STACK_INCREMENT? 10? //存儲空間分配增量
#define OVERFLOW????????? 1
#define OK????????? 1
#define ERROR????? 0
#define TRUE??????? 1
#define FALSE?????? 0
typedef char????? SElemType;
typedef char????? QElemType;
typedef int???? Status;
typedef struct{
?SElemType *base;??????????? //棧基址
SElemType *top;???????????? //棧頂地址
?int stacksize;
}SqStack;
typedef struct QNode{
?QElemType data;
?struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
?QueuePtr front;?? //隊頭指針
?QueuePtr rear;??? //隊尾指針
}LinkQueue;
Status InitStack(SqStack &S)
//構造一個空棧
{
?S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(char));
?if(!S.base)
??exit (OVERFLOW);//存儲單元分配失敗
?S.top=S.base;
?S.stacksize=STACK_INIT_SIZE;
?return OK;
}
Status Push(SqStack &S,SElemType e)
//插入元素e棧頂單元
{
?if(S.top-S.base>=S.stacksize)
?{//棧滿，追加存儲空間
??S.base=(SElemType *)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(char));
?if(!S.base)
??exit (OVERFLOW);//存儲單元分配失敗
?S.top=S.base+S.stacksize;
?S.stacksize+=STACK_INCREMENT;
?}
?*(S.top)=e;
?S.top++;
?return OK;
}
Status Pop(SqStack &S,SElemType& e)
//若棧不為空，則刪除S的棧頂單元，用e返回其值
{
?if(S.base==S.top)
??return ERROR;
?S.top--;
?e=*(S.top);
?return OK;
}
Status StackEmpty(SqStack S)
{
?if(S.base==S.top)
??return 0;
?else
??return 1;
}

Status InitQueue(LinkQueue &Q)
//構造一個空隊列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)
//插入元素e為Q的新的隊尾元素
{
?QueuePtr p;
?p=(QueuePtr)malloc(sizeof (QNode));
?p->data=e;
?p->next=NULL;
?Q.rear->next=p;
?Q.rear=p;
?return OK;
}
Status DeQueue (LinkQueue &Q,QElemType &e)
//若隊列不空，則刪除Q的隊頭元素，用e返回其值，并返回OK;
//否則返回ERROR
{
?QueuePtr p;
?if(Q.front==Q.rear)
??return ERROR;
p=Q.front->next;
?e=p->data;
?Q.front->next=p->next;
?if(p==Q.rear)
??Q.rear=Q.front;
?free(p);
?return OK;
}
Status QueueEmpty(LinkQueue Q)
//若隊列Q為空隊列,則返回TRUE，否則返回FALSE
{
?if(Q.rear==Q.front)
??return FALSE;
?else
??return TRUE;
}
void InStack(char fiend[],SqStack &S)
{
?int m,i=0;
?for(;fiend[i]!='\0';i++);//計算fiend中有多少
?for(m=i-1;m>=0;m--)
??Push(S,fiend[m]);
}
void main()
{
?char e,c,d;
?SqStack S,zhan;
?LinkQueue Q;
?? InitQueue(Q);
?char? mowang[]="B(ehnxgz)B";
?printf("你想要解釋的魔王語言為：%s\n",mowang);
??? char? B[]="tAdA";
?InitStack(S);
?InitStack(zhan);
?InStack(mowang,S);//全部壓進棧中
?while(StackEmpty(S))//在棧不為空的情況下
?{
??Pop(S,e);
??if(e=='B')
??InStack(B,zhan);
??else
if(e=='(')//如果為右括號，則輸出括號中所有內容
???{
????while(Pop(S,e)&&e!=')')//當為左括號時停止
????{
?????if(e!=')')
?????EnQueue (Q,e);
????}
?????DeQueue (Q,c);//讀出隊列中第一個元素
????while(QueueEmpty(Q))
????{
?????DeQueue (Q,d);//取出元素
?????Push(zhan,c);
?????Push(zhan,d);
????}
????Push(zhan,c);//再次壓入第一個元素
???//?Pop(S,e);//去掉左括號
???}

?}
?printf("\n解釋的結果為:? ");
??? while(StackEmpty(zhan))//在棧不為空的情況下
?{
?
??Pop(zhan,c);
??if(c=='A')
printf("sae");
??????? else
???? printf("%c",c);
??}
??printf("\n");
}

?