步驟：
- 表達式語法分析
- 表達式檢查
- 一步一步的求值
表達式語法分析
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<tokens.size(); i++ )
{
t=(Token)tokens.elementAt( i );
if ( t.mark==')' )
return i;
}
return 0;
}
|
第二步，找出與第一步找到的閉括號相匹配的開括號，如 清單 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 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：所有的操作符都是二元的，也就是說第一個操作數位于操作符之前，第二個操作符位于操作符之后。
清單 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 );
...
|
操作數可以是變量，還可以是十進制、十六進制、八進制或二進制數。
清單 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 &&
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==')'
||
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 < 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 聯系。 |