魔王语言
魔王语言解释
实验目的
问题描述:魔王总是使用自己的一种非常精练而抽象的语言讲话,没人能听懂,但他的语言是可逐步解释成人能听懂的语言,因为他的语言是由以下两种形式 1)α---> (a1)(a2)....(am)
2)(αβ1β2β3β4)---->αβ4αβ3αβ2αβ1α
在这两种形式中,从左到右均表示解释.试写一个魔王语言的解释系统,将他的话解释成人能听得懂的话.基本要求:用下述两条具体规则和上述规则形式实现.设大写字母表示魔王语言的词汇,小写字母表示人的语言的词汇;希腊字母表示可以用大写字母或小写字母代换的变量.魔王语言可含人的词汇.,1, B --> tAdA A --> sae
测试数据B(ehnxgz)B 解释成 tsaedsaeezegexenehetsaedsae若将小写字母与汉字建立下表所示的对应关系,则魔王说的话是:"天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅
t d s a e z g h n x 天 地 上 一只 鹅 追 赶 下 蛋 恨
程序
首先要实现对于一些基本函数的操作将魔王的语言自右
至左进栈T,总是处理栈顶字符.中间加入对括号配对是否正确的判断。若是开括号,则逐一出栈,将字母顺序入队列,直至闭括号出栈,并按规则要求逐一出队列Q再处理后入栈S.再把栈S中元素进入队列W。栈T中其他情况直接进队列W,A->sae,B->tsaedsae,。再把队列W中字符输入到文件~再按字母与汉字的对应关系~把对应的汉字输入到另一个文件。
把括号中字符进按规则入栈S 栈T(前队列Q 面还利
用一个
中间栈)
若为A,sae依次进队列Q;
若为B;tsaedsae依次进队列Q
其他情况直接进队列Q
主要代码及注释
1.将魔王的语言自右至左进栈T:
while(*p!='#'){//字符串结尾为#
Push( S,*p);//先压入栈再调换次序
if(*p=='(' )i++;//i用于判断字母序列中括号是否配对 //正确
else if(*p==')')i--;
p++;}//先把字母序列压入栈S
if(i!=0){//判断括号是否是否配对正确
printf("输入错误");
exit(0);}
while(S.top!=S.base){//当栈S非空时执行循环
Pop(S,temp);
Push(T,temp);}//T相当于把元素从右往左压入栈得//到
2. 处理栈顶字符.若是开括号,则逐一出栈,将字母顺序入队列,直至闭括号出栈,并按规则要求逐一出队列Q再处理后入栈S.再把栈S中元素进入队列W。栈T中其他情况直接进队列W,A->sae,B->tsaedsae,。
if(temp=='(' ){//当出现‘,’直到‘,’结束 Pop(T,temp);
while(temp!=')'){//把括号内字符压入队列Q
EnQueue(Q,temp);
Pop(T,temp);}
DeQueue(Q,q);
Push(S,q);
while(Q.rear!=Q.front){//再把所有字符按规则压入栈S
DeQueue(Q,temp);//先取出字符
Push(S,temp);//再压入栈
Push(S,q);//按规则执行的操作~不能少
}
free(Q.base);//释放Q中存储单元
while(S.base!=S.top){//再把它压入队列~得到正
确的顺序和字符串
Pop(S,temp);
EnQueue(W,temp);
}
else if(temp=='B'){//如果字符B为把tsaedsae进队列
EnQueue(W,'t');EnQueue(W,'s');EnQueue (W,'a');
EnQueue(W,'e');EnQueue(W,'d');
EnQueue(W,'s');EnQueue (W,'a'); EnQueue(W,'e');
}
else if(temp=='A'){//如果字符A为把sae进队列
EnQueue(W,'s');EnQueue(W,'a');EnQueue(W,'e');
}
else EnQueue(W,temp);//其他情况直接进队列
}
free(T.base);free(S.base);//释放S.T中存储单元
3. 把队列W中字符输入到文件~再按字母与汉字的对应
关系~把对应的汉字输入到另一个文件
FILE *fp,*f;
if ((fp=fopen("字母.txt","w"))==NULL) {printf("Can
not open file\n");exit(-1);} if ((f=fopen("汉字.txt","w"))==NULL) {printf("Can not
open file\n");exit(-1);} while(W.rear!=W.front){
DeQueue(W,temp);
fprintf(fp,"%c",temp);//把字符入文件字母.txt
switch(temp){//把汉字入文件汉字.txt
case't':fprintf(f,"天");break;
case'd':fprintf(f,"地");break;
case's':fprintf(f,"上");break;
case'a':fprintf(f,"一只");break;
case'e':fprintf(f,"鹅");break;
case'z':fprintf(f,"追");break;
case'g':fprintf(f,"赶");break;
case'x':fprintf(f,"下");break;
case'n':fprintf(f,"蛋");break;
case'h':fprintf(f,"恨");break;}
}
实验心得
本次实验熟悉了站和队列的一下基本操作~重要的操作如:创建栈~元素入栈~元素出栈~释放栈的空间~创建队列~元素入队列~元素出队列~释放队列空间已经基本上掌握。解决了在程序编写的一些常见错误~规范程序语言。同时也掌握同时运用栈和队列的巧妙所在。在编写程序的过程中~慢慢推理~还是容易把次序弄错了~再栈和队列的实现过程中~次序非常重要~不能弄乱。
学习错误积累:1.Push(&S,&T)错误~应为Push(S,T)等等错误
2. 释放栈Q的操作为free(Q.base)
3.这次实验在读取字符串关于循环犯了一次错误。下面循环执行语句部分循序不能调换~否则可能会出现乱码
while(temp!=')'){
EnQueue(Q,temp);
Pop(T,temp);}
4还有主要是括号没配对好~导致一些语法错误 ~特别是在申请存储空间时。
附源代码:
#include
#include #define STACKSIZE 200 #define STACKINCRE 50 typedef int Status; typedef struct {
char *base;
char *top;
int stacksize;
}SqStack;
typedef struct {
char *base;
int front ;
int rear;
}Squeue;
Status InitStack(SqStack &S){//创建栈 S.base=(char*)malloc(STACKSIZE*sizeof(char));
if(!S.base) exit(-1);
S.top=S.base;
S.stacksize=STACKSIZE;
return 1;
}
Status Push(SqStack &S,char e){//把元素e压入栈S
if(S.top-S.base>=S.stacksize){
S.base=(char*)realloc(S.base,(S.stacksize+STACKINCRE)*s
izeof(char));
if(!S.base) exit(-1);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCRE;
}
*S.top++=e;
return 1;
}
Status Pop(SqStack &s,char &e){//e返回栈顶元素
if(s.top==s.base) return 0;
e=*--s.top;
return 1;
}
Status IniQueue(Squeue &Q){//创建队列
Q.base=(char *)malloc(300*sizeof(char));
if(!Q.base) exit(-1);
Q.front=0;Q.rear=0;
return 1;
}
Status EnQueue(Squeue &Q,char e){//把元素e压入队列
if((Q.rear+1)%200==Q.front) return 0;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%200;
return 1;
}
Status DeQueue(Squeue &Q,char &e){//e返回队列队头元素
if(Q.front==Q.rear) return 0;
e=Q.base[Q.front];
Q.front=(Q.front+1)%200;
return 1;
}
main(int argc,char *argv[]){
char *p,temp,q;int i=0;
SqStack S,T;Squeue Q,W;
p=*(++argv);
InitStack(S);InitStack(T);IniQueue(Q);IniQueue(W);
while(*p!='#'){
Push( S,*p);
if(*p=='(' )i++;
else if(*p==')')i--;
p++;}
if(i!=0){
printf("输入错误");
exit(0);}
while(S.top!=S.base){
Pop(S,temp);
Push(T,temp);}//T相当于把元素从右往左压入栈得到的
free(S.base);InitStack(S);
while(T.base!=T.top){
Pop(T,temp);
if(temp=='(' ){
Pop(T,temp);
while(temp!=')'){//先把括号内字符压入队列
EnQueue(Q,temp);
Pop(T,temp);}
DeQueue(Q,q);
Push(S,q);
while(Q.rear!=Q.front){//再把它压入栈
DeQueue(Q,temp);
Push(S,temp);
Push(S,q);
}
free(Q.base);
while(S.base!=S.top){//再把它压入队列~得到正确的顺序
和字符串
Pop(S,temp);
EnQueue(W,temp);
}
}
else if(temp=='B'){//如果字符B为把tsaedsae进队列
EnQueue(W,'t'); EnQueue(W,'s');EnQueue (W,'a'); EnQueue(W,'e');EnQueue (W,'d'); EnQueue(W,'s');EnQueue (W,'a'); EnQueue(W,'e');
}
else if(temp=='A'){//如果字符A为把sae进队列
EnQueue(W,'s');EnQueue(W,'a');EnQueue(W,'e');
}
else EnQueue(W,temp);//其他情况直接进队列
}
free(T.base);free(S.base);
FILE *fp,*f;
if ((fp=fopen("字母.txt","w"))==NULL) {printf("Can not open file\n");exit(-1);}
if ((f=fopen("汉字.txt","w"))==NULL) {printf("Can not
open file\n");exit(-1);}
while(W.rear!=W.front){
DeQueue(W,temp);
fprintf(fp,"%c",temp);
switch(temp){
case't':fprintf(f,"天");break;
case'd':fprintf(f,"地");break;
case's':fprintf(f,"上");break;
case'a':fprintf(f,"一只");break;
case'e':fprintf(f,"鹅");break;
case'z':fprintf(f,"追");break;
case'g':fprintf(f,"赶");break;
case'x':fprintf(f,"下");break;
case'n':fprintf(f,"蛋");break;
case'h':fprintf(f,"恨");break;} }
}