编译原理实验报告(设计和验证型).doc

课 程 实 验 报 告专 业 年 级 计算机科学与技术 课 程 名 称 编 译 原 理 指 导 教 师 学 生 姓 名 学 号 实 验 日 期 实 验 地 点 实 验 成 绩 教务处制2010年 月 日实验报告专业班级姓名学号课程名称编译原理实验名称一个顺序栈的基本运算实验实验编号实验一实验形式设计性实验类型认识与验证型实验学时2学时实验目的1了解掌握栈的相关知识。2学习并使用栈，并能建立栈。实验要求1. 建立一个字符栈。2. 所建栈有进栈、出栈、初始化栈、判断栈空、判断栈满、清栈和取栈顶元素这几个函数。实验内容建立一个字符栈，并有相应的配套函数。把字符串uwdweoqei#入栈并输出。实验步骤 #define wyo chartypedef structwyo data50;int top;stack;void InitStack(stack *s)/栈初始化s-top=-1;int StackEmpty(stack *s)/判栈空,空为if(s-top=-1)return 1;elsereturn 0;int StackFull(stack *s)/判栈满,满为if(s-top=50)return 1;elsereturn 0;void ClearStack(stack *s)/清栈s-top=-1;void Push(stack *s,wyo e)/入栈if(!StackFull(s)s-data+s-top=e;elsecoutdatas-top-;elsecoutdatas-top;elsecout栈空不能出栈。;return -1;void main()stack x;char y=NULL;InitStack(&x);couty;Push(&x,y);coutendl输出栈内字符串:;while(StackEmpty(&x)!=1)coutBD,D-FD,D-,F-+B,F-B,B-CE,E-GE,E-,G*C,G-/C,C-(A),C-i分别验证字符串i+(i-i*i)/i-i和i+(i-i*i)/ii是否合法.实验步骤 #define wyo chartypedef structwyo data50;int top;stack;void InitStack(stack *s)/栈初始化s-top=-1;int StackEmpty(stack *s)/判栈空,空为if(s-top=-1)return 1;elsereturn 0;int StackFull(stack *s)/判栈满,满为if(s-top=50)return 1;elsereturn 0;void ClearStack(stack *s)/清栈s-top=-1;void Push(stack *s,wyo e)/入栈if(!StackFull(s)s-data+s-top=e;elsecoutdatas-top-;elsecoutdatas-top;elsecout=0&x-1&cha(X)7)if(X=x)Pop(&N);Pop(&n);elsecout匹配不成功endl;return 0;elseif(X=#)if(x=#)cout匹配成功endl;return 1;elsecout匹配不成功=0&x=9)y=cha(i);elsey=cha(x);switch(X)case A:for(int i=0;i3;i+) Yyi=Ayi;break;case B:for(int i=0;i3;i+) Yyi=Byi;break;case C:for(int i=0;i3;i+) Yyi=Cyi;break;case D:for(int i=0;i3;i+) Yyi=Dyi;break;case E:for(int i=0;i3;i+) Yyi=Eyi;break;case F:for(int i=0;i3;i+) Yyi=Fyi;break;case G:for(int i=0;i3;i+) Yyi=Gyi;break;if(Yy0!=NULL)if(Yy0=)Pop(&N);elsePop(&N);if(Yy2!=NULL)Push(&N,Yy2);if(Yy1!=NULL)Push(&N,Yy1);if(Yy0!=NULL)Push(&N,Yy0);elsecout匹配不成功endl;return 0;void main()stack x,z;char y=NULL;InitStack(&x);InitStack(&z);cout输入需要验证的字符串,以#号结束:y;Push(&x,y);while(StackEmpty(&x)!=1)Push(&z,Pop(&x);yan(z); 实验结果与分析 教师评语成绩评定：指导教师签名：实验报告专业班级姓名学号课程名称编译原理实验名称中缀表达式转换为后缀表达式实验编号实验三实验形式设计性实验类型认识与验证型实验学时2学时实验目的1掌握并了解什么是中缀表达式，什么是后缀表达式。2学会如何把中缀表达式转换为后缀表达式。实验要求在实验一的基础上，设计一个函数，此函数的功能是把中缀表达式转换为后缀表达式。实验内容输入字符串k+k-k+(k*k+k-k)/k-k,输出这个字符串的后缀表达式。实验步骤 #define wyo charchar M50;int m(0);typedef structwyo data50;int top;stack;void InitStack(stack *s)/栈初始化s-top=-1;int StackEmpty(stack *s)/判栈空,空为if(s-top=-1)return 1;elsereturn 0;int StackFull(stack *s)/判栈满,满为if(s-top=50)return 1;elsereturn 0;void ClearStack(stack *s)/清栈s-top=-1;void Push(stack *s,wyo e)/入栈if(!StackFull(s)s-data+s-top=e;elsecoutdatas-top-;elsecoutdatas-top;elsecout栈空不能出栈。;return -1;int you(char ch)/确定运算符优先级switch(ch)case (:return 0;case +:case -:return 1;case /:case *:return 2;case ):return 3;default:return -1;void li()/中缀表达示转换为后缀表达示stack x,y;InitStack(&x);InitStack(&y);char z=NULL;cout输入中缀表达式，以#号结束：z;Push(&x,z);while(StackEmpty(&x)!=1)Push(&y,Pop(&x);while(Seqtop(&y)!=#)if(you(Seqtop(&y)=-1)/y栈顶为数字时，把y出栈入M队列Mm+=Pop(&y);continue;if(you(Seqtop(&y)=0)/y栈顶为（时，把y出栈入X栈Push(&x,Pop(&y);continue;if(you(Seqtop(&y)=3)/y栈顶为）时，把y出栈，把x栈里（后的符号都入M队列，在把（出栈Pop(&y);while(you(Seqtop(&x)!=0)Mm+=Pop(&x);Pop(&x);continue;if(you(Seqtop(&y)=2|you(Seqtop(&y)=1)/当x为空时把y栈顶入x栈。如x不为空，y栈顶的优先级小于等于x栈顶优先级时把x栈顶入M队列直到yx,最后把y入xif(StackEmpty(&x)=1)Push(&x,Pop(&y);elsewhile(you(Seqtop(&y)=you(Seqtop(&x)Mm+=Pop(&x);if(StackEmpty(&x)=1)break;Push(&x,Pop(&y);continue;while(StackEmpty(&x)!=1)/把X余下的元素入M队列Mm+=Pop(&x);cout后缀表达式为：;for(int i=0;i=m;i+)/输出后缀表达式coutMi;coutBD,D-FD,D-,F-+B,F-B,B-CE,E-GE,E-,G*C,G-/C,C-(A),C-i2+(8-2*2)/4-1实验步骤 #define wyo charchar M50;int m(0);typedef structwyo data50;int top;stack;void InitStack(stack *s)/栈初始化s-top=-1;int StackEmpty(stack *s)/判栈空,空为if(s-top=-1)return 1;elsereturn 0;int StackFull(stack *s)/判栈满,满为if(s-top=50)return 1;elsereturn 0;void ClearStack(stack *s)/清栈s-top=-1;void Push(stack *s,wyo e)/入栈if(!StackFull(s)s-data+s-top=e;elsecoutdatas-top-;elsecoutdatas-top;elsecout=0&x-1&cha(X)7)if(X=x)Pop(&N);Pop(&n);elsecout匹配不成功endl;return 0;elseif(X=#)if(x=#)cout匹配成功endl;return 1;elsecout匹配不成功=0&x=9)y=cha(i);elsey=cha(x);switch(X)case A:for(int i=0;i3;i+) Yyi=Ayi;break;case B:for(int i=0;i3;i+) Yyi=Byi;break;case C:for(int i=0;i3;i+) Yyi=Cyi;break;case D:for(int i=0;i3;i+) Yyi=Dyi;break;case E:for(int i=0;i3;i+) Yyi=Eyi;break;case F:for(int i=0;i3;i+) Yyi=Fyi;break;case G:for(int i=0;i3;i+) Yyi=Gyi;break;if(Yy0!=NULL)if(Yy0=)Pop(&N);elsePop(&N);if(Yy2!=NULL)Push(&N,Yy2);if(Yy1!=NULL)Push(&N,Yy1);if(Yy0!=NULL)Push(&N,Yy0);elsecout匹配不成功endl;return 0;void jisuan()int x,y,i,n=0,ans50;for(int i=0;im;i+)if(Mi=0)ansn+=Mi-0;elseswitch(Mi)case +:x=ans-n;y=ans-n;ansn+=y+x;break;case -:x=ans-n;y=ans-n;ansn+=y-x;break;case *:x=ans-n;y=ans-n;ansn+=y*x;break;case /:x=ans-n;y=ans-n;ansn+=y/x;break;cout计算结果为：ans-nendl;int you(char ch)/确定运算符优先级switch(ch)case (:return 0;case +:case -:return 1;case /:case *:return 2;case ):return 3;default:return -1;void li()/中缀表达示转换为后缀表达示stack x,y;InitStack(&x);InitStack(&y);char z=NULL;cout输入中缀表达式，以#号结束：z;Push(&x,z);while(StackEmpty(&x)!=1)Push(&y,Pop(&x);if(yan(y)=1)while(Seqtop(&y)!=#)if(you(Seqtop(&y)=-1)/y栈顶为数字时，把y出栈入M队列Mm+=Pop(&y);continue;if(you(Seqtop(&y)=0)/y栈顶为（时，把y出栈入X栈Push(&x,Pop(&y);continue;if(you(Seqtop(&y)=3)/y栈顶为）时，把y出栈，把x栈里（后的符号都入M队列，在把（出栈Pop(&y);while(you(Seqtop(&x)!=0)Mm+=Pop(&x);Pop(&x);continue;if(you(Seqtop(&y)=2|you(Seqtop(&y)=1)/当x为空时把y栈顶入x栈。如x不为空，y栈顶的优先级小于等于x栈顶优先级时把x栈顶入M队列直到yx,最后把y入xif(StackEmpty(&x)=1)Push(&x,Pop(&y);elsewhile(you(Seqtop(&y)=you(Seqtop(&x)Mm+=Pop(&x);if(StackEmpty(&x)=1)break;Push(&x,Pop(&y);continue;while(StackEmpty(&x)!=1)/把X余下的元素入M队列Mm+=Pop(&x);cout后缀表达式为：;for(int i=0;i=m;i+)/输出后缀表达式coutMi;coutendl;jisuan();void main()li(); 实验结果与分析教师评语成绩评定：指导教师签名：