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

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

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

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