用兩種方法實(shí)現(xiàn)表達(dá)式求值

一、 設(shè)計(jì)思想一．中綴式計(jì)算結(jié)果的設(shè)計(jì)思想：此種算法最主要是用了兩個(gè)棧：用兩個(gè)棧來(lái)實(shí)現(xiàn)算符優(yōu)先，一個(gè)棧用來(lái)保存需要計(jì)算的數(shù)據(jù)numStack（操作數(shù)棧），一個(gè)用來(lái)保存計(jì)算優(yōu)先符priStack（操作符棧）。從字符串中獲取元素，如果是操作數(shù)，則直接進(jìn)操作數(shù)棧，但如果獲取的是操作符，則要分情況討論，如下：（這里討論優(yōu)先級(jí)時(shí)暫不包括“（”和“）”的優(yōu)先級(jí)）如果獲取的操作符a的優(yōu)先級(jí)高于操作符棧棧頂元素b的優(yōu)先級(jí)，則a直接入操作符棧;如果獲取的操作符a的優(yōu)先級(jí)低于操作符棧棧頂元素b的優(yōu)先級(jí)，則b出棧，a進(jìn)棧，并且取出操作數(shù)棧的棧頂元素m,再取出操作數(shù)棧新的棧頂元素n,如果b為+，則用n+m，若為減號(hào)，則n-m,依此類(lèi)推，并將所得結(jié)果入操作數(shù)棧；如果獲取的是“（”，則直接進(jìn)操作符棧；如果獲取的是“）”，則操作符棧的棧頂元素出棧,做類(lèi)似于情況2的計(jì)算，之后把計(jì)算結(jié)果入操作數(shù)棧，再取操作符棧頂元素，如果不是“（”，則出棧，重復(fù)操作，直到操作符棧頂元素為“（”，然后“（”出棧；當(dāng)表達(dá)式中的所有元素都入棧后，看操作符棧中是否還有元素，如果有，則做類(lèi)似于情況2的計(jì)算，并將結(jié)果存入操作數(shù)棧，則操作數(shù)棧中最終的棧頂元素就是所要求的結(jié)果。二．中綴轉(zhuǎn)后綴及對(duì)后綴表達(dá)式計(jì)算的設(shè)計(jì)思想：中綴轉(zhuǎn)后綴時(shí)主要用了一個(gè)操作符棧和一個(gè)用來(lái)存放后綴表達(dá)式的棧，從表達(dá)式中依次獲取元素，如果獲取的是操作數(shù)，則直接存入S3棧中，如果獲取的是操作符也需分情況討論，如下：（這里討論優(yōu)先級(jí)時(shí)暫不包括“（”和“）”的優(yōu)先級(jí)）如果獲取的操作符a的優(yōu)先級(jí)高于操作符棧棧頂元素b的優(yōu)先級(jí)，則a直接入操作符棧;如果獲取的操作符a的優(yōu)先級(jí)低于操作符棧棧頂元素b的優(yōu)先級(jí)，則b出棧,a進(jìn)棧，并且將b存入到操作符棧中；如果獲取的是“（”，則直接進(jìn)操作符棧；如果獲取的是“）”，則操作符棧的棧頂元素出棧,并依次存入到操作符棧中，直到操作符棧棧頂元素為“（”，然后將“（”出棧；當(dāng)表達(dá)式中的所有元素都入棧或存入到操作符棧之后，看操作符棧中是否還有元素，如果有，則依次出棧，并且依次存入到操作符棧中，最后打印操作符棧中的字符串，則此字符串即為要求的后綴表達(dá)式。對(duì)后綴表達(dá)式的計(jì)算方法：主要用到了一個(gè)操作數(shù)棧，從操作符棧中依次取出元素，如果是操作數(shù)，則進(jìn)棧，如果是操作符，則從操作數(shù)棧中依次取出兩個(gè)棧頂元素al和a2,如果操作符是“/”，則計(jì)算a2/a1,將計(jì)算結(jié)果再次進(jìn)棧，依此類(lèi)推，最終棧頂元素即為計(jì)算的最終結(jié)果。在這兩種算法中，應(yīng)該特別注意一點(diǎn)：人的習(xí)慣，用戶(hù)在輸入表達(dá)式時(shí)，容易這樣輸入，如：3*4（3+2），這樣是不可取的，應(yīng)必須要用戶(hù)輸入3*4*（3+2），這是在設(shè)計(jì)思想上錯(cuò)誤提示的很重要一點(diǎn)，否則計(jì)算不全面！二、 算法流程圖第一個(gè)圖是直接計(jì)算的流程圖，圖中反應(yīng)除了這種方法的大致設(shè)計(jì)思路，但是有些細(xì)節(jié)沒(méi)有反映出來(lái)，比如說(shuō)，怎樣把字符型數(shù)據(jù)轉(zhuǎn)換為浮點(diǎn)型數(shù)據(jù)，就沒(méi)有反映出來(lái)。特別說(shuō)明

的是棱形左邊代表Y,右邊代表N,具體流程圖如下:第二個(gè)圖是對(duì)后綴表達(dá)式的求值的算法流程圖，同樣，棱形左邊代表Y,右邊代表N,怎樣把字符型數(shù)據(jù)轉(zhuǎn)換為浮點(diǎn)型數(shù)據(jù)，也同樣沒(méi)有反映出來(lái)。具體圖如下：圖2后綴表達(dá)式計(jì)算的流程圖三、源代碼程序全部由java語(yǔ)言編寫(xiě)，用面向?qū)ο蟮乃悸方鉀Q，通過(guò)eclipe測(cè)試。（一）用中綴式實(shí)現(xiàn)四則運(yùn)算利用棧，進(jìn)行四則運(yùn)算的類(lèi)用兩個(gè)棧來(lái)實(shí)現(xiàn)算符優(yōu)先，一個(gè)棧用來(lái)保存需要計(jì)算的數(shù)據(jù)numStack,—個(gè)用來(lái)保存計(jì)算優(yōu)先符priStack?；舅惴▽?shí)現(xiàn)思路為:用當(dāng)前取得的運(yùn)算符與priStack棧頂運(yùn)算符比較優(yōu)先級(jí):若高于,則因?yàn)闀?huì)先運(yùn)算，放入棧頂；若等于，因?yàn)槌霈F(xiàn)在后面，所以會(huì)后計(jì)算，所以棧頂元素出棧，取出操作數(shù)運(yùn)算；若小于，則同理，取出棧頂元素運(yùn)算，將結(jié)果入操作數(shù)棧。各個(gè)優(yōu)先級(jí)'（'>'*'='/'>+'>')'+'.xiaoliu.zhongzhuishi;importjava.util.Stack;//這個(gè)算法的表達(dá)式要以#結(jié)束如：21+5*1#publicclassOperate{privateStack<Character>priStack=newStack<Character>();//操作符棧privateStack<Integer>numStack=newStack<Integer>();;//操作數(shù)棧/**傳入需要解析的字符串，返回計(jì)算結(jié)果(此處因?yàn)闀r(shí)間問(wèn)題，省略合法性驗(yàn)證)@paramstr需要進(jìn)行技術(shù)的表達(dá)式@return計(jì)算結(jié)果*/publicintcaculate(Stringstr){//1.判斷string當(dāng)中有沒(méi)有非法字符Stringtemp;//用來(lái)臨時(shí)存放讀取的字符//2.循環(huán)開(kāi)始解析字符串，當(dāng)字符串解析完，且符號(hào)棧為空時(shí)，則計(jì)算完成StringBuffertempNum=newStringBuffer();//用來(lái)臨時(shí)存放數(shù)字字符串(當(dāng)為多位數(shù)時(shí))StringBufferstring=newStringBuffer().append(str);//用來(lái)保存，提高效率while(string.length()!=0){temp=string.substring(0,1);string.delete(0,1);//判斷temp，當(dāng)temp為操作符時(shí)if(!isNum(temp)){//I.此時(shí)的tempNum內(nèi)即為需要操作的數(shù)，取出數(shù)，壓棧，并且清空tempNumif(!"".equals(tempNum.toString())){//當(dāng)表達(dá)式的第一個(gè)符號(hào)為括號(hào)intnum=Integer.parseInt(tempNum.toString());numStack.push(num);tempNum.delete(0,tempNum.length());}//用當(dāng)前取得的運(yùn)算符與棧頂運(yùn)算符比較優(yōu)先級(jí)：若高于，則因?yàn)闀?huì)先運(yùn)算，放入棧頂；若等于，因?yàn)槌霈F(xiàn)在后面，所以會(huì)后計(jì)算，所以棧頂元素出棧，取出操作數(shù)運(yùn)算；//若小于，則同理，取出棧頂元素運(yùn)算，將結(jié)果入操作數(shù)棧。//判斷當(dāng)前運(yùn)算符與棧頂元素優(yōu)先級(jí)，取出元素，進(jìn)行計(jì)算(因?yàn)閮?yōu)先級(jí)可能小于棧頂元素，還小于第二個(gè)元素等等，需要用循環(huán)判斷)while(!compare(temp.charAt(0))&&(!priStack.empty())){inta=(int)numStack.pop();//第二個(gè)運(yùn)算數(shù)intb=(int)numStack.pop();//第一個(gè)運(yùn)算數(shù)charope=priStack.pop();

intresult=0;//運(yùn)算結(jié)果switch(ope){//如果是加號(hào)或者減號(hào)，則case'+':result=b+a;//將操作結(jié)果放入操作數(shù)棧numStack.push(result);break;case'-':result=b-a;//將操作結(jié)果放入操作數(shù)棧numStack.push(result);break;case'*':result=b*a;//將操作結(jié)果放入操作數(shù)棧numStack.push(result);break;case'/':result=b/a;//將操作結(jié)果放入操作數(shù)棧numStack.push(result);break;}}//判斷當(dāng)前運(yùn)算符與棧頂元素優(yōu)先級(jí)，如果高，或者低于平，計(jì)算完后，將當(dāng)前操去掉括號(hào)priStack.push(newCharacter(temp.charAt(0)));if(temp.charAt(0)==')'){//當(dāng)棧頂為'('，而當(dāng)前元素為')'時(shí)，則是括號(hào)內(nèi)以算完，priStack.pop();priStack.pop();}作符號(hào)，放入操作符棧}}elseif(temp.charAt(0)!='#'){//if(temp.charAt(0)!='#'){tempNum=tempNum.append(temp);//將讀到的這一位數(shù)接到以讀出的數(shù)后(當(dāng)不是個(gè)位數(shù)的時(shí)候)}returnnumStack.pop();}/***判斷傳入的字符是不是0-9的數(shù)字**@paramstr*傳入的字符串*@return*/privatebooleanisNum(Stringtemp){returntemp.matches("[0-9]");}/***比較當(dāng)前操作符與棧頂元素操作符優(yōu)先級(jí)，如果比棧頂元素優(yōu)先級(jí)高，則返回true,否則返回false*@paramstr需要進(jìn)行比較的字符@return比較結(jié)果true代表比棧頂元素優(yōu)先級(jí)高，false代表比棧頂元素優(yōu)先級(jí)低*/privatebooleancompare(charstr){if(priStack.empty()){//當(dāng)為空時(shí)，顯然當(dāng)前優(yōu)先級(jí)最低，返回高returntrue;}charlast=(char)priStack.lastElement();//如果棧頂為'('顯然，優(yōu)先級(jí)最低，')'不可能為棧頂。if(last=='('){returntrue;}switch(str){case'#':returnfalse;//結(jié)束符case'('://'('優(yōu)先級(jí)最高,顯然返回truereturntrue;case')'://')'優(yōu)先級(jí)最低，returnfalse;case'*':{//'*/'優(yōu)先級(jí)只比'+-'高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);}}(二)用后綴式實(shí)現(xiàn)四則運(yùn)算同樣用java語(yǔ)言編寫(xiě)，通過(guò)eclipse測(cè)試。.xiaoliu.houzhuishi;importjava.util.Stack;importjava.util.Scanner;.xiaoliu.zhongzhuishi.Operate;publicclassCaulate{publicStringsuffix_expression(Stringexpression)〃中綴表達(dá)式轉(zhuǎn)換后綴表達(dá)式{Stack<Object>s3=newStack<Object>();//存放后綴表達(dá)式的結(jié)果棧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))〃如果是運(yùn)算符，將前面的數(shù)數(shù)字入s3棧，操作符入s4棧{if(i==len-1&&(!isOprator(c1)))〃當(dāng)最后一位且不是操作符時(shí)，將前面的數(shù)壓棧m=i+l;elsem=i;//操作數(shù)入棧,向前遍歷到下一個(gè)運(yùn)算符，將中間的字符串轉(zhuǎn)化為doublefor(intj=i-1;j>=0;j--){if(isOprator(expression.charAt(j))){n=j;break;}n=j-1;}if(m!=n+1)〃只有當(dāng)這兩個(gè)值不等時(shí)中間才會(huì)有操作數(shù){number=Double.parseDouble(expression.substring(n+1,m));s3.push(number);}//運(yùn)算符入棧if(i==0&&(c1!='('))〃當(dāng)表達(dá)式第一個(gè)字符就為運(yùn)算符且不是左括號(hào)時(shí)，返回表達(dá)式錯(cuò)誤{return"表達(dá)式錯(cuò)誤！";}elseif(isOprator(c1))〃且是操作符時(shí){while(true){if(s4.isEmpty()lls4.peek()=='('llc1=='(')〃如果棧為空或者棧頂元素為(或者c1為(時(shí)，則直接將運(yùn)算符壓入棧內(nèi){s4.push(c1);break;}elseif(c1==')')〃當(dāng)c1為)時(shí)，依次彈出s4中的運(yùn)算符并壓入s3，直到(，舍棄這一對(duì)括號(hào){while(s4.peek()!='('){s3.push(s4.pop());if(s4.isEmpty())〃彈出所有不為左括號(hào)之后堆棧為空，則表達(dá)式不合法{return"缺少左括號(hào)";}}s4.pop();〃彈出(break;}else{if(priorityCompare(cl,s4.peek())==l)〃判斷優(yōu)先級(jí)，優(yōu)先級(jí)高入棧，優(yōu)先級(jí)低將棧頂運(yùn)算符壓入s3{s4.push(cl);break;}else{s3.push(s4.pop());}}}}}elsecontinue;}while(!s4.isEmpty())〃表達(dá)式結(jié)束后，依次將s4剩下的運(yùn)算符壓入s3{if((char)s4.peek()=='(')return"缺少右括號(hào)";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;}//判斷字符是否為運(yùn)算符，是為真，不是為假 ,此方法在前面已經(jīng)調(diào)用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>();〃后綴表達(dá)式棧Stack<Double>s2=newStack<Double>();〃操作數(shù)棧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());//返回最后的結(jié)果}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;}//用于進(jìn)行測(cè)試的方法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);}}四、運(yùn)行結(jié)果圖中為計(jì)算(21+5)-5*12的截圖，結(jié)果為—34圖中為計(jì)算7+8*3-3*(6-3)的截圖，結(jié)果為22。五、遇到的問(wèn)題及解決這部分我主要遇到了如下兩個(gè)問(wèn)題，其內(nèi)容與解決方法如下所列：在編寫(xiě)中綴轉(zhuǎn)后綴表達(dá)式的時(shí)候出現(xiàn)這樣的情況：如果用戶(hù)輸入4+3*2時(shí)，運(yùn)行出的后綴表達(dá)式正確，即413|2|*|+|,但是在輸入3*2+4時(shí)，運(yùn)行出的后綴表達(dá)式始終為3|2|*|+|，顯然是不對(duì)的，正確的應(yīng)為3|2|*|4|+|解決方法：根據(jù)運(yùn)行結(jié)果，分析得，當(dāng)從expression表達(dá)式中獲得的操作符的優(yōu)先級(jí)低于操作棧棧頂元素時(shí)會(huì)出錯(cuò)，而從3|2|*|4|+1與3|2|*|+|的比較，說(shuō)明漏掉了