实验3-逆波兰式的产生及计算

河南工业大学实验报告课程名称编译原理_实验项目实验三逆波兰式的产生及计算院系____信息科学与工程学院____专业班级__计科F1201班________姓名____张伟龙___________学号_____201216010313_____指导老师阎娟日期2015.5.7批改日期成绩一.实验目的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.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；三.实验过程#includeiostream#includealgorithm#includestring#includestackusingnamespacestd;/*************************************************题目：将中缀后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。我们假设输入的中缀表达式都是合法的函数:cal():计算算符优先级compute():计算表达式ace():出栈计算Author:dezhonger************************************************/constdoubleEPS=1e-6;#defineDIVIDEBYZEROdivideByZero//除零错误#defineGOODgoodstrings,ans,FLAG;stackcharst;//符号栈stackdoublesd;//数字栈intcal(charc){switch(c){case'+':case'-':return1;case'*':case'/':return2;default:return-123456;}}doublecompute(charc,doublea,doubleb){switch(c){case'+':returna+b;case'-':returna-b;case'*':returna*b;case'/':{if(fabs(b)EPS)FLAG=DIVIDEBYZERO;returna/b;}default:return-123456;}}voidact(){ans+=st.top();doublea=sd.top();sd.pop();doubleb=sd.top();sd.pop();//coutst.top()baendl;doublec=compute(st.top(),b,a);sd.push(c);st.pop();}intmain(){freopen(in.txt,r,stdin);cout姓名：张伟龙学号：201216010313班级：计科1201endlendl;while(cins){cout中缀表达式为:sendl;ans=;FLAG=GOOD;while(!st.empty())st.pop();while(!sd.empty())sd.pop();st.push('#');intl=s.length();for(inti=0;il;i++){charc=s[i];if(isdigit(c)){doubletemp=0;if(isdigit(ans[ans.length()-1]))ans+='&';while(isdigit(s[i])){ans+=s[i];temp=temp*10+s[i++]-'0';}sd.push(temp);i--;}elseif(c=='#');elseif(c=='(')st.push(c);elseif(c==')'){while(st.top()!='('){act();}st.pop();}else{while(cal(c)=cal(st.top())){act();}st.push(c);}}while(st.top()!='#'){act();}cout对应的后缀表达式为:ansendl;if(FLAG==GOOD)cout该式子的结果为:sd.top()endl;elsecout式子中有除0错误endl;coutendl;}return0;}四.实验总结（心得）通过这次的实验，知道了算符优先文法的概念以及这个文法的简单应用。通过对中缀表达式转化为后缀表达式的实验，我对算符优先级有了更深的理解。并解决了如何构造这些优先级以及如何运用他们来计算后缀表达式，同时计算出表达式的结果。算符优先文法是一种自下而上的分析法，其文法的特点是文法的产生式中不含两个相邻的非终结符。一般的表达式就属于这种文法。