-`
实习2、魔王语言解释
一、 需求分析
1. 问题描述
有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没人能听的懂，但他的语言是可以逐步解释成人能懂得语言的，因为他的语言是由以下两种形式的规则由人的语言逐 步抽象上去的：
（1）α->β1 β2 ... βn
（2）(θ δ1 δ2 ... δn) —>θ δn θ δn-1 ...θ δ1 θ
在这两种形式中，从左到右均表示解释。试写一个魔王解释系统，把他的话解释成人能听懂得话。
2. 基本要求
用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写或小写字母代换的变量。魔王语言可含人的词汇。
（1）B—>tAdA
（2）A—>sae
3. 测试数据
B（ehnxgz）B 解释成tsaedsaeezegexenehetsaedsae
若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是“天上一个鹅地上一个鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一个鹅地上一个鹅”。
t
d
s
a
e
z
g
x
n
h
天
地
上
一 只
鹅
追
赶
下
蛋
恨
4. 实现提示
将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈，将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简单，请读者思考如何处理。应首先实现栈和队列的基本操作。
二、 概要设计
1、 设定栈的抽象数据类型定义：
ADT Stack {
数据对象：D= {ai| ai∈CharSet, i= 1,2,……n,. n≥0 }
数据关系：R1={
| ai-1,ai∈D, ai-1 |ai-1,ai∈D t i= 1,2,……n}
基本操作：
InitQueue (*Q)
操作结果：构造一个空队列Q。
EnQueue（*Q,e）
初始条件：队列Q已经存在。
操作结果：插入元素e为Q的新的队尾元素。
DeQueue（*Q,*e）
初始条件：队列Q已经存在。
操作结果：删除Q的对头元素，并以e返回其值。
QueueEmpty（Q）
初始条件：队列Q已经存在。
操作结果：若队列Q为空栈，则返回1，否则返回0。
}ADT Queue
三、 详细设计（源代码）
（使用C语言）
#include
#include
#define STACK_INIT_SIZE 100//存储空间初始分配量
#define STACKINCREMENT 10//存储空间分配增量
typedef struct
{
char* base;//栈底指针
char* top;//栈顶指针
int stacksize;
}SqStack;
typedef struct QNote
{
char data;
struct QNote *next;
}QNote,*QueuePtr;
typedef struct
{
QueuePtr front;//队头指针
QueuePtr rear;//队尾指针
}LinkQueue;
void InitStack(SqStack *s)
{//构造一个空栈
s->base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));
s->top=s->base;
s->stacksize=STACK_INIT_SIZE;
}
void Push(SqStack *s,char e)
{//插入元素e为新的栈顶元素
if(s->top-s->base>=STACK_INIT_SIZE)
{
s->base=(char*)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(char));
s->top=s->base+s->stacksize;
s->stacksize+=STACKINCREMENT;
}
*(s->top)=e;
s->top++;
}
void Pop(SqStack *s,char *e)
{//元素e出栈
*e=*--s->top;
}
int StackEmpty(SqStack s)
{//判断栈是否为空
if(s.top==s.base)
return 1;
else return 0;
}
void ClearStack(SqStack *s)
{//清空栈
s->top=s->base;
}
void InitQueue(LinkQueue *q)
{//构造一个空队列
q->front=q->rear=(QNote*)malloc(sizeof(QNote));
q->front->next=NULL;
}
void EnQueue(LinkQueue *q,char e)
{//插入元素e为新的队尾元素
QNote *p;
p=(QNote*)malloc(sizeof(QNote));
p->data=e;
p->next=NULL;
q->rear->next=p;
q->rear=p;
}
void DeQueue(LinkQueue *q,char *e)
{//元素出队
QNote *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(char* ch,SqStack *s)
{//把字符数组从右至左压入栈中
int i,L=0;
while(ch[L]!=\0)
L++;
for(i=L-1;i>=0;i--)
Push(s,ch[i]);
}
int main()
{
printf("**************************************************************\n");
printf("* **************************** *\n");
printf("* * 魔王语言解释系统 * *\n");
printf("* **************************** *\n");
printf("**************************************************************\n");
int xunhuan=1;
printf("请输入您想要解释的魔王语言：\n");
while (xunhuan==1) //一个总循环控制整个程序的重复进行
{
char A[]="sae"; //大写字母作为字符数组名存放小写字母
char B[]="tsaedsae";
char flag=0; //flag用来标记处理括号
char e1,key,e2,e,i=0;
int mark=1; //标记输入的魔王语言是否在允许的范围之内
int f=1; // 判断括号是否匹配
char MoWang[100]="\0"; //定义一个魔王变量，存放待解释的语言字符
SqStack S; //作为栈存储元素，为后续操作和输出做准备
SqStack temp; //用来处理括号外的元素
InitStack(&S);
InitStack(&temp);
LinkQueue Q;
InitQueue(&Q);
gets(MoWang); //变量MoWang存储输入的语言
InStack(MoWang,&S); //把要解释的魔王语言压入栈中
while(!StackEmpty(S)) //把魔王语言进行出栈，不符合语言的进行提示
{
Pop(&S,&e1);
if(e1==()
{
if(StackEmpty(S))
{
printf("魔王语言错误!\n");
mark=0;f=0;
break;
}
while(!StackEmpty(S))
{
Pop(&S,&e1);
if(e1==))
{
if(i==0)//判断是否存在空括号（本程序设空括号为非法语言）
f=0;
break;
}
else if(!(e1>=a&&e1<=z)&&!(e1>=A&&e1<=Z))
{
printf("魔王语言错误！\n");
mark=0;
break;
}
i++;
}
if(mark==0)
break;
if(f!=1)
{
printf("魔王语言错误！\n");
break;
}
}
else if(e1==))
{
printf("魔王语言错误！\n");
mark=0;
break;
}
else if(!(e1>=a&&e1<=z)&&!(e1>=A&&e1<=Z))
{
printf("魔王语言错误！\n");
mark=0;
break;
}
}
if(mark==1&&f==1) //对符合语言规则的魔王语言进行规则处理
{
ClearStack(&S);
InStack(MoWang,&S); //把魔王语言从右至左压栈存放
while(!StackEmpty(S)) //栈不空时，用栈temp进行存储不带括号内元素的元素
{
Pop(&S,&e1);
if(e1==B||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); //将队头的元素赋值给key
}
else
Push(&temp,e1);
}
while(!StackEmpty(temp)) //将魔王说的语言规则地压入栈s中
{
Pop(&temp,&e1);
if(e1!=flag)
Push(&S,e1); //把括号外的元素压入栈s中
else
{
while(!QueueEmpty(Q)) //处理括号中的元素进栈
{
DeQueue(&Q,&e2);
Push(&S,key);
Push(&S,e2);
}
Push(&S,key); //最后还要压一个key
}
}
printf("解释后的语言为：\n");
while(!StackEmpty(S)) //依次出栈输出处理后的元素
{
Pop(&S,&e);
EnQueue(&Q,e); //元素进队是为了输出对应汉字
if(e==B) printf("%s",B);
else if(e==A) printf("%s",A);
else printf("%c",e);
}
printf("\n");
while(!QueueEmpty(Q)) //翻译成对应的汉字
{
DeQueue(&Q,&e);
switch(e)
{
case t : printf("天");break;
case d : printf("地"); break;
case s : printf("上"); break;
case a : printf("一只"); break;
case e : printf("鹅"); break;
case z : printf("追"); break;
case g : printf("赶"); break;
case x : printf("下"); break;
case n : printf("蛋"); break;
case h : printf("恨"); break;
case B : printf("天上一只鹅地上一只鹅");break;
case A : printf("上一只鹅");break;
default : printf("(对不起此处为非法字符或词汇！)");break;
}
}
printf("\n");
}
printf("再次输入魔王语言(按数字键0退出)\n");
scanf("%d",&xunhuan);
}
return 0;
}
四、 调试分析
编译环境为CodeBlocks。