逆波兰式的产生与计算

计算机科学与技术系实验报告专业名称计算机科学与技术课程名称编译原理项目名称逆波兰式的产生与计算班级学号姓名同组人员无实验日期2016.12.21一、实验目的与要求：（简述本次实验要求达到的目的，涉及到的相关知识点，实验的具体要求。）目的：1、将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值；2、掌握自底向上分析中算符优先分析法的基本原理；3、掌握优先关系表的构造方法。要求：根据介绍的算术表达式文法编制调试算符优先分析程序，以便对任意输入的简单算术表达式进行分析。将用中缀式表示的算术表达式转换为用逆波兰式(后缀式)表示的算术表达式，并计算用逆波兰式表示的算术表达式的值。程序输入一以#结束的符号串，如：2*(3+4)#。输出过程如下：（1）逆波兰式(后缀式)为：2#3#4#+*；（2）（2）计算结果：14。二、实验内容（根据本次实验项目的具体任务和要求，完成相关内容，可包括：实验目的、算法原理、实验仪器、设备选型及连线图、算法描述或流程图、源代码、实验运行步骤、关键技术分析、测试数据与实验结果、其他）具体任务：输出的格式如下：(1)逆波兰式的生成及计算程序，编制人：姓名，学号，班级(2)输入一以#结束的中缀表达式(包括+—*/（）数字#)：在此位置输入符号串如(28+68)*2#(3)逆波兰式为：28&68+2*(4)逆波兰式28&68+2*计算结果为192备注：(1)在生成的逆波兰式中如果两个数相连则用&分隔，如28和68，中间用&分隔；(2)在此位置输入符号串为用户自行输入的符号串。原理：逆波兰式是将平时我们正常写入的表达式变成后缀式表达式，将符号后入，括号不入，逆波兰式根据符号对应的几目运算符，将输出几个操作数进行运算，因此将不需要括号来进行优先级。编写逆波兰式时，需要判别是数字还是符号，数字的话就将其入栈，符号的话就先入符号栈，再下一个符号来临入栈之前，将上一个入栈的符号入进存放操作数的数组，其中顺序必须依次来，不能乱，在符号入栈结束之后，符号栈中将还会剩有两个符号，开始和结束的，此时将这两个符号按顺序入栈即可，至此完成逆波兰式。流程图：代码：#includestdio.h#includestdlib.h#includemath.h#definemax100charex[max];//ex[]数组用来存放逆波兰式voidtrans(){charstr[max];charstack[max];//存表达式的符号charch;intsum,i,j,t,top=0;printf(*请输入一个求值的表达式，以#结束:\n);printf(**********************************************************\n);printf(您的算数表达式为：);i=0;//进行初始化，从键盘输入表达式do{i++;scanf(%c,&str[i]);//从键盘输入的字符装入字符数组str[]中}while(str[i]!='#'&&i!=max);//以#为结束sum=i;//i=输入字符的个数，sum=it=1;i=1;//i归1ch=str[i];//将数组的第一个字符给chi++;while(ch!='#')//当字符不为#时进入循环{switch(ch){case'('://字符为(时，top++;//当字符为(时，将该字符入栈stack[top]=ch;break;case')'://字符为)时while(stack[top]!='(')//当栈顶的元素不为左括号(时{ex[t]=stack[top];top--;t++;//当栈顶的元素不为左括号时，将现在栈顶中（以前的都进入数组}top--;//遇到（的时候直接跳过break;case'+'://字符为+时，case'-'://字符为-时，while(top!=0&&stack[top]!='('){ex[t]=stack[top];top--;t++;}top++;stack[top]=ch;break;case'*'://字符为*时，case'/'://字符为/时，while(stack[top]=='*'||stack[top]=='/'){ex[t]=stack[top];top--;t++;}top++;stack[top]=ch;break;case'':break;//字符为空格时，default:while(ch='0'&&ch='9'){ex[t]=ch;t++;ch=str[i];i++;//现在指针++为取读下一个字符}i--;//一开始进行了++ex[t]='#';t++;}ch=str[i];i++;}while(top!=0){ex[t]=stack[top];//在栈中元素中加上后面的符号t++;top--;}ex[t]='#';printf(*********************************************************\n);printf(原来表达式：);for(j=1;jsum;j++)printf(%c,str[j]);printf(\n*********************************************************\n);printf(逆波兰式：);for(j=1;jt;j++)printf(%c,ex[j]);}voidcompvalue(){floatstack[max],d;charch;intt=1,top=0;ch=ex[t];t++;while(ch!='#'){switch(ch){case'+':stack[top-1]=stack[top-1]+stack[top];top--;break;case'-':stack[top-1]=stack[top-1]-stack[top];top--;break;case'*':stack[top-1]=stack[top-1]*stack[top];top--;break;case'/':if(stack[top]!=0)stack[top-1]=stack[top-1]/stack[top];else{printf(\n\t除零错误!\n);exit(0);}top--;break;default:d=0;while(ch='0'&&ch='9'){d=ch-'0';//现在ch存的是数字的ASCII码将ch转换成要表达的数字ch=ex[t];t++;}top++;stack[top]=d;}ch=ex[t];t++;}printf(\n*********************************************************\n);printf(计算结果为:%g\n,stack[top]);}main(){trans();compvalue();}实验分析都已经在代码后面进行了详细注释。截图：实验结果与手动计算结果一致。三、实验分析与小结：（实验过程中的问题分析、产生的原因以及解决方法；实验结果分析；有待优化思路）经过这个实验的练习，通过对程序的分析，对逆波兰式有了更详细的了解，本来对逆波兰式的符号和操作数的先后顺序还有一些不清楚，但是在了解完这个程序就就对逆波兰式很清楚了，了解了逆波兰式的原理，程序分析的时候，在把输入的符号串进行分析的时候，需要一个个进行判断输入的符号是否是操作数还是符号，将其进行分开存放，在下一个运算符进栈的时候，将前一个不是括号的符号入数组，碰见括号需要特别处理，因为在逆波兰式中并不需要括号，所以括号不需要入数组，需要跳过，在识别的时候也需要特别处理。当其分析完毕后，将符号进行相应的运算即可，这里识别符号是几目运算符很重要，因为是几目运算符将决定输出的操作数的个数。这个程序一开始进行分析的时候有点困难，有的点不是很清楚，然后记下来和同学进行讨论和理解，将我们各自理解的说出来以后进行综合就发现问题迎刃而解了，有的时候自己一个人理解会陷入怪圈，和同学一些讨论会更有助于理解和增长知识。四、其它无得分（百分制）