(编译原理)逆波兰式算法的源代码

1/8一.实验目的1．深入理解算符优先分析法2．掌握FirstVt和LastVt集合的求法有算符优先关系表的求法3．掌握利用算符优先分析法完成中缀表达式到逆波兰式的转化二.实验内容及要求将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。程序输入/输出示例：输出的格式如下：(1)逆波兰式的生成及计算程序，编制人：姓名，学号，班级(2)输入一以#结束的中缀表达式(包括+—*/（）数字#)：在此位置输入符号串如(28+68)*2#(3)逆波兰式为：28&68+2*(4)逆波兰式28&68+2*计算结果为192备注：(1)在生成的逆波兰式中如果两个数相连则用&分隔，如28和68，中间用&分隔；(2)在此位置输入符号串为用户自行输入的符号串。注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、数字，结束符#；2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；三.实验过程1、逆波兰式定义将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。采用逆波兰式可以很好的表示简单算术表达式，其优点在于易于计算机处理表达式。2、产生逆波兰式的前提中缀算术表达式3、逆波兰式生成的实验设计思想及算法2/8(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。(2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。(3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。(4)如果不是数字，该字符则是运算符，此时需比较优先关系。做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算否出错处理否否是是是是否是否输入一个中缀式表示的简单运算表达式‘#’入栈sym=当前输入符号sym是数字吗?对数字进行处理，形成一个数字串栈顶运算符优先级低于sym吗?将向前看符号入栈栈顶运算符与sym优先级相等吗?将栈顶运算符弹出，且输出栈顶运算符优先级高于sym吗栈顶是’(‘且sym为’）吗栈顶运算符出栈程序结束3/8符从栈中弹出，将该字符入栈。(5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。3、逆波兰式计算的实验设计思想及算法(1)构造一个栈，存放运算对象。(2)读入一个用逆波兰式表示的简单算术表达式。(3)自左至右扫描该简单算术表达式并判断该字符，如果该字符是运算对象，则将该字符入栈。若是运算符，如果此运算符是二目运算符，则将对栈顶部的两个运算对象进行该运算，将运算结果入栈，并且将执行该运算的两个运算对象从栈顶弹出。如果该字符是一目运算符，则对栈顶部的元素实施该运算，将该栈顶部的元素弹出，将运算结果入栈。(4)重复上述操作直至扫描完整个简单算术表达式的逆波兰式，确定所有字符都得到正确处理，我们便可以求出该简单算术表达式的值。4.实验的源程序代码如下：#includestdio.h#includemath.h#definemax100charex[max]。/*存储后缀表达式*/voidtrans(){/*将算术表达式转化为后缀表达式*/读入一个逆波兰算术表达式sym=当前输入符号sym是运算符吗?将该字符入栈根据运算符的特点从栈顶部取出若干个运算对象进行该运算将运算结果入栈程序结束否是Sym=‘#’否是4/8charstr[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]!='('){5/8ex[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++)6/8printf(%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--。7/8break。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])。}main(){trans()。compvalue()。}5.程序的运行结果如下：8/8四.实验总结（心得）通过本实验的学习，主要掌握了逆波兰式算法的含义，结合书本知识，让我更加清楚此算法实现的主要过程，以及使用该算法的好处，通过对程序实现的分析，对于逆波兰式算法的细节了解的更加清楚，从中学到了很多的东西。