前綴、中綴、后綴表達(dá)式

對于未經(jīng)訓(xùn)練的用戶來說，計(jì)算機(jī)科學(xué)領(lǐng)域中數(shù)學(xué)表達(dá)式求值的傳統(tǒng)方法即不順手又難以使用；軟件工程師Nikola.Stepan旨在改變這些傳統(tǒng)方法。他的appletW3Eval對表達(dá)式求值與您用紙筆計(jì)算的一系列步驟完全一致，但更快并且沒有錯誤。請往下讀，了解這一挑戰(zhàn)一人類易讀的數(shù)學(xué)到Java代碼的轉(zhuǎn)換。還記得在您的第一臺科學(xué)計(jì)算器上用逆波蘭表示法奮斗的經(jīng)歷嗎？W3Evalapplet無法讓您可信賴的HP-41更易用，正如它的名稱所暗示—一個(gè)只能運(yùn)行于Web的表達(dá)式求值程序。但它的確提供了一種方法一人類更易于遵循的對表達(dá)式一步一步的求值。W3Eval的方法與傳統(tǒng)計(jì)算器不同，卻和人類的計(jì)算方式一致。當(dāng)您用傳統(tǒng)的計(jì)算器計(jì)算時(shí)，每輸入一個(gè)新數(shù)，前一個(gè)數(shù)就看不到了。如果在輸入一個(gè)長表達(dá)式中出了錯，就得全部重來。有了W3Eval，您就能看到參與計(jì)算的所有東西，還能輕松的編輯表達(dá)式。它獨(dú)特的能力（一步一步的對表達(dá)式求值）非常容易實(shí)現(xiàn)，因?yàn)橛脩裟芸吹角笾档拿恳徊?，包括臨時(shí)結(jié)果。本文將讓您從頭至尾認(rèn)識W3Eval功能性的要點(diǎn)；您將看到一些用于表達(dá)式求值的代碼。不過，我們還是先看看表達(dá)式求值的經(jīng)典算法，這樣您就會明白W3Eval方法的差異究竟有多少。表達(dá)式求值的經(jīng)典算法編寫代碼對算術(shù)表達(dá)式求值的經(jīng)典方法由DonaldKnuth描述于1962年（請參閱參考資料）。Knuth將此概括為三個(gè)步驟：對中綴表達(dá)式進(jìn)行語法分析中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換對后綴表達(dá)式求值注意到我們談到的這個(gè)經(jīng)典算法有些簡化：算術(shù)表達(dá)式只包含操作數(shù)、二元操作符和一種括號。此外，對于每個(gè)操作數(shù)和操作符，只用單個(gè)字符表示，使語法分析直觀。表達(dá)式表示法算術(shù)表達(dá)式中最常見的表示法形式有中綴、前綴和后綴表示法。中綴表示法是書寫表達(dá)式的常見方式，而前綴和后綴表示法主要用于計(jì)算機(jī)科學(xué)領(lǐng)域。中綴表示法中綴表示法是算術(shù)表達(dá)式的常規(guī)表示法。稱它為中綴表示法是因?yàn)槊總€(gè)操作符都位于其操作數(shù)的中間，這種表示法只適用于操作符恰好對應(yīng)兩個(gè)操作數(shù)的時(shí)候（在操作符是二元操作符如加、減、乘、除以及取模的情況下）。對以中綴表示法書寫的表達(dá)式進(jìn)行語法分析時(shí)，需要用括號和優(yōu)先規(guī)則排除多義性。Syntax:operandloperatoroperand2Example:(A+B)前綴和后綴表示法有三項(xiàng)公共特征：操作數(shù)的順序與等價(jià)的中綴表達(dá)式中操作數(shù)的順序一致不需要括號前綴和后綴表示法有三項(xiàng)公共特征：操作數(shù)的順序與等價(jià)的中綴表達(dá)式中操作數(shù)的順序一致不需要括號操作符的優(yōu)先級不相關(guān)中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換要把表達(dá)式從中綴表達(dá)式的形式轉(zhuǎn)換成用后綴表示法表示的等價(jià)表達(dá)式，必須了解操作符的優(yōu)先級和結(jié)合性。優(yōu)先級或者說操作符的強(qiáng)度決定求值順序；優(yōu)先級高的操作符比優(yōu)先級低的操作符先求值。如果所有操作符優(yōu)先級一樣，那么求值順序就取決于它們的結(jié)合性。操作符的結(jié)合性定義了相同優(yōu)先級操作符組合的順序（從右至左或從左至右）。Leftassociativity:A+B+C=（A+B）+C前綴表示法前綴表示法中，操作符寫在操作數(shù)的前面。這種表示法經(jīng)常用于計(jì)算機(jī)科學(xué)，特別是編譯器設(shè)計(jì)方面。為紀(jì)念其發(fā)明家一JanLukasiewicz（請參閱參考資料），這種表示法也稱波Syntax:operatoroperand1operand2Example:-*+ABC/D+EF后綴表示法在后綴表示法中，操作符位于操作數(shù)后面。后綴表示法也稱逆波蘭表示法（reversePolishnotation，RPN），因其使表達(dá)式求值變得輕松，所以被普遍使用。Syntax:operand1operand2operatorExample:AB+C*DEF+/-Rightassociativity:AEC=A"(B"C)轉(zhuǎn)換過程包括用下面的算法讀入中綴表達(dá)式的操作數(shù)、操作符和括號：初始化一個(gè)空堆棧，將結(jié)果字符串變量置空。從左到右讀入中綴表達(dá)式，每次一個(gè)字符。如果字符是操作數(shù)，將它添加到結(jié)果字符串。如果字符是個(gè)操作符，彈出(pop)操作符，直至遇見開括號(openingparenthesis)、優(yōu)先級較低的操作符或者同一優(yōu)先級的右結(jié)合符號。把這個(gè)操作符壓入(push)堆棧。如果字符是個(gè)開括號，把它壓入堆棧。如果字符是個(gè)閉括號(closingparenthesis)，在遇見開括號前，彈出所有操作符，然后把它們添加到結(jié)果字符串。如果到達(dá)輸入字符串的末尾，彈出所有操作符并添加到結(jié)果字符串。后綴表達(dá)式求值對后綴表達(dá)式求值比直接對中綴表達(dá)式求值簡單。在后綴表達(dá)式中，不需要括號，而且操作符的優(yōu)先級也不再起作用了。您可以用如下算法對后綴表達(dá)式求值：初始化一個(gè)空堆棧從左到右讀入后綴表達(dá)式如果字符是一個(gè)操作數(shù)，把它壓入堆棧。如果字符是個(gè)操作符，彈出兩個(gè)操作數(shù)，執(zhí)行恰當(dāng)操作，然后把結(jié)果壓入堆棧。如果您不能夠彈出兩個(gè)操作數(shù)，后綴表達(dá)式的語法就不正確。到后綴表達(dá)式末尾，從堆棧中彈出結(jié)果。若后綴表達(dá)式格式正確，那么堆棧應(yīng)該為空。W3Eval：一種新的方法W3Eval的方法與上面概括的經(jīng)典算法不同。不是把中綴表達(dá)式轉(zhuǎn)換為后綴表示法；恰恰相反，它對中綴表達(dá)式直接求值。這種方法比傳統(tǒng)方法稍微復(fù)雜了些，但它支持一步一步的求值，在執(zhí)行時(shí)您能看到每一步。求值過程類似于手工計(jì)算：如果表達(dá)式中包含括號，先求嵌套最深的括號對中的子表達(dá)式的值。所有括號內(nèi)的子表達(dá)式都求值完畢后，表達(dá)式的其它部分再求值。求值過程分為三個(gè)步驟：表達(dá)式語法分析表達(dá)式檢查

3.步一步的求值3.步一步的求值表達(dá)式語法分析W3Eval的數(shù)學(xué)表達(dá)式由數(shù)字、變量、操作符、函數(shù)和括號組成。除了缺省的十進(jìn)制計(jì)數(shù)制外W3Eval還支持二進(jìn)制、八進(jìn)制和十六進(jìn)制。這些以其它計(jì)數(shù)制計(jì)數(shù)的數(shù)必須以#開頭，并緊跟b、o或者h(yuǎn)來分別表示二進(jìn)制、八進(jìn)制或十六進(jìn)制。W3Eval的變量是不限長度的大寫字母和數(shù)字序列，其首字符必須是字母。W3Eval有一些預(yù)定義的變量，不過它也支持用戶定義的變量。W3Eval支持帶有固定或不定數(shù)量自變量的函數(shù)。函數(shù)可分為以下幾組：三角函數(shù)（sin、cos、tan、cot、sec、csc）反三角函數(shù)（asin、acos、atan、atan2、acot、asec、acsc）雙曲線函數(shù)（sinh、cosh、tanh、coth、sech、csch）反雙曲線函數(shù)（asinh、acosh、atanh、acoth、asech、acsch）指數(shù)函數(shù)（log、log2、log10、exp、exp2、exp10、sqrt、cur）組合學(xué)函數(shù)（Combinatoric）（comb、combr、perm、permr、var、varr）統(tǒng)計(jì)函數(shù)（sum、avg、min、max、stddev、count）其它（abs、ceil、fact、floor、pow、random、rint、round、sign、frac、hypot、deg、rad、trunc、int）W3Eval對表達(dá)式進(jìn)行語法分析也就是指它識別出表達(dá)式的算術(shù)成分，并將它們轉(zhuǎn)化成語言符號（token），然后把它們放入向量。表達(dá)式一旦處于這種狀態(tài)，就為下面兩步做好了準(zhǔn)備：表達(dá)式檢查和求值。W3Eval的符號（token）是算術(shù)表達(dá)式的組成部分;記號Sa/k）是獨(dú)立的字符，由applet使用，作為識別各種符號的內(nèi)部標(biāo)志。每種符號有唯一的mark與之對應(yīng)。W3Eval的表達(dá)式由表1所示的符號組成。表1.W3Eval的符號TokenMark類十進(jìn)制數(shù)Double二進(jìn)制數(shù)String十六進(jìn)制數(shù)String八進(jìn)制數(shù)String變量Variable函數(shù)Function操作符Operator開括號String閉括號String逗號String用以表示函數(shù)、操作符和變量類的定義如清單1所示：清單1.Function、Operator和Variable類的定義publicclassFunction(publicStringfunction;publicintnumber_of_arguments;publicFunction(Stringfunction,intnumber_of_arguments)(this.function=function;this.number_of_arguments=number_of_arguments;}publicStringtoString()(returnfunction;}}publicclassOperator(publicStringoperator;publicbytepriority;publicOperator(Stringoperator,bytepriority)(this.operator=operator;this.priority=priority;}publicStringtoString()(returnoperator;}}publicclassVariable(publicStringvariable;publicdoublevalue;publicVariable(Stringvariable,doublevalue)(this.variable=variable;this.value=value;}publicStringtoString()(returnvariable;}}Token類如清單2所示。清單2.Token類publicclassToken(publicObjecttoken;publiccharmark;publicintposition;publicintlength;publicToken(Objecttoken,charmark,intposition,intlength)(this.token=token;this.mark=mark;this.position=position;this.length=length;}publicStringtoString()(returntoken.toString()+〃;〃+mark+〃;〃+position+〃;〃+length+〃?;}}表達(dá)式檢查檢查正規(guī)表達(dá)式正確性的所有代碼都在一個(gè)獨(dú)立的類中。詳細(xì)的表達(dá)式檢查能夠確定錯誤確切的類型和位置。錯誤檢查有七類：括號檢查。W3Eval的表達(dá)式可以包含三種括號：標(biāo)準(zhǔn)圓括號、方括號和花括號。如果表達(dá)式包含相同數(shù)量的開括號和閉括號，并且每個(gè)開括號與一個(gè)相應(yīng)的同種閉括號相匹配，則表達(dá)式的括號語法正確。三種括號在語義上等價(jià)，如下面的代碼段所示。清單3.三種括號importjava.util.Stack;publicclassParentheses_check(publicstaticbooleanis_open_parenthesis(charc)(if(c=='('&line;&line;c=='['&line;&line;c=='{')returntrue;elsereturnfalse;}publicstaticbooleanis_closed_parenthesis(charc)(if(c==')'&line;&line;c==']'&line;&line;c=='}')returntrue;elsereturnfalse;}privatestaticbooleanparentheses_match(charopen,charclosed)(if(open=='('&&closed==')')returntrue;elseif(open=='['&&closed==']')returntrue;elseif(open=='{'&&closed=='}')returntrue;elsereturnfalse;}publicstaticbooleanparentheses_valid(Stringexp)(Stacks=newStack();int i;char current_char;Characterc;char c1;booleanret=true;for(i=0;i(current_char=exp.charAt(i);if(is_open_parenthesis(current_char)){—— —c=newCharacter(current_char);s.push(c);}elseif(is_closed_parenthesis(current_char))(if(s.isEmpty())(ret=false;break;}else(c=(Character)s.pop();c1=c.charValue();if(!parentheses_match(cl,current_char))(ret=false;break;}token檢查。檢查表達(dá)式語法。確保表達(dá)式所有部分都被認(rèn)為是合法的。表達(dá)式開頭的檢查（請參閱清單4）。確保表達(dá)式從合法的符號開始。不可以用操作符、逗號或閉括號作為表達(dá)式的開始符。清單4.正確的表達(dá)式開頭的檢查privatestaticbooleanbegin_check(Vectortokens,Ranger,StringBuffererr)(charmark;Tokent;t=(Token)tokens.elementAt(0);mark=t.mark;if(mark=='P')err.append(Messages.begin_operator);elseif(mark==')')err.append(Messages.begin_parenthesis);elseif(mark=='Z')err.append(Messages.begin_comma);elsereturntrue;r.start=0;r.end=t.length;表達(dá)式末尾的檢查。確保表達(dá)式以合法符號結(jié)束。不可以用操作符、函數(shù)、逗號或開括號作為表達(dá)式結(jié)束符。符號序列的檢查。檢查表達(dá)式中的符號序列。在下面的表格中，若X軸上的符號和Y軸上的符號對應(yīng)的交界處用X作了記號，則相應(yīng)X軸上的符號可以接在Y軸上符號的后面。表2.合法的符號序列DBHOVf|P()_^^^_^^^^^^^^^^^^^^^^^^?^^^^^^?^^^^^^_?^^^^DBHOVFP()Z函數(shù)檢查。確保表達(dá)式中所有函數(shù)的自變量數(shù)量正確。逗號檢查。逗號只能用于分隔函數(shù)的自變量。若用于表達(dá)式其它地方，就不合法。一步一步的求值只有能順利通過以上概括的所有檢查的表達(dá)式，W3Eval才求值。從而確保內(nèi)建于W3Eval中的前提條件不會出現(xiàn)問題。后面的算法用于單步執(zhí)行表達(dá)式求值：找出嵌入最深的那對括號。在這對括號中，找出優(yōu)先級最高的操作符。若這對括號中沒有操作符：o 如果表達(dá)式再不包含任何其它的括號，求值(過程)完成。o 如果表達(dá)式包含括號，但不包含操作符，則存在一個(gè)函數(shù)。對函數(shù)求值，然后轉(zhuǎn)到步驟5。獲取操作數(shù)并執(zhí)行運(yùn)算。從向量中除去用過的符號并在同一位置放入結(jié)果。除去冗余括號。將向量中剩余的符號結(jié)合到字符串并在屏幕上顯示結(jié)果?，F(xiàn)在，我們將更為詳細(xì)的查看算法的每一步，同時(shí)查看大部分有意思的代碼片段。步驟1：為避免括號的處理，W3Eval確定哪個(gè)子表達(dá)式處于嵌套最深的那對括號中。這項(xiàng)任務(wù)需要兩步。第一步，W3Eval必須找出第一個(gè)閉括號：清單5.找出第一個(gè)閉括號publicstaticintpos_first_closed_parenthesis(Vectortokens)(Tokent;for(inti=0;i(t=(Token)tokens.elementAt(i);if(t.mark==')')returni;}return0;}第二步，找出與第一步找到的閉括號相匹配的開括號，如清單6所示步驟2：要實(shí)現(xiàn)求值的單步執(zhí)行，W3Eval在嵌套最深的那對括號中找出優(yōu)先級最高的操作符。(操作符的優(yōu)先級已硬編碼到applet中；請參閱參考資料以獲取完整的代碼清單。)清單7.找出優(yōu)先級最高的操作符publicstaticintpos_operator(Vectortokens,Ranger)(bytemax_priority=Byte.MAX_VALUE;intmax_pos=0;bytepriority;Stringoperator;Tokent;for(inti=r.start+2;i(t=(Token)tokens.elementAt(i);if(t.mark!='P')continue;priority=((Operator)t.token).priority;operator=((Operator)t.token).operator;if(priorityoperator.equals(〃**〃))&&priority==max_priority)(max_priority二priority;max_pos=i;}}returnmax_pos;}步驟3：如果表達(dá)式中不包含其它括號，求值的過程就完成。如果表達(dá)式包含括號，但不包含操作符，則存在需要求值的函數(shù)。清單8.檢查是否還有其它操作符?..intpoz_max_op=pos_operator(tokens,range);//iftherearenooperatorsif(poz_max_op==0)(if(no_more_parentheses)(returnfalse;}else(doubleresult;result=function_result(tokens,range.start-1);function_tokens_removal(tokens,range.start-1);t=newToken(newDouble(result),'D',0,0);tokens.setElementAt(t,range.start-1);parentheses_removal(tokens,range.start-1);returntrue;???步驟4：所有的操作符都是二元的，也就是說第一個(gè)操作數(shù)位于操作符之前，第二個(gè)操作符位于操作符之后。清單9.獲取操作數(shù)并執(zhí)行運(yùn)算???doubleoperandl,operand2;//firstoperandisbefore,,,t=(Token)tokens?elementAt(poz_max_op-1);operand1=operand_value(t);//???andsecondoperandisafteroperatort=(Token)tokens?elementAt(poz_max_op+1);operand2=operand_value(t);//operatort=(Token)tokens?elementAt(poz_max_op);Stringop=((Operator)t?token)?operator;doubleresult=operation_result(operandl,operand2,op);tokens?removeElementAt(poz_max_op+1);tokens?removeElementAt(poz_max_op);t=newToken(newDouble(result),'D',0,0);tokens?setElementAt(t,poz_max_op-1);parentheses_removal(tokens,poz_max_op-1);,??操作數(shù)可以是變量，還可以是十進(jìn)制、十六進(jìn)制、八進(jìn)制或二進(jìn)制數(shù)。publicstaticdoubleoperand_value(Tokent)(if(t.mark=='V')return((Variable)t.token).value;elseif(t.mark=='D')return((Double)t.token).doubleValue();elseif(t.mark=='H')returnbase_convert(((String)t.token).substring(2),16);elseif(t.mark=='O')returnbase_convert(((String)t.token).substring(2),8);elseif(t.mark=='B')returnbase_convert(((String)t.token).substring(2),2);}接下來的方法將不同計(jì)數(shù)制的數(shù)轉(zhuǎn)化為十進(jìn)制的形式。清單11.將數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)publicstaticlongbase_convert(Strings,intbase)(longr=0;inti,j;for(i=s.length()-1,j=0;i>=0;i--,j++)r=r+digit_weight(s.charAt(i))*(long)Math.pow(base,j);returnr;}publicstaticintdigit_weight(charc)(if(Character.isDigit(c))returnc-48;elseif('A' returnc-55;elseif('a' returnc-87;return-1;}一旦確定操作數(shù)和操作符后，就可以執(zhí)行運(yùn)算了，如清單12所示。步驟5:在這步中，W3Eval從向量中除去用過的符號并在同一位置放入結(jié)果。對于函數(shù)求值這類情況，除去的是函數(shù)、括號、自變量和逗號；而對于操作符求值這類情況而言，除去的則是操作數(shù)和操作符。步驟6：在求值的這一步，W3Eval從表達(dá)式中除去冗余括號。清單13.除去冗余括號privatestaticvoidparentheses_removal(Vectortokens,intpos)(if(pos>1&&&&((Token)tokens.elementAt(poz-2)).mark!='F'&&&&((Token)tokens.elementAt(poz-1)).mark=='('&&&&((Token)tokens.elementAt(poz+1)).mark==')'&line;&line;pos==1&&&&((Token)tokens.elementAt(0)).mark=='('&&&&((Token)tokens.elementAt(2)).mark==')')(tokens.removeElementAt(poz+1);tokens.removeElementAt(poz-1);}return;}步驟7：在求值的最后一步，向量中剩余的符號被結(jié)合到字符串，并在屏幕上顯示。publicstaticStringtoken_join(Vectortokens)(Stringresult=newString();Tokent;for(inti=0;i(t=(Token)tokens.elementAt(i);if(t.mark=='D')(doublen=((Double)t.token).doubleValue();result=result+formated_number(n);}elseresult=result+t.token;if(result.endsWith(〃.0〃))result=result.substring(0,result.length()-2);result=result+"";}returnresult;}結(jié)論本文分析了一個(gè)applet，它能一步一步的對算