魔王语言解释-数据结构课程设计

实习2、魔王语言解释

一、需求分析

1.问题描述

有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没人能听的懂，但他的语言

是可以逐步解释成人能懂得语言的，因为他的语言是由以下两种形式的规则由人的语言逐步抽象

上去的：

(1)a->p1P2...pn

(2)(96162...6n)—>06n95n-l...0619

在这两种形式中，从左到右均表示解释。试写一个魔王解释系统，把他的话解释成人能听懂

得话。

2.基本要求

用下述两条具体规则和上述规则形式(2)实现。设大写字母表示魔王语言的词汇；小

写字母表示人的语言词汇；希腊字母表示可以用大写或小写字母代换的变量。魔王语言可含人

的词汇。

(1)B—>tAdA

(2)A—>sae

3.测试数据

B(ehnxgz)B解释成tsaedsaeezegexenehetsaedsae

若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是“天上一个鹅地上一个鹅

鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一个鹅地上一个鹅”。

tdSaeZgXnh

天地上-只鹅追赶下蛋恨

4.实现提示

将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈，将字母顺序

入队列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简单，请读者思

考如何处理。应首先实现栈和队列的基本操作。

二、概要设计

1、设定栈的抽象数据类型定义：

ADTStack{

数据对象：D={a|aGCharSet,i=1,2,.......nvn>0}

数据关系：Rl={<a',a>|a,aD,a<a,i=l,2........,n}

i-lii-lii-1i

基本操作：

InitStackC*S)

操作结果：构造一个空栈。

Push(*S,e)

初始条件：栈S已存在

操作结果：在栈顶插入新的元素。

Pop(*S,*e)

初始条件：栈S已存在

操作结果：删除栈顶元素，并用e返回其值。

StackEmpty(S)

初始条件：栈S已存在

操作结果：若S为空栈，则返回1,否则返回Oo

ClearStack(*S)

初始条件：栈S已存在操

作结果：将栈S清空。

InStack(char*ch,SqStack*s)

初始条件：栈S已存在

操作结果：把字符数组从右至左压入栈中。

}ADTStack

ADTQueue{

数据对象：D={ai|aiCharSeti=1,2,.......n,.n20)

数据关系：Rl={<ai-l,ai>|ai-l,ai^Dti=1,2,.......n}

基本操作：

InitQueue(*Q)

操作结果：构造一个空队列Q。

EnQueue(*Q,e)

初始条件：队列Q已经存在。

操作结果：插入元素e为Q的新的队尾元素。

DeQueue(*Q,*e)

初始条件：队列Q已经存在。

操作结果：删除Q的对头元素，并以e返回其值。

QueueEmpty(Q)

初始条件：队列Q已经存在。

操作结果：若队列Q为空栈，则返回I,否则返回0。

(ADTQueue

三、详细设计(源代码)

(使用C语言)

#include<stdio.h>

#include<stdlib.h>

/♦defineSTACK_INIT_SIZE100〃存储空间初始分配量

#defineSTACKINCREMENT10〃存储空间分配增量

typedefstruct

(

char*base;〃栈底指针

char*top;〃栈顶指针

intstacksize;

}SqStack;

typedefstructQNote

(

chardata;

structQNote*next;

}QNote,*QueuePtr;

typedefstruct

(

QueuePtrfront;〃队头指针

QueuePtrrear;〃队尾指针

}LinkQueue;

voidlnitStack(SqStack*s)

{〃构造一个空栈

s->base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));

s->top=s->base;

s->stacksize=STACK_INIT_SIZE;

)

voidPush(SqStack*s,chare)

{//插入元素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++;

)

voidPop(SqStack*s,char*e)

{//元素e出栈

*e=*-s->top;

)

intStackEmpty(SqStacks)

{//判断栈是否为空

if(s.top==s.base)

return1;

elsereturn0;

voidClearStack(SqStack*s)

{〃清空栈

s->top=s->base;

voidlnitQueue(LinkQueue*q)

{//构造一个空队列

q->front=q->rear=(QNote*)malloc(sizeof(QNote));

q->front->next=NULL;

)

voidEnQueue(LinkQueue*q,chare)

{//插入元素e为新的队尾元素QNote

*P；

p=(QNote*)malloc(sizeof(QNote));

p->data=e;

p->next=NULL;

q->rear->next=p;

q->rear=p;

)

voidDeQueue(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);

intQueueEmpty(LinkQueueq)

{//判断队列是否为空

if(q.front==q.rear)

return1;

else

return0;

}

voidlnStack(char*ch,SqStack*s)

{//把字符数组从右至左压入栈中

inti,L=0;

while(ch[L]!='\0')

L++；

for(i=L-l;i>=0;i-)

Push(s,ch[i]);

intmain()

prjntf(”*************************************************************

****************************

printfC**\n");

printf("**魔王语言解释系统**\n");

****************************

printf("**\n");

prjntf(”**************************************************************'n'').

intxunhuan=l;

printf("请输入您想要解释的魔王语言：\n");

while(xunhuan==l)〃一个总循环控制整个程序的重复进行

charA[]=Hsae";〃大写字母作为字符数组名存放小写字母

charB[]="tsaedsae";

charflag='O';//flag用来标记处理括号

chareLkey,e2,e,i=0;

intmark=l;〃标记输入的魔王语言是否在允许的范围之内

intf=l;//判断括号是否匹配

charMoWang[100]="\0";〃定义一个魔王变量，存放待解释的语言字符

SqStackS;〃作为栈存储元素，为后续操作和输出做准备

SqStacktemp;〃用来处理括号外的元素

lnitStack(&S);

lnitStack(&temp);

LinkQueueQ;

lnitQueue(&Q);

gets(MoWang);〃变量MoWang存储输入的语言

lnStack(MoWang,&S);〃把要解释的魔王语言压入栈中

while(!StackEmpty(S))〃把魔王语言进行出栈，不符合语言的进行提示

Pop(&S,&el);

if(el=='(')

(

if(StackEmpty(S))

(

printf(“魔王语言错误!\n“);

mark=O;f=O;

break;

}

while)!StackEmpty(S))

Pop(&S,&el);

if(el==')')

if(i==O)〃判断是否存在空括号(本程序设空括号为非法语言)

f=0;

break;

)

elseif(!(el>='a,&&el<=,z,)&&!(el>=,A'&&el<='Z'))

(

printf("魔王语言错误！\n");

mark=O;

break;

)

if(mark==O)

break;

if(f!=l)

(

printf("魔王语言错误!\n");

break;

)

)

elseif(el==')')

(

printf(“魔王语言错误!\n");

mark=O;

break;

}

elseif(!(el>=,a,&&el<=,z')&&!(el>=,A,&&el<=,Z'))

printf("魔王语言错误!\n");

mark=O;

break;

)

)

if(mark==l&&f==l)〃对符合语言规则的魔王语言进行规则处理

ClearStack(&S);

lnStack(MoWang,&S);〃把魔王语言从右至左压栈存放

while(!StackEmpty(S))〃栈不空时.，用栈temp进行存储不带括号内元素

的元素

Pop(&S,&el);

if(el=='B'||el=='A')

Push(&temp,el);

elseif(el=='(')〃用队存储括号中的元素

(

Push(&temp,flag);〃有括号的话就用flag标记

Pop(&S,&el);

while(el!=')')〃把括号中的元素存入队列中

(

EnQueue(&Cbel);

Pop(&S,&el);

)

if(!QueueEmpty(Q))

DeQueue(&Q,&key);//将队头的元素赋值给key

}

else

Push(&temp,el);

)

while(!StackEmpty(temp))〃将魔王说的语言规则地压入栈s中

(

Pop(&temp,&el);

if(el!=flag)

Push(&S,el);〃把括号外的元素压入栈s中

else

while(!QueueEmpty(Q))〃处理括号中的元素进栈

(

DeQueue(&Q,&e2);

Push(&Szkey);

Push(&Sze2);

)

Push(&S,key);〃最后还要压一个key

)

)

printf(“解释后的语言为：\n");

while(!StackEmpty(S))〃依次出栈输出处理后的元素

(

Pop(&S,&e);

〃元素进队是为了输出对应汉字

EnQueue(&Qze);

if(e=='B')printf(”％s”,B);

elseif(e==,A')printf("%s",A);

elseprintf(”%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':printff'一只"）;break;

case'e'：printf（"鹅"）；break；

case'z':printf（"追"）;break;

case'g':printf（"0"）;break;

case'x':printf（"下"）；break;

case'n':printf（"蛋"）;break;

case'h':printf（"恨"）;break;

case'B':printf（"天上一只鹅地上一只鹅"）;break;

case'A':printf（"上一只鹅"）;break