逆波兰式的产生及计算

河南工业大学实验报告课程编译原理实验名称逆波兰式的产生及计算系别___河南工业大学信息科学与工程学院_专业班级___计科0905___实验日期2012年5月3日姓名___杨金锋____学号_200948140512____实验指导教师___阎娟___一、实验目的和要求1．深入理解算符优先分析法2．掌握FirstVt和LastVt集合的求法有算符优先关系表的求法3．掌握利用算符优先分析法完成中缀表达式到逆波兰式的转化二、实验内容将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。(1)逆波兰式的生成及计算程序，编制人：姓名，学号，班级(2)输入一以#结束的中缀表达式(包括+—*/（）数字#)：在此位置输入符号串如(28+68)*2#(3)逆波兰式为：28&68+2*(4)逆波兰式28&68+2*计算结果为192三、实验步骤1、基于实验的内容，构造程序所需的模块2、根据已建构的模块，写出各个模块的相应程序代码3、在主函数中调用模块来完成所要得到的效果此程序主要包括两个运算函数和一个主函数：将算术表达式转化为后缀表达式：voidtrans(){/*将算术表达式转化为后缀表达式*/charstr[max];/*存储原算术表达式*/charstack[max];/*作为栈使用*/charch;intsum,i,j,t,top=0;printf(*****************************************\n);printf(*输入一个求值的表达式，以#结束。*\n);printf(******************************************\n);printf(算数表达式：);i=0;/*获取用户输入的表达式*/do{i++;scanf(%c,&str[i]);}while(str[i]!='#'&&i!=max);sum=i;t=1;i=1;ch=str[i];i++;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\t原来表达式：);for(j=1;jsum;j++)printf(%c,str[j]);printf(\n\t后缀表达式：,ex);for(j=1;jt;j++)printf(%c,ex[j]);}计算后缀表达式的值：voidcompvalue(){/*计算后缀表达式的值*/floatstack[max],d;/*作为栈使用*/charch;intt=1,top=0;/*t为ex下标，top为stack下标*/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=10*d+ch-'0';/*将数字字符转化为对应的数值*/ch=ex[t];t++;}top++;stack[top]=d;}ch=ex[t];t++;}printf(\n\t计算结果:%g\n,stack[top]);}最后为主函数：voidmain(){printf(逆波兰式的产生及计算程序：姓名：杨金锋学号：200948140512班级：计科0905\n);trans();compvalue();}四、实验过程记录：1.exit()函数头文件问题#includestdlib.h2．程序源代码#includestdio.h#includemath.h#includestdlib.h#definemax100charex[max];/*存储后缀表达式*/voidtrans(){/*将算术表达式转化为后缀表达式*/charstr[max];/*存储原算术表达式*/charstack[max];/*作为栈使用*/charch;intsum,i,j,t,top=0;printf(*****************************************\n);printf(*输入一个求值的表达式，以#结束。*\n);printf(******************************************\n);printf(算数表达式：);i=0;/*获取用户输入的表达式*/do{i++;scanf(%c,&str[i]);}while(str[i]!='#'&&i!=max);sum=i;t=1;i=1;ch=str[i];i++;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\t原来表达式：);for(j=1;jsum;j++)printf(%c,str[j]);printf(\n\t后缀表达式：,ex);for(j=1;jt;j++)printf(%c,ex[j]);}voidcompvalue(){/*计算后缀表达式的值*/floatstack[max],d;/*作为栈使用*/charch;intt=1,top=0;/*t为ex下标，top为stack下标*/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=10*d+ch-'0';/*将数字字符转化为对应的数值*/ch=ex[t];t++;}top++;stack[top]=d;}ch=ex[t];t++;}printf(\n\t计算结果:%g\n,stack[top]);}voidmain(){printf(逆波兰式的产生及计算程序：姓名：杨金锋学号：200948140512班级：计科0905\n);trans();compvalue();}3.运行结果五、实验总结：此次试验为逆波兰式的产生及计算，其中用到FirstVt和ListVt集合的求法与算符优先关系表的求法，，还有利用算符优先分析法完成中缀表达式到逆波兰式的转化，通过实验，让我对以上在课本中学过的知识在实践中的运用更加熟练，让我受益匪浅。