实验三-逆波兰表达式的产生及计算

江苏科技大学计算机学院编译原理实验报告0941901228章进兴实验三逆波兰表达式的产生及计算一、实验目的非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。二、实验内容将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。三、逆波兰表达式的产生及计算实验设计思想及算法逆波兰式定义将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。产生逆波兰式的前提中缀算术表达式逆波兰式生成的设计思想及算法(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。(2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。(3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。(4)如果不是数字，该字符则是运算符，此时需比较优先关系。做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。(5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。江苏科技大学计算机学院编译原理实验报告0941901228章进兴运用以上算法分析表达式(a+b*c)*d的过程如下：当前符号输入区符号栈输出区（a+b*c)*da+b*c)*d(+*c)*d(abc)*d(+a*)*d(+abc*d(+*ab)*d(+*abc)*d(+abc*)d(abc**abc*+d*abc*+*abc*+dabc*+d江苏科技大学计算机学院编译原理实验报告0941901228章进兴(1)构造一个栈，存放运算对象。(2)读入一个用逆波兰式表示的简单算术表达式。(3)自左至右扫描该简单算术表达式并判断该字符，如果该字符是运算对象，则将该字符入栈。若是运算符，如果此运算符是二目运算符，则将对栈顶部的两个运算对象进行该运算，将运算结果入栈，并且将执行该运算的两个运算对象从栈顶弹出。如果该字符是一目运算符，则对栈顶部的元素实施该运算，将该栈顶部的元素弹出，将运算结果入栈。(4)重复上述操作直至扫描完整个简单算术表达式的逆波兰式，确定所有字符都得到正确处理，我们便可以求出该简单算术表达式的值。逆波兰式计算的设计思想及算法四、实验要求1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。2、如果遇到错误的表达式，应输出错误提示信息。3、程序输入/输出实例：输入以#结束的中缀表达式(包括+-*/（）数字#)。江苏科技大学计算机学院编译原理实验报告0941901228章进兴例：(1)（a+b）(2)(a+b*c)(3)B+(-(A))*C输出逆波兰表达式的格式如下：(1)(a+b);→ab+)((2)(a+b*c)→abc*+)((3)B+(-A(A))*C→BA)(-)(C*+输入中缀表达式并计算结果：a*(b+c)+(-d)#；输出逆波兰式:abc+*d@+输入：a=3;b=1;c=2;d=5;计算结果为:4五、实验步骤1、根据流程图编写出各个模块的源程序代码上机调试。2、编制好源程序后，设计若干用例对系统进行全面的上机测试，并通过所设计的逆波兰式的产生及计算程序；直至能够得到完全满意的结果。江苏科技大学计算机学院编译原理实验报告0941901228章进兴3、书写实验报告；实验报告正文的内容：描述逆波兰式的产生及计算程序的设计思想。程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；函数之间的调用关系图。详细的算法描述（程序执行流程图）。给出软件的测试方法和测试结果。实验总结（设计的特点、不足、收获与体会）。六、源代码1、操作类packageRPNAnalysis;publicclassRPN_Operation{privatechar[]expChar=newchar[100];//表达式栈privateintexpPointer=0;//表达式栈指针privatechar[]ariStack=newchar[100];//运算符栈privateinttop=0;//运算符栈指针privatechar[]exitChar=newchar[100];//输出栈privateintexitPointer=0;//输出栈指针privateString[][]dataStrings=newString[1000][5];//表格数据privateStringtempString=newString();//临时字符串privateStringresult=newString();//结果字符串privateintrow=0;//表格数据行privateStringcompValue=newString();//计算值privatefinalchar[]Arithmetic={'+','-','*','/','(',')','#'};//运算符privatefinalchar[]Letter={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};//字母表privatefinalchar[]Digit={'1','2','3','4','5','6','7','8','9','0'};//数字表publicRPN_Operation(){江苏科技大学计算机学院编译原理实验报告0941901228章进兴for(inti=0;i1000;i++){for(intj=0;j5;j++){dataStrings[i][j]=newString();dataStrings[i][j]=;}}}//判断字符是否为字母publicbooleanisLetter(charword){intN=0;while(NLetter.length){if(word==Letter[N]){returntrue;}N++;}returnfalse;}//判断字符是否为数字publicbooleanisDigit(charword){intN=0;while(NDigit.length){if(word==Digit[N]){returntrue;}N++;}returnfalse;}//判断字符是否为算数运算符publicbooleanisArithmetic(charword){intN=0;while(NArithmetic.length){if(word==Arithmetic[N]){returntrue;}N++;}returnfalse;}//输出剩余字符串publicvoidprintExpChar(){tempString=newString();江苏科技大学计算机学院编译原理实验报告0941901228章进兴for(inti=expPointer;iexpChar.length;i++){tempString+=expChar[i];System.out.print(expChar[i]);result+=expChar[i];}System.out.print(\t\t);result+=\t\t;}//输出符号栈publicvoidprintAriStack(){tempString=newString();for(inti=0;itop;i++){tempString+=ariStack[i];System.out.print(ariStack[i]);result+=ariStack[i];}System.out.print(\t\t);result+=\t\t;}//输出逆波兰式publicvoidprintExitChar(){tempString=newString();for(inti=0;iexitPointer;i++){tempString+=exitChar[i];System.out.print(exitChar[i]);result+=exitChar[i];}System.out.print(\r\n);result+=\r\n;}//检查字符publicbooleancheckString(StringcheckString){charch;for(inti=0;icheckString.length();i++){ch=checkString.charAt(i);if(isLetter(ch)){continue;}elseif(isDigit(ch)){continue;}elseif(isArithmetic(ch)){continue;}else{returnfalse;}江苏科技大学计算机学院编译原理实验报告0941901228章进兴}returntrue;}//逆波兰分析publicvoidRPNAnalysis(Stringexpression){expChar=expression.toCharArray();charch=expChar[expPointer++];inttemp=0;if(checkString(expression)){System.out.print(步骤\t当前符号\t输入区\t\t运算符号栈\t\t输出区\r\n);result+=步骤\t当前符号\t输入区\t\t运算符号栈\t\t输出区\r\n;while(ch!='#'){if(isArithmetic(ch)){switch(ch){case'(':ariStack[top++]=ch;System.out.print(row+\t+ch+\t);result+=row+\t+ch+\t;dataStrings[row][0]=row+;dataStrings[row][1]=String.valueOf(ch);printExpChar();dataStrings[row][2]=tempString;printAriStack();dataStrings[row][3]=tempString;printExitChar();dataStrings[row][4]=tempString;row++;break;case')':while(ariStack[--top]!='('){exitChar[exitPointer++]=ariStack[top];System.out.print(row+\t+ch+\t);result+=row+\t+ch+\t;dataStrings[row][0]=row+;dataStrings[row][1]=String.valueOf(ch);printExpChar();dataStrings[row][2]=tempString;printAriStack();dataStrings[row][3]=tempString;printExitChar();江苏科技大学计算机学院编译原理实验报告0941901228章进兴dataStrings[row][4]=tempString;row++;}System.out.print(row+\t+ch+\t);dataStrings[row][0]=row+;result+=row+\t+ch+\t;dataStri