 |
使用這個方便的 applet ，您就能一步一步的計算數學表達式了 Nikola Stepan (nikola.stepan@vz.tel.hr)
軟件工程師，ABIT Ltd.
2001 年 9 月
對于未經訓練的用戶來說，計算機科學領域中數學表達式求值的傳統方法即不順手又難以使用；軟件工程師 Nikola.Stepan 旨在改變這些傳統方法。他的 applet W3Eval 對表達式求值與您用紙筆計算的一系列步驟完全一致，但更快并且沒有錯誤。請往下讀，了解這一挑戰 — 人類易讀的數學到 Java 代碼的轉換。 還記得在您的第一臺科學計算器上用逆波蘭表示法奮斗的經歷嗎？W3Eval applet 無法讓您可信賴的 HP-41 更易用，正如它的名稱所暗示 — 一個只能運行于 Web 的表達式求值程序。但它的確提供了一種方法 — 人類更易于遵循的對表達式一步一步的求值。
W3Eval 的方法與傳統計算器不同，卻和人類的計算方式一致。當您用傳統的計算器計算時，每輸入一個新數，前一個數就看不到了。如果在輸入一個長表達式中出了錯，就得全部重來。有了 W3Eval，您就能看到參與計算的所有東西，還能輕松的編輯表達式。它獨特的能力（一步一步的對表達式求值）非常容易實現，因為用戶能看到求值的每一步，包括臨時結果。
本文將讓您從頭至尾認識 W3Eval 功能性的要點；您將看到一些用于表達式求值的代碼。不過，我們還是先看看表達式求值的經典算法，這樣您就會明白 W3Eval 方法的差異究竟有多少。
表達式求值的經典算法
編寫代碼對算術表達式求值的經典方法由 Donald Knuth 描述于 1962 年（請參閱參考資料）。Knuth 將此概括為三個步驟：
- 對中綴表達式進行語法分析
- 中綴表達式到后綴表達式的轉換
- 對后綴表達式求值
注意到我們談到的這個經典算法有些簡化：算術表達式只包含操作數、二元操作符和一種括號。此外，對于每個操作數和操作符，只用單個字符表示，使語法分析直觀。
表達式表示法
算術表達式中最常見的表示法形式有中綴、前綴和后綴表示法。中綴表示法是書寫表達式的常見方式，而前綴和后綴表示法主要用于計算機科學領域。
中綴表示法
中綴表示法是算術表達式的常規表示法。稱它為中綴表示法是因為每個操作符都位于其操作數的中間，這種表示法只適用于操作符恰好對應兩個操作數的時候（在操作符是二元操作符如加、減、乘、除以及取模的情況下）。對以中綴表示法書寫的表達式進行語法分析時，需要用括號和優先規則排除多義性。
Syntax: operand1 operator operand2Example: (A+B)*C-D/(E+F) | 前綴表示法
前綴表示法中，操作符寫在操作數的前面。這種表示法經常用于計算機科學，特別是編譯器設計方面。為紀念其發明家 — Jan Lukasiewicz（請參閱參考資料），這種表示法也稱波蘭表示法。
Syntax : operator operand1 operand2Example : -*+ABC/D+EF | 后綴表示法
在后綴表示法中，操作符位于操作數后面。后綴表示法也稱逆波蘭表示法（reverse Polish notation，RPN），因其使表達式求值變得輕松，所以被普遍使用。
Syntax : operand1 operand2 operatorExample : AB+C*DEF+/- | 前綴和后綴表示法有三項公共特征：
- 操作數的順序與等價的中綴表達式中操作數的順序一致
- 不需要括號
- 操作符的優先級不相關
中綴表達式到后綴表達式的轉換
要把表達式從中綴表達式的形式轉換成用后綴表示法表示的等價表達式，必須了解操作符的優先級和結合性。優先級或者說操作符的強度決定求值順序；優先級高的操作符比優先級低的操作符先求值。 如果所有操作符優先級一樣，那么求值順序就取決于它們的結合性。操作符的結合性定義了相同優先級操作符組合的順序（從右至左或從左至右）。
Left associativity : A+B+C = (A+B)+CRight associativity : A^B^C = A^(B^C) | 轉換過程包括用下面的算法讀入中綴表達式的操作數、操作符和括號：
- 初始化一個空堆棧，將結果字符串變量置空。
- 從左到右讀入中綴表達式，每次一個字符。
- 如果字符是操作數，將它添加到結果字符串。
- 如果字符是個操作符，彈出（pop）操作符，直至遇見開括號（opening parenthesis）、優先級較低的操作符或者同一優先級的右結合符號。把這個操作符壓入（push）堆棧。
- 如果字符是個開括號，把它壓入堆棧。
- 如果字符是個閉括號（closing parenthesis），在遇見開括號前，彈出所有操作符，然后把它們添加到結果字符串。
- 如果到達輸入字符串的末尾，彈出所有操作符并添加到結果字符串。
后綴表達式求值
對后綴表達式求值比直接對中綴表達式求值簡單。在后綴表達式中，不需要括號，而且操作符的優先級也不再起作用了。您可以用如下算法對后綴表達式求值：
- 初始化一個空堆棧
- 從左到右讀入后綴表達式
- 如果字符是一個操作數，把它壓入堆棧。
- 如果字符是個操作符，彈出兩個操作數，執行恰當操作，然后把結果壓入堆棧。如果您不能夠彈出兩個操作數，后綴表達式的語法就不正確。
- 到后綴表達式末尾，從堆棧中彈出結果。若后綴表達式格式正確，那么堆棧應該為空。
W3Eval：一種新的方法
W3Eval 的方法與上面概括的經典算法不同。不是把中綴表達式轉換為后綴表示法；恰恰相反，它對中綴表達式直接求值。這種方法比傳統方法稍微復雜了些，但它支持一步一步的求值，在執行時您能看到每一步。求值過程類似于手工計算：如果表達式中包含括號，先求嵌套最深的括號對中的子表達式的值。所有括號內的子表達式都求值完畢后，表達式的其它部分再求值。
求值過程分為三個步驟：
- 表達式語法分析
- 表達式檢查
- 一步一步的求值
表達式語法分析
W3Eval 的數學表達式由數字、變量、操作符、函數和括號組成。除了缺省的十進制計數制外 W3Eval 還支持二進制、八進制和十六進制。這些以其它計數制計數的數必須以 # 開頭，并緊跟 b、o 或者 h 來分別表示二進制、八進制或十六進制。
W3Eval 的變量是不限長度的大寫字母和數字序列，其首字符必須是字母。W3Eval 有一些預定義的變量，不過它也支持用戶定義的變量。
W3Eval 支持帶有固定或不定數量自變量的函數。 函數可分為以下幾組：
- 三角函數（sin、cos、tan、cot、sec、csc）
- 反三角函數（asin、acos、atan、atan2、acot、asec、acsc）
- 雙曲線函數（sinh、cosh、tanh、coth、sech、csch）
- 反雙曲線函數（asinh、acosh、atanh、acoth、asech、acsch）
- 指數函數（log、log2、log10、exp、exp2、exp10、sqrt、cur）
- 組合學函數（Combinatoric）（comb、combr、perm、permr、var、varr）
- 統計函數（sum、avg、min、max、stddev、count）
- 其它（abs、ceil、fact、floor、pow、random、rint、round、sign、frac、hypot、deg、rad、trunc、int）
W3Eval 對表達式進行語法分析，也就是指它識別出表達式的算術成分，并將它們轉化成語言符號（token），然后把它們放入向量。表達式一旦處于這種狀態，就為下面兩步做好了準備：表達式檢查和求值。
W3Eval 的符號（token）是算術表達式的組成部分；記號（mark） 是獨立的字符， 由 applet 使用，作為識別各種符號的內部標志。每種符號有唯一的 mark 與之對應。W3Eval 的表達式由表 1 所示的符號組成。
表 1. W3Eval 的符號
| Token |
Mark |
類 |
| 十進制數 |
|
Double |
| 二進制數 |
|
String |
| 十六進制數 |
|
String |
| 八進制數 |
|
String |
| 變量 |
|
Variable |
| 函數 |
|
Function |
| 操作符 |
|
Operator |
| 開括號 |
|
String |
| 閉括號 |
|
String |
| 逗號 |
|
String |
用以表示函數、操作符和變量類的定義如清單 1 所示：
清單 1. Function、Operator 和 Variable 類的定義
public class Function { public String function; public int number_of_arguments; public Function( String function, int number_of_arguments ) { this.function=function; this.number_of_arguments=number_of_arguments; } public String toString() { return function; } }public class Operator { public String operator; public byte priority; public Operator( String operator, byte priority ) { this.operator=operator; this.priority=priority; } public String toString() { return operator; } }public class Variable { public String variable; public double value; public Variable( String variable, double value ) { this.variable=variable; this.value=value; } public String toString() { return variable; } } | Token 類如清單 2 所示。
清單 2. Token 類
public class Token { public Object token; public char mark; public int position; public int length; public Token ( Object token, char mark, int position, int length ) { this.token=token; this.mark=mark; this.position=position; this.length=length; } public String toString() { return token.toString()+" ; "+mark+" ; "+position+" ; "+length+""; } } | 表達式檢查
檢查正規表達式正確性的所有代碼都在一個獨立的類中。詳細的表達式檢查能夠確定錯誤確切的類型和位置。 錯誤檢查有七類：
括號檢查。W3Eval 的表達式可以包含三種括號：標準圓括號、方括號和花括號。如果表達式包含相同數量的開括號和閉括號，并且每個開括號與一個相應的同種閉括號相匹配，則表達式的括號語法正確。三種括號在語義上等價，如下面的代碼段所示。
清單 3. 三種括號
import java.util.Stack;public class Parentheses_check { public static boolean is_open_parenthesis( char c ) { if ( c=='(' || c=='[' || c=='{' ) return true; else return false; } public static boolean is_closed_parenthesis( char c ) { if ( c==')' || c==']' || c=='}' ) return true; else return false; } private static boolean parentheses_match( char open, char closed ) { if ( open=='(' && closed==')' ) return true; else if ( open=='[' && closed==']' ) return true; else if ( open=='{' && closed=='}' ) return true; else return false; } public static boolean parentheses_valid( String exp ) { Stack s = new Stack(); int i; char current_char; Character c; char c1; boolean ret=true; for ( i=0; i < exp.length(); i++ ) { current_char=exp.charAt( i ); if ( is_open_parenthesis( current_char ) ) { c=new Character( current_char ); s.push( c ); } else if ( is_closed_parenthesis( current_char ) ) { if ( s.isEmpty() ) { ret=false; break; } else { c=(Character)s.pop(); c1=c.charValue(); if ( !parentheses_match( c1, current_char ) ) { ret=false; break; } } } } if ( !s.isEmpty() ) ret=false; return ret; } } | token 檢查。檢查表達式語法。確保表達式所有部分都被認為是合法的。
表達式開頭的檢查（請參閱清單 4）。確保表達式從合法的符號開始。不可以用操作符、逗號或閉括號作為表達式的開始符。
清單 4. 正確的表達式開頭的檢查
private static boolean begin_check( Vector tokens, Range r, StringBuffer err ) { char mark; Token t; t=(Token)tokens.elementAt( 0 ); mark=t.mark; if ( mark=='P' ) err.append( Messages.begin_operator ); else if ( mark==')' ) err.append( Messages.begin_parenthesis ); else if ( mark=='Z' ) err.append ( Messages.begin_comma ); else return true; r.start=0; r.end=t.length; return false; } |
表達式末尾的檢查。確保表達式以合法符號結束。不可以用操作符、函數、逗號或開括號作為表達式結束符。
符號序列的檢查。檢查表達式中的符號序列。在下面的表格中，若 X 軸上的符號和 Y 軸上的符號對應的交界處用 X 作了記號，則相應 X 軸上的符號可以接在 Y 軸上符號的后面。
表 2. 合法的符號序列
|
| _ |
D |
B |
H |
O |
V |
F |
P |
( |
) |
Z |
| D |
_ |
_ |
_ |
_ |
_ |
_ |
犠 |
_ |
犠 |
犠 |
| B |
_ |
_ |
_ |
_ |
_ |
_ |
犠 |
_ |
犠 |
犠 |
| H |
_ |
_ |
_ |
_ |
_ |
_ |
犠 |
_ |
犠 |
犠 |
| O |
_ |
_ |
_ |
_ |
_ |
_ |
犠 |
_ |
犠 |
犠 |
| V |
_ |
_ |
_ |
_ |
_ |
_ |
犠 |
_ |
犠 |
犠 |
| F |
_ |
_ |
_ |
_ |
_ |
_ |
_ |
犠 |
_ |
_ |
| P |
犠 |
犠 |
犠 |
犠 |
犠 |
犠 |
_ |
犠 |
_ |
_ |
| ( |
犠 |
犠 |
犠 |
犠 |
犠 |
犠 |
_ |
犠 |
_ |
_ |
| ) |
_ |
_ |
_ |
_ |
_ |
_ |
犠 |
_ |
犠 |
犠 |
| Z |
犠 |
犠 |
犠 |
犠 |
犠 |
犠 |
_ |
犠 |
_ |
_ |
函數檢查。確保表達式中所有函數的自變量數量正確。
逗號檢查。逗號只能用于分隔函數的自變量。若用于表達式其它地方，就不合法。
一步一步的求值
只有能順利通過以上概括的所有檢查的表達式，W3Eval 才求值。從而確保內建于 W3Eval 中的前提條件不會出現問題。后面的算法用于單步執行表達式求值：
- 找出嵌入最深的那對括號。
- 在這對括號中，找出優先級最高的操作符。
- 若這對括號中沒有操作符：
- 如果表達式再不包含任何其它的括號，求值（過程）完成。
- 如果表達式包含括號，但不包含操作符，則存在一個函數。對函數求值，然后轉到步驟 5。
- 獲取操作數并執行運算。
- 從向量中除去用過的符號并在同一位置放入結果。
- 除去冗余括號。
- 將向量中剩余的符號結合到字符串并在屏幕上顯示結果。
現在，我們將更為詳細的查看算法的每一步，同時查看大部分有意思的代碼片段。
步驟 1：為避免括號的處理，W3Eval 確定哪個子表達式處于嵌套最深的那對括號中。這項任務需要兩步。第一步，W3Eval 必須找出第一個閉括號：
清單 5. 找出第一個閉括號
public static int pos_first_closed_parenthesis( Vector tokens ) { Token t; for ( int i=0; i | 第二步，找出與第一步找到的閉括號相匹配的開括號，如清單 6 所示。
清單 6. 找出匹配的開括號
public static int pos_open_parenthesis( Vector tokens, int closed_parenthesis ) { int i; Token t; i=closed_parenthesis-2; while ( i>=0 ) { t=(Token)tokens.elementAt( i ); if ( t.mark=='(' ) { return i; } i--; } return 0; } |
步驟 2：要實現求值的單步執行，W3Eval 在嵌套最深的那對括號中找出優先級最高的操作符。（操作符的優先級已硬編碼到 applet 中；請參閱參考資料以獲取完整的代碼清單。）
清單 7. 找出優先級最高的操作符
public static int pos_operator( Vector tokens, Range r ) { byte max_priority=Byte.MAX_VALUE; int max_pos=0; byte priority; String operator; Token t; for ( int i=r.start+2; i<=r.end-2; i++ ) { t=(Token)tokens.elementAt( i ); if ( t.mark!='P' ) continue; priority=((Operator)t.token).priority; operator=((Operator)t.token).operator; if ( priority < max_priority || ( operator.equals("^") || operator.equals("**") ) && priority == max_priority ) { max_priority=priority; max_pos=i; } } return max_pos; } | 步驟 3：如果表達式中不包含其它括號，求值的過程就完成。如果表達式包含括號，但不包含操作符，則存在需要求值的函數。
清單 8. 檢查是否還有其它操作符
...int poz_max_op=pos_operator( tokens, range );// if there are no operatorsif ( poz_max_op==0 ) { if ( no_more_parentheses ) { return false; } else { double result; result=function_result( tokens, range.start-1 ); function_tokens_removal( tokens, range.start-1 ); t = new Token ( new Double(result), 'D', 0, 0 ); tokens.setElementAt( t, range.start-1 ); parentheses_removal( tokens, range.start-1 ); return true; } }... | 步驟 4：所有的操作符都是二元的，也就是說第一個操作數位于操作符之前，第二個操作符位于操作符之后。
清單 9. 獲取操作數并執行運算
...double operand1, operand2;// first operand is before...t=(Token)tokens.elementAt( poz_max_op-1 );operand1=operand_value( t );// ...and second operand is after operatort=(Token)tokens.elementAt( poz_max_op+1 );operand2=operand_value( t );// operatort=(Token)tokens.elementAt( poz_max_op );String op=((Operator)t.token).operator;double result=operation_result( operand1, operand2, op );tokens.removeElementAt( poz_max_op+1 );tokens.removeElementAt( poz_max_op );t = new Token ( new Double(result), 'D', 0, 0 );tokens.setElementAt( t, poz_max_op-1 );parentheses_removal( tokens, poz_max_op-1 );... | 操作數可以是變量，還可以是十進制、十六進制、八進制或二進制數。
清單 10. 獲取操作數
public static double operand_value( Token t ) { if ( t.mark=='V' ) return ((Variable)t.token).value; else if ( t.mark=='D' ) return ((Double)t.token).doubleValue(); else if ( t.mark=='H' ) return base_convert( ((String)t.token).substring(2), 16 ); else if ( t.mark=='O' ) return base_convert( ((String)t.token).substring(2), 8 ); else if ( t.mark=='B' ) return base_convert( ((String)t.token).substring(2), 2 ); } | 接下來的方法將不同計數制的數轉化為十進制的形式。
清單 11. 將數轉化為十進制數
public static long base_convert( String s, int base ) { long r=0; int i, j; for ( i=s.length()-1, j=0; i>=0; i--, j++ ) r=r+digit_weight( s.charAt( i ) )*(long)Math.pow( base, j ); return r; }public static int digit_weight( char c ) { if ( Character.isDigit( c ) ) return c-48; else if ( 'A'<=c && c<='f' ) return c-55; else if ( 'a'<=c && c<='f' ) return c-87; return -1; } | 一旦確定操作數和操作符后，就可以執行運算了，如清單 12 所示。
步驟 5：在這步中，W3Eval 從向量中除去用過的符號并在同一位置放入結果。對于函數求值這類情況，除去的是函數、括號、自變量和逗號；而對于操作符求值這類情況而言，除去的則是操作數和操作符。
步驟 6：在求值的這一步，W3Eval 從表達式中除去冗余括號。
清單 13. 除去冗余括號
private static void parentheses_removal( Vector tokens, int pos ) { if ( pos>1 &&&& ((Token)tokens.elementAt( poz-2 )).mark!='F' &&&& ((Token)tokens.elementAt( poz-1 )).mark=='(' &&&& ((Token)tokens.elementAt( poz+1 )).mark==')' || pos==1 &&&& ((Token)tokens.elementAt( 0 )).mark=='(' &&&& ((Token)tokens.elementAt( 2 )).mark==')' ) { tokens.removeElementAt( poz+1 ); tokens.removeElementAt( poz-1 ); } return; } | 步驟 7：在求值的最后一步，向量中剩余的符號被結合到字符串，并在屏幕上顯示。
清單 14. 結合符號并顯示結果
public static String token_join( Vector tokens ) { String result=new String(); Token t; for ( int i=0; i < tokens.size(); i++ ) { t=(Token)tokens.elementAt( i ); if ( t.mark=='D' ) { double n=((Double)t.token).doubleValue(); result=result + formated_number( n ); } else result=result + t.token; if ( result.endsWith( ".0" ) ) result=result.substring( 0, result.length()-2 ); result=result + " "; } return result; } | 結論
本文分析了一個 applet ，它能一步一步的對算術表達式求值。同時還按順序回顧了最有意思的代碼片段，并論述了兩種不同的表達式求值方法。
下一版 W3Eval 有望在各方面得到增強，包括有能力添加用戶定義的功能；支持分數、復數和矩陣；改良的圖形用戶界面（GUI）；大小和速度優化以及安全性方面的增強。我鼓勵您提供您自己對于增強方面的設想。
我希望您會發現 W3Eval 是個對表達式求值有益的在線工具，它在某種程度上比經典的方法更簡單自然。我還期待這里談到的代碼和算法使您明白 Java 語言有助于處理數學問題。
參考資料
關于作者
 Nikola Stepan 是 ABIT Ltd. 的軟件工程師，他在那里從事銀行業軟件的設計和開發。他有廣博的信息系統方面的學術背景和豐富的編程經驗（從低級編程到信息系統）。他特別喜歡面向對象編程語言、關系數據庫、因特網編程和系統編程。他于 1999 年在克羅地亞 Varazdin 的 Faculty of Organisation and Informatic 獲得信息系統學士學位。他會說克羅地亞語、英語和一點德語。請通過 nikola.stepan@vz.tel.hr 與 Nikola 聯系。 | |
|