步骤：
- 表达式语法分析
- 表达式检查
- 一步一步的求值
表达式语法分析
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 联系。 |