對于未經(jīng)訓練的用戶(hù)來(lái)說(shuō)，計算機科學(xué)領(lǐng)域中數學(xué)表達式求值的傳統方法即不順手又難以使用；軟件工程師 Nikola.Stepan
旨在改變這些傳統方法。他的 applet W3Eval
對表達式求值與您用紙筆計算的一系列步驟完全一致，但更快并且沒(méi)有錯誤。請往下讀，了解這一挑戰 — 人類(lèi)易讀的數學(xué)到 Java 代碼的轉換。
還記得在您的第一臺科學(xué)計算器上用逆波蘭表示法奮斗的經(jīng)歷嗎？W3Eval applet 無(wú)法讓您可信賴(lài)的 HP-41 更易用，正如它的名稱(chēng)所暗示
— 一個(gè)只能運行于 Web 的表達式求值程序。但它的確提供了一種方法 — 人類(lèi)更易于遵循的對表達式一步一步的求值。
W3Eval的方法與傳統計算器不同，卻和人類(lèi)的計算方式一致。當您用傳統的計算器計算時(shí)，每輸入一個(gè)新數，前一個(gè)數就看不到了。如果在輸入一個(gè)長(cháng)表達式中出了錯，就
得全部重來(lái)。有了
W3Eval，您就能看到參與計算的所有東西，還能輕松的編輯表達式。它獨特的能力（一步一步的對表達式求值）非常容易實(shí)現，因為用戶(hù)能看到求值的每一
步，包括臨時(shí)結果。
本文將讓您從頭至尾認識 W3Eval 功能性的要點(diǎn)；您將看到一些用于表達式求值的代碼。不過(guò)，我們還是先看看表達式求值的經(jīng)典算法，這樣您就會(huì )明白 W3Eval 方法的差異究竟有多少。
表達式求值的經(jīng)典算法
編寫(xiě)代碼對算術(shù)表達式求值的經(jīng)典方法由 Donald Knuth 描述于 1962 年（請參閱參考資料）。Knuth 將此概括為三個(gè)步驟：
- 對中綴表達式進(jìn)行語(yǔ)法分析
- 中綴表達式到后綴表達式的轉換
- 對后綴表達式求值
注意到我們談到的這個(gè)經(jīng)典算法有些簡(jiǎn)化：算術(shù)表達式只包含操作數、二元操作符和一種括號。此外，對于每個(gè)操作數和操作符，只用單個(gè)字符表示，使語(yǔ)法分析直觀(guān)。
表達式表示法
算術(shù)表達式中最常見(jiàn)的表示法形式有中綴、前綴和后綴表示法。中綴表示法是書(shū)寫(xiě)表達式的常見(jiàn)方式，而前綴和后綴表示法主要用于計算機科學(xué)領(lǐng)域。
中綴表示法
中綴表示法是算術(shù)表達式的常規表示法。稱(chēng)它為中綴表示法是因為每個(gè)操作符都位于其操作數的中間，這種表示法只適用于操作符恰好對應兩個(gè)操作數的時(shí)候（在操作符是二元操作符如加、減、乘、除以及取模的情況下）。對以中綴表示法書(shū)寫(xiě)的表達式進(jìn)行語(yǔ)法分析時(shí)，需要用括號和優(yōu)先規則排除多義性。
Syntax: operand1 operator operand2
Example: (A+B)*C-D/(E+F)
|
前綴表示法
前綴表示法中，操作符寫(xiě)在操作數的前面。這種表示法經(jīng)常用于計算機科學(xué)，特別是編譯器設計方面。為紀念其發(fā)明家 — Jan Lukasiewicz（請參閱參考資料），這種表示法也稱(chēng)波蘭表示法。
Syntax : operator operand1 operand2
Example : -*+ABC/D+EF
|
后綴表示法
在后綴表示法中，操作符位于操作數后面。后綴表示法也稱(chēng)逆波蘭表示法（reverse Polish notation，RPN），因其使表達式求值變得輕松，所以被普遍使用。
Syntax : operand1 operand2 operator
Example : AB+C*DEF+/-
|
前綴和后綴表示法有三項公共特征：
- 操作數的順序與等價(jià)的中綴表達式中操作數的順序一致
- 不需要括號
- 操作符的優(yōu)先級不相關(guān)
中綴表達式到后綴表達式的轉換
要把表達式從中綴表達式的形式轉換成用后綴表示法表示的等價(jià)表達式，必須了解操作符的優(yōu)先級和結合性。優(yōu)先級或者說(shuō)操作符的強度決定求值順序；優(yōu)先級高的操作符比優(yōu)先級低的操作符先求值。 如果所有操作符優(yōu)先級一樣，那么求值順序就取決于它們的結合性。操作符的結合性定義了相同優(yōu)先級操作符組合的順序（從右至左或從左至右）。
Left associativity : A+B+C = (A+B)+C
Right associativity : A^B^C = A^(B^C)
|
轉換過(guò)程包括用下面的算法讀入中綴表達式的操作數、操作符和括號：
- 初始化一個(gè)空堆棧，將結果字符串變量置空。
- 從左到右讀入中綴表達式，每次一個(gè)字符。
- 如果字符是操作數，將它添加到結果字符串。
- 如果字符是個(gè)操作符，彈出（pop）操作符，直至遇見(jiàn)開(kāi)括號（opening parenthesis）、優(yōu)先級較低的操作符或者同一優(yōu)先級的右結合符號。把這個(gè)操作符壓入（push）堆棧。
- 如果字符是個(gè)開(kāi)括號，把它壓入堆棧。
- 如果字符是個(gè)閉括號（closing parenthesis），在遇見(jiàn)開(kāi)括號前，彈出所有操作符，然后把它們添加到結果字符串。
- 如果到達輸入字符串的末尾，彈出所有操作符并添加到結果字符串。
后綴表達式求值
對后綴表達式求值比直接對中綴表達式求值簡(jiǎn)單。在后綴表達式中，不需要括號，而且操作符的優(yōu)先級也不再起作用了。您可以用如下算法對后綴表達式求值：
- 初始化一個(gè)空堆棧
- 從左到右讀入后綴表達式
- 如果字符是一個(gè)操作數，把它壓入堆棧。
- 如果字符是個(gè)操作符，彈出兩個(gè)操作數，執行恰當操作，然后把結果壓入堆棧。如果您不能夠彈出兩個(gè)操作數，后綴表達式的語(yǔ)法就不正確。
- 到后綴表達式末尾，從堆棧中彈出結果。若后綴表達式格式正確，那么堆棧應該為空。
W3Eval：一種新的方法
W3Eval
的方法與上面概括的經(jīng)典算法不同。不是把中綴表達式轉換為后綴表示法；恰恰相反，它對中綴表達式直接求值。這種方法比傳統方法稍微復雜了些，但它支持一步
一步的求值，在執行時(shí)您能看到每一步。求值過(guò)程類(lèi)似于手工計算：如果表達式中包含括號，先求嵌套最深的括號對中的子表達式的值。所有括號內的子表達式都求
值完畢后，表達式的其它部分再求值。
求值過(guò)程分為三個(gè)步驟：
- 表達式語(yǔ)法分析
- 表達式檢查
- 一步一步的求值
表達式語(yǔ)法分析
W3Eval 的數學(xué)表達式由數字、變量、操作符、函數和括號組成。除了缺省的十進(jìn)制計數制外 W3Eval 還支持二進(jìn)制、八進(jìn)制和十六進(jìn)制。這些以其它計數制計數的數必須以 # 開(kāi)頭，并緊跟 b、o 或者 h 來(lái)分別表示二進(jìn)制、八進(jìn)制或十六進(jìn)制。
W3Eval 的變量是不限長(cháng)度的大寫(xiě)字母和數字序列，其首字符必須是字母。W3Eval 有一些預定義的變量，不過(guò)它也支持用戶(hù)定義的變量。
W3Eval 支持帶有固定或不定數量自變量的函數。 函數可分為以下幾組：
- 三角函數（sin、cos、tan、cot、sec、csc）
- 反三角函數（asin、acos、atan、atan2、acot、asec、acsc）
- 雙曲線(xiàn)函數（sinh、cosh、tanh、coth、sech、csch）
- 反雙曲線(xiàn)函數（asinh、acosh、atanh、acoth、asech、acsch）
- 指數函數（log、log2、log10、exp、exp2、exp10、sqrt、cur）
- 組合學(xué)函數（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 對表達式進(jìn)行語(yǔ)法分析，也就是指它識別出表達式的算術(shù)成分，并將它們轉化成語(yǔ)言符號（token），然后把它們放入向量。表達式一旦處于這種狀態(tài)，就為下面兩步做好了準備：表達式檢查和求值。
W3Eval 的符號（token）是算術(shù)表達式的組成部分；記號（mark） 是獨立的字符， 由 applet 使用，作為識別各種符號的內部標志。每種符號有唯一的 mark 與之對應。W3Eval 的表達式由表 1 所示的符號組成。
表 1. W3Eval 的符號
| Token | Mark | 類(lèi) |
| 十進(jìn)制數 | | Double |
| 二進(jìn)制數 | | String |
| 十六進(jìn)制數 | | String |
| 八進(jìn)制數 | | String |
| 變量 | | Variable |
| 函數 | | Function |
| 操作符 | | Operator |
| 開(kāi)括號 | | String |
| 閉括號 | | String |
| 逗號 | | String |
用以表示函數、操作符和變量類(lèi)的定義如清單 1 所示：
清單 1. Function、Operator 和 Variable 類(lèi)的定義
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 類(lèi)如清單 2 所示。
清單 2. Token 類(lèi)
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+"
";
}
}
|
表達式檢查
檢查正規表達式正確性的所有代碼都在一個(gè)獨立的類(lèi)中。詳細的表達式檢查能夠確定錯誤確切的類(lèi)型和位置。 錯誤檢查有七類(lèi)：
括號檢查。W3Eval 的表達式可以包含三種括號：標準圓括號、方括號和花括號。如果表達式包含相同數量的開(kāi)括號和閉括號，并且每個(gè)開(kāi)括號與一個(gè)相應的同種閉括號相匹配，則表達式的括號語(yǔ)法正確。三種括號在語(yǔ)義上等價(jià)，如下面的代碼段所示。
清單 3. 三種括號
import java.util.Stack;
public class Parentheses_check
{
public static boolean is_open_parenthesis( char c )
{
if ( c==‘(‘ &line;&line; c==‘[‘ &line;&line; c==‘{‘ )
return true;
else
return false;
}
public static boolean is_closed_parenthesis( char c )
{
if ( c==‘)‘ &line;&line; c==‘]‘ &line;&line; 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 {
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 檢查。檢查表達式語(yǔ)法。確保表達式所有部分都被認為是合法的。
表達式開(kāi)頭的檢查（請參閱清單 4）。確保表達式從合法的符號開(kāi)始。不可以用操作符、逗號或閉括號作為表達式的開(kāi)始符。
清單 4. 正確的表達式開(kāi)頭的檢查
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;
}
|
表達式末尾的檢查。確保表達式以合法符號結束。不可以用操作符、函數、逗號或開(kāi)括號作為表達式結束符。
符號序列的檢查。檢查表達式中的符號序列。在下面的表格中，若 X 軸上的符號和 Y 軸上的符號對應的交界處用 X 作了記號，則相應 X 軸上的符號可以接在 Y 軸上符號的后面。
表 2. 合法的符號序列
|
| _ | D | B | H | O | V | F | P | ( | ) | Z |
| D | _ | _ | _ | _ | _ | _ | 犠 | _ | 犠 | 犠 |
| B | _ | _ | _ | _ | _ | _ | 犠 | _ | 犠 | 犠 |
| H | _ | _ | _ | _ | _ | _ | 犠 | _ | 犠 | 犠 |
| O | _ | _ | _ | _ | _ | _ | 犠 | _ | 犠 | 犠 |
| V | _ | _ | _ | _ | _ | _ | 犠 | _ | 犠 | 犠 |
| F | _ | _ | _ | _ | _ | _ | _ | 犠 | _ | _ |
| P | 犠 | 犠 | 犠 | 犠 | 犠 | 犠 | _ | 犠 | _ | _ |
| ( | 犠 | 犠 | 犠 | 犠 | 犠 | 犠 | _ | 犠 | _ | _ |
| ) | _ | _ | _ | _ | _ | _ | 犠 | _ | 犠 | 犠 |
| Z | 犠 | 犠 | 犠 | 犠 | 犠 | 犠 | _ | 犠 | _ | _ |
函數檢查。確保表達式中所有函數的自變量數量正確。
逗號檢查。逗號只能用于分隔函數的自變量。若用于表達式其它地方，就不合法。
一步一步的求值
只有能順利通過(guò)以上概括的所有檢查的表達式，W3Eval 才求值。從而確保內建于 W3Eval 中的前提條件不會(huì )出現問(wèn)題。后面的算法用于單步執行表達式求值：
- 找出嵌入最深的那對括號。
- 在這對括號中，找出優(yōu)先級最高的操作符。
- 若這對括號中沒(méi)有操作符：
- 如果表達式再不包含任何其它的括號，求值（過(guò)程）完成。
- 如果表達式包含括號，但不包含操作符，則存在一個(gè)函數。對函數求值，然后轉到步驟 5。
- 獲取操作數并執行運算。
- 從向量中除去用過(guò)的符號并在同一位置放入結果。
- 除去冗余括號。
- 將向量中剩余的符號結合到字符串并在屏幕上顯示結果。
現在，我們將更為詳細的查看算法的每一步，同時(shí)查看大部分有意思的代碼片段。
步驟 1：為避免括號的處理，W3Eval 確定哪個(gè)子表達式處于嵌套最深的那對括號中。這項任務(wù)需要兩步。第一步，W3Eval 必須找出第一個(gè)閉括號：
清單 5. 找出第一個(gè)閉括號
public static int pos_first_closed_parenthesis( Vector tokens )
{
Token t;
for ( int i=0; i {
t=(Token)tokens.elementAt( i );
if ( t.mark==‘)‘ )
return i;
}
return 0;
}
|
第二步，找出與第一步找到的閉括號相匹配的開(kāi)括號，如清單 6 所示。
清單 6. 找出匹配的開(kāi)括號
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：要實(shí)現求值的單步執行，W3Eval 在嵌套最深的那對括號中找出優(yōu)先級最高的操作符。（操作符的優(yōu)先級已硬編碼到 applet 中；請參閱參考資料以獲取完整的代碼清單。）
清單 7. 找出優(yōu)先級最高的操作符
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 {
t=(Token)tokens.elementAt( i );
if ( t.mark!=‘P‘ )
continue;
priority=((Operator)t.token).priority;
operator=((Operator)t.token).operator;
if ( priority operator.equals("**") ) && priority == max_priority )
{
max_priority=priority;
max_pos=i;
}
}
return max_pos;
}
|
步驟 3：如果表達式中不包含其它括號，求值的過(guò)程就完成。如果表達式包含括號，但不包含操作符，則存在需要求值的函數。
清單 8. 檢查是否還有其它操作符
...
int poz_max_op=pos_operator( tokens, range );
// if there are no operators
if ( 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：所有的操作符都是二元的，也就是說(shuō)第一個(gè)操作數位于操作符之前，第二個(gè)操作符位于操作符之后。
清單 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 operator
t=(Token)tokens.elementAt( poz_max_op+1 );
operand2=operand_value( t );
// operator
t=(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 );
...
|
操作數可以是變量，還可以是十進(jìn)制、十六進(jìn)制、八進(jìn)制或二進(jìn)制數。
清單 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 );
}
|
接下來(lái)的方法將不同計數制的數轉化為十進(jìn)制的形式。
清單 11. 將數轉化為十進(jìn)制數
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‘ return c-55;
else if ( ‘a‘ return c-87;
return -1;
}
|
一旦確定操作數和操作符后，就可以執行運算了，如清單 12 所示。
步驟 5：在這步中，W3Eval 從向量中除去用過(guò)的符號并在同一位置放入結果。對于函數求值這類(lèi)情況，除去的是函數、括號、自變量和逗號；而對于操作符求值這類(lèi)情況而言，除去的則是操作數和操作符。
步驟 6：在求值的這一步，W3Eval 從表達式中除去冗余括號。
清單 13. 除去冗余括號
private static void parentheses_removal( Vector tokens, int pos )
{
if (
pos>1 &&
amp;&&
amp;
((Token)tokens.elementAt( poz-2 )).mark!=‘F‘ &&
amp;&&
amp;
((Token)tokens.elementAt( poz-1 )).mark==‘(‘ &&
amp;&&
amp;
((Token)tokens.elementAt( poz+1 )).mark==‘)‘
&line;&line;
pos==1 &&
amp;&&
amp;
((Token)tokens.elementAt( 0 )).mark==‘(‘ &&
amp;&&
amp;
((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 {
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;
}
|
結論
本文分析了一個(gè) applet ，它能一步一步的對算術(shù)表達式求值。同時(shí)還按順序回顧了最有意思的代碼片段，并論述了兩種不同的表達式求值方法。
下一版 W3Eval 有望在各方面得到增強，包括有能力添加用戶(hù)定義的功能；支持分數、復數和矩陣；改良的圖形用戶(hù)界面（GUI）；大小和速度優(yōu)化以及安全性方面的增強。我鼓勵您提供您自己對于增強方面的設想。
我希望您會(huì )發(fā)現 W3Eval 是個(gè)對表達式求值有益的在線(xiàn)工具，它在某種程度上比經(jīng)典的方法更簡(jiǎn)單自然。我還期待這里談到的代碼和算法使您明白 Java 語(yǔ)言有助于處理數學(xué)問(wèn)題。
參考資料
