版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
实习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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024-2029年中国顺风车行业市场现状分析及竞争格局与投资发展研究报告
- 责任与诚信演讲稿(3篇)
- 昆虫记读后感15篇
- 木材合同购销合同6篇
- 汽车修理厂合伙协议书(3篇)
- 矛与盾课件10篇
- 教学反思简短【15篇】
- 驱动系统数字化改造项目可行性研究报告写作模板-备案审批
- 数字政府应用服务规范 第5部分:业务流程服务接口规范(征求意见稿)
- 人力资源的薪酬体系设计
- 科学与工程教育(STEM)2035行动计划-2024.08-28正式版-WN8
- 课件第一章信息技术基础知识
- 2024年个人信用报告(个人简版)样本(带水印-可编辑)
- 16J914-1 公用建筑卫生间
- 信息资源建设-习题集(含答案)
- 学校项目式学习实施方案
- 经典绘本《失落的一角》课件
- 国际音标KK音标对照表
- (精选)承担基层医疗机构中医药人才培训制度、保障措施和培训方案
- 辊道窑使用维修说明手册
- 年产450万米管桩生产线项目可行性研究报告
评论
0/150
提交评论