用两种方法实现表达式求值

一、 设计思想一．中缀式计算结果的设计思想：此种算法最主要是用了两个栈：用两个栈来实现算符优先，一个栈用来保存需要计算的数据numStack（操作数栈），一个用来保存计算优先符priStack（操作符栈）。从字符串中获取元素，如果是操作数，则直接进操作数栈，但如果获取的是操作符，则要分情况讨论，如下：（这里讨论优先级时暂不包括“（”和“）”的优先级）如果获取的操作符a的优先级高于操作符栈栈顶元素b的优先级，则a直接入操作符栈;如果获取的操作符a的优先级低于操作符栈栈顶元素b的优先级，则b出栈，a进栈，并且取出操作数栈的栈顶元素m,再取出操作数栈新的栈顶元素n,如果b为+，则用n+m，若为减号，则n-m,依此类推，并将所得结果入操作数栈；如果获取的是“（”，则直接进操作符栈；如果获取的是“）”，则操作符栈的栈顶元素出栈,做类似于情况2的计算，之后把计算结果入操作数栈，再取操作符栈顶元素，如果不是“（”，则出栈，重复操作，直到操作符栈顶元素为“（”，然后“（”出栈；当表达式中的所有元素都入栈后，看操作符栈中是否还有元素，如果有，则做类似于情况2的计算，并将结果存入操作数栈，则操作数栈中最终的栈顶元素就是所要求的结果。二．中缀转后缀及对后缀表达式计算的设计思想：中缀转后缀时主要用了一个操作符栈和一个用来存放后缀表达式的栈，从表达式中依次获取元素，如果获取的是操作数，则直接存入S3栈中，如果获取的是操作符也需分情况讨论，如下：（这里讨论优先级时暂不包括“（”和“）”的优先级）如果获取的操作符a的优先级高于操作符栈栈顶元素b的优先级，则a直接入操作符栈;如果获取的操作符a的优先级低于操作符栈栈顶元素b的优先级，则b出栈,a进栈，并且将b存入到操作符栈中；如果获取的是“（”，则直接进操作符栈；如果获取的是“）”，则操作符栈的栈顶元素出栈,并依次存入到操作符栈中，直到操作符栈栈顶元素为“（”，然后将“（”出栈；当表达式中的所有元素都入栈或存入到操作符栈之后，看操作符栈中是否还有元素，如果有，则依次出栈，并且依次存入到操作符栈中，最后打印操作符栈中的字符串，则此字符串即为要求的后缀表达式。对后缀表达式的计算方法：主要用到了一个操作数栈，从操作符栈中依次取出元素，如果是操作数，则进栈，如果是操作符，则从操作数栈中依次取出两个栈顶元素al和a2,如果操作符是“/”，则计算a2/a1,将计算结果再次进栈，依此类推，最终栈顶元素即为计算的最终结果。在这两种算法中，应该特别注意一点：人的习惯，用户在输入表达式时，容易这样输入，如：3*4（3+2），这样是不可取的，应必须要用户输入3*4*（3+2），这是在设计思想上错误提示的很重要一点，否则计算不全面！二、 算法流程图第一个图是直接计算的流程图，图中反应除了这种方法的大致设计思路，但是有些细节没有反映出来，比如说，怎样把字符型数据转换为浮点型数据，就没有反映出来。特别说明

的是棱形左边代表Y,右边代表N,具体流程图如下:第二个图是对后缀表达式的求值的算法流程图，同样，棱形左边代表Y,右边代表N,怎样把字符型数据转换为浮点型数据，也同样没有反映出来。具体图如下：图2后缀表达式计算的流程图三、源代码程序全部由java语言编写，用面向对象的思路解决，通过eclipe测试。（一）用中缀式实现四则运算利用栈，进行四则运算的类用两个栈来实现算符优先，一个栈用来保存需要计算的数据numStack,—个用来保存计算优先符priStack。基本算法实现思路为:用当前取得的运算符与priStack栈顶运算符比较优先级:若高于,则因为会先运算，放入栈顶；若等于，因为出现在后面，所以会后计算，所以栈顶元素出栈，取出操作数运算；若小于，则同理，取出栈顶元素运算，将结果入操作数栈。各个优先级'（'>'*'='/'>+'>')'+'.xiaoliu.zhongzhuishi;importjava.util.Stack;//这个算法的表达式要以#结束如：21+5*1#publicclassOperate{privateStack<Character>priStack=newStack<Character>();//操作符栈privateStack<Integer>numStack=newStack<Integer>();;//操作数栈/**传入需要解析的字符串，返回计算结果(此处因为时间问题，省略合法性验证)@paramstr需要进行技术的表达式@return计算结果*/publicintcaculate(Stringstr){//1.判断string当中有没有非法字符Stringtemp;//用来临时存放读取的字符//2.循环开始解析字符串，当字符串解析完，且符号栈为空时，则计算完成StringBuffertempNum=newStringBuffer();//用来临时存放数字字符串(当为多位数时)StringBufferstring=newStringBuffer().append(str);//用来保存，提高效率while(string.length()!=0){temp=string.substring(0,1);string.delete(0,1);//判断temp，当temp为操作符时if(!isNum(temp)){//I.此时的tempNum内即为需要操作的数，取出数，压栈，并且清空tempNumif(!"".equals(tempNum.toString())){//当表达式的第一个符号为括号intnum=Integer.parseInt(tempNum.toString());numStack.push(num);tempNum.delete(0,tempNum.length());}//用当前取得的运算符与栈顶运算符比较优先级：若高于，则因为会先运算，放入栈顶；若等于，因为出现在后面，所以会后计算，所以栈顶元素出栈，取出操作数运算；//若小于，则同理，取出栈顶元素运算，将结果入操作数栈。//判断当前运算符与栈顶元素优先级，取出元素，进行计算(因为优先级可能小于栈顶元素，还小于第二个元素等等，需要用循环判断)while(!compare(temp.charAt(0))&&(!priStack.empty())){inta=(int)numStack.pop();//第二个运算数intb=(int)numStack.pop();//第一个运算数charope=priStack.pop();

intresult=0;//运算结果switch(ope){//如果是加号或者减号，则case'+':result=b+a;//将操作结果放入操作数栈numStack.push(result);break;case'-':result=b-a;//将操作结果放入操作数栈numStack.push(result);break;case'*':result=b*a;//将操作结果放入操作数栈numStack.push(result);break;case'/':result=b/a;//将操作结果放入操作数栈numStack.push(result);break;}}//判断当前运算符与栈顶元素优先级，如果高，或者低于平，计算完后，将当前操去掉括号priStack.push(newCharacter(temp.charAt(0)));if(temp.charAt(0)==')'){//当栈顶为'('，而当前元素为')'时，则是括号内以算完，priStack.pop();priStack.pop();}作符号，放入操作符栈}}elseif(temp.charAt(0)!='#'){//if(temp.charAt(0)!='#'){tempNum=tempNum.append(temp);//将读到的这一位数接到以读出的数后(当不是个位数的时候)}returnnumStack.pop();}/***判断传入的字符是不是0-9的数字**@paramstr*传入的字符串*@return*/privatebooleanisNum(Stringtemp){returntemp.matches("[0-9]");}/***比较当前操作符与栈顶元素操作符优先级，如果比栈顶元素优先级高，则返回true,否则返回false*@paramstr需要进行比较的字符@return比较结果true代表比栈顶元素优先级高，false代表比栈顶元素优先级低*/privatebooleancompare(charstr){if(priStack.empty()){//当为空时，显然当前优先级最低，返回高returntrue;}charlast=(char)priStack.lastElement();//如果栈顶为'('显然，优先级最低，')'不可能为栈顶。if(last=='('){returntrue;}switch(str){case'#':returnfalse;//结束符case'('://'('优先级最高,显然返回truereturntrue;case')'://')'优先级最低，returnfalse;case'*':{//'*/'优先级只比'+-'高if(last=='+'||last=='-')returntrue;elsereturnfalse;}case'/':{if(last=='+'||last=='-')returntrue;elsereturnfalse;}//'+-'为最低，一直返回falsecase'+':returnfalse;case'-':returnfalse;}returntrue;}publicstaticvoidmain(Stringargs[]){Operateoperate=newOperate();System.out.println("theansweris:");intt=operate.caculate("21+5*l#");System.out.println(t);}}(二)用后缀式实现四则运算同样用java语言编写，通过eclipse测试。.xiaoliu.houzhuishi;importjava.util.Stack;importjava.util.Scanner;.xiaoliu.zhongzhuishi.Operate;publicclassCaulate{publicStringsuffix_expression(Stringexpression)〃中缀表达式转换后缀表达式{Stack<Object>s3=newStack<Object>();//存放后缀表达式的结果栈Stack<Character>s4=newStack<Character>();〃存放操作符栈intlen=expression.length();charc1;doublenumber;intm,n=-1;for(inti=0;i<len;i++){c1=expression.charAt(i);if(isOprator(cl)ll(i==len-l))〃如果是运算符，将前面的数数字入s3栈，操作符入s4栈{if(i==len-1&&(!isOprator(c1)))〃当最后一位且不是操作符时，将前面的数压栈m=i+l;elsem=i;//操作数入栈,向前遍历到下一个运算符，将中间的字符串转化为doublefor(intj=i-1;j>=0;j--){if(isOprator(expression.charAt(j))){n=j;break;}n=j-1;}if(m!=n+1)〃只有当这两个值不等时中间才会有操作数{number=Double.parseDouble(expression.substring(n+1,m));s3.push(number);}//运算符入栈if(i==0&&(c1!='('))〃当表达式第一个字符就为运算符且不是左括号时，返回表达式错误{return"表达式错误！";}elseif(isOprator(c1))〃且是操作符时{while(true){if(s4.isEmpty()lls4.peek()=='('llc1=='(')〃如果栈为空或者栈顶元素为(或者c1为(时，则直接将运算符压入栈内{s4.push(c1);break;}elseif(c1==')')〃当c1为)时，依次弹出s4中的运算符并压入s3，直到(，舍弃这一对括号{while(s4.peek()!='('){s3.push(s4.pop());if(s4.isEmpty())〃弹出所有不为左括号之后堆栈为空，则表达式不合法{return"缺少左括号";}}s4.pop();〃弹出(break;}else{if(priorityCompare(cl,s4.peek())==l)〃判断优先级，优先级高入栈，优先级低将栈顶运算符压入s3{s4.push(cl);break;}else{s3.push(s4.pop());}}}}}elsecontinue;}while(!s4.isEmpty())〃表达式结束后，依次将s4剩下的运算符压入s3{if((char)s4.peek()=='(')return"缺少右括号";s3.push(s4.pop());}returncount_result(s3);}privateintpriorityCompare(charcl,charc2){switch(cl){case'+':case'-':return(c2=='*'||c2=='/'?-l:0);case'*':case'/':return(c2=='+'||c2=='-'?1:0);}return1;}//判断字符是否为运算符，是为真，不是为假 ,此方法在前面已经调用privatebooleanisOprator(Objectc){try{charc1=((Character)c).charValue();if(c1=='+'||c1=='-'||c1=='*'||c1=='/'||c1=='('||c1==')')returntrue;}catch(Exceptione){returnfalse;}returnfalse;}privateStringcount_result(Stack<Object>ob){Stack<Object>sl=newStack<Object>();〃后缀表达式栈Stack<Double>s2=newStack<Double>();〃操作数栈while(!ob.isEmpty())〃将传入的栈逆序压入{sl.push(ob.pop());}while(!sl.isEmpty()){if(!isOprator(s1.peek()))〃遇到非操作符，压入s2栈{s2.push((Double)s1.pop());}else{s2.push(cout(s2.pop(),s2.pop(),(Character)s1.pop()));}}returnDouble.toString(s2.peek());//返回最后的结果}privateDoublecout(doubles1,doubles2,chars3){doubleresult=0;switch(s3){case'+':result=s1+s2;break;case'-':result=s2-s1;break;case'*':result=s1*s2;break;case'/':result=s2/s1;break;}returnresult;}//用于进行测试的方法publicstaticvoidmain(Stringargs[]){Caulatecaulate=newCaulate();System.out.println("pleaseinputexpression:");Stringexp=newScanner(System.in).nextLine();System.out.println("theansweris:");Stringt=caulate.suffix_expression(exp);System.out.println(t);}}四、运行结果图中为计算(21+5)-5*12的截图，结果为—34图中为计算7+8*3-3*(6-3)的截图，结果为22。五、遇到的问题及解决这部分我主要遇到了如下两个问题，其内容与解决方法如下所列：在编写中缀转后缀表达式的时候出现这样的情况：如果用户输入4+3*2时，运行出的后缀表达式正确，即413|2|*|+|,但是在输入3*2+4时，运行出的后缀表达式始终为3|2|*|+|，显然是不对的，正确的应为3|2|*|4|+|解决方法：根据运行结果，分析得，当从expression表达式中获得的操作符的优先级低于操作栈栈顶元素时会出错，而从3|2|*|4|+1与3|2|*|+|的比较，说明漏掉了