设计并实现魔王语言的解释器，具体要求如下：大写字母表示魔王语言的词汇；小写字母表示人的词汇语言；魔王语言中可包含括号。

    如：我们有魔王语言的解释规则：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");
}