operator是什么意思

本文将让您从头至尾认识W3Eval功能性的要点；您将看到一些用于表达式求值的代码。不

过，我们还是先看看表达式求值的经典算法，这样您就会明白W3Eval方法的差异究竟有多

少。

表达式求值的经典算法

编写代码对算术表达式求值的经典方法由DonaldKnuth描述于1962年（请参阅参考资

料）。Knuth将此概括为三个步骤：

对中缀表达式进行语法分析

中缀表达式到后缀表达式的转换

对后缀表达式求值

注意到我们谈到的这个经典算法有些简化：算术表达式只包含操作数、二元操作符和一种括

号。此外，对于每个操作数和操作符，只用单个字符表示，使语法分析直观。

表达式表示法

算术表达式中最常见的表示法形式有中缀、前缀和后缀表示法。中缀表示法是书写表达式的

常见方式，而前缀和后缀表示法主要用于计算机科学领域。

中缀表示法

中缀表示法是算术表达式的常规表示法。称它为中缀表示法是因为每个操作符都位于其操作

数的中间，这种表示法只适用于操作符恰好对应两个操作数的时候（在操作符是二元操作符

如加、减、乘、除以及取模的情况下）。对以中缀表示法书写的表达式进行语法分析时，需

要用括号和优先规则排除多义性。

Syntax:operand1operatoroperand2

Example:(A+B)*C-D/(E+F)

前缀表示法

前缀表示法中，操作符写在操作数的前面。这种表示法经常用于计算机科学，特别是编译器

设计方面。为纪念其发明家—JanLukasiewicz（请参阅参考资料），这种表示法也称波

兰表示法。

Syntax:operatoroperand1operand2

Example:-*+ABC/D+EF

后缀表示法

在后缀表示法中，操作符位于操作数后面。后缀表示法也称逆波兰表示法（reverPolish

notation，RPN），因其使表达式求值变得轻松，所以被普遍使用。

Syntax:operand1operand2operator

Example:AB+C*DEF+/-

前缀和后缀表示法有三项公共特征：

操作数的顺序与等价的中缀表达式中操作数的顺序一致

不需要括号

操作符的优先级不相关

中缀表达式到后缀表达式的转换

要把表达式从中缀表达式的形式转换成用后缀表示法表示的等价表达式，必须了解操作符的

优先级和结合性。优先级或者说操作符的强度决定求值顺序；优先级高的操作符比优先级低

的操作符先求值。如果所有操作符优先级一样，那么求值顺序就取决于它们的结合性。操

作符的结合性定义了相同优先级操作符组合的顺序（从右至左或从左至右）。

Leftassociativity:A+B+C=(A+B)+C

Rightassociativity:A^B^C=A^(B^C)

转换过程包括用下面的算法读入中缀表达式的操作数、操作符和括号：

1.初始化一个空堆栈，将结果字符串变量置空。

2.从左到右读入中缀表达式，每次一个字符。

3.如果字符是操作数，将它添加到结果字符串。

4.如果字符是个操作符，弹出（pop）操作符，直至遇见开括号（openingparenthesis）、

优先级较低的操作符或者同一优先级的右结合符号。把这个操作符压入（push）堆

栈。

5.如果字符是个开括号，把它压入堆栈。

6.如果字符是个闭括号（closingparenthesis），在遇见开括号前，弹出所有操作符，

然后把它们添加到结果字符串。

7.如果到达输入字符串的末尾，弹出所有操作符并添加到结果字符串。

后缀表达式求值

对后缀表达式求值比直接对中缀表达式求值简单。在后缀表达式中，不需要括号，而且操作

符的优先级也不再起作用了。您可以用如下算法对后缀表达式求值：

1.初始化一个空堆栈

2.从左到右读入后缀表达式

3.如果字符是一个操作数，把它压入堆栈。

4.如果字符是个操作符，弹出两个操作数，执行恰当操作，然后把结果压入堆栈。如

果您不能够弹出两个操作数，后缀表达式的语法就不正确。

5.到后缀表达式末尾，从堆栈中弹出结果。若后缀表达式格式正确，那么堆栈应该为

空。

W3Eval：一种新的方法

W3Eval

的方法与上面概括的经典算法不同。不是把中缀表达式转换为后缀表示法；恰恰相反，它对

中缀表达式直接求值。这种方法比传统方法稍微复杂了些，但它支持一步

一步的求值，在执行时您能看到每一步。求值过程类似于手工计算：如果表达式中包含括号，

先求嵌套最深的括号对中的子表达式的值。所有括号内的子表达式都求

值完毕后，表达式的其它部分再求值。

求值过程分为三个步骤：

1.表达式语法分析

2.表达式检查

3.一步一步的求值

表达式语法分析

W3Eval的数学表达式由数字、变量、操作符、函数和括号组成。除了缺省的十进制计数制

外W3Eval还支持二进制、八进制和十六进制。这些以其它计数制计数的数必须以#开头，

并紧跟b、o或者h来分别表示二进制、八进制或十六进制。

W3Eval的变量是不限长度的大写字母和数字序列，其首字符必须是字母。W3Eval有一些预

定义的变量，不过它也支持用户定义的变量。

W3Eval支持带有固定或不定数量自变量的函数。函数可分为以下几组：

三角函数（sin、cos、tan、cot、c、csc）

反三角函数（asin、acos、atan、atan2、acot、ac、acsc）

双曲线函数（sinh、cosh、tanh、coth、ch、csch）

反双曲线函数（asinh、acosh、atanh、acoth、ach、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的符号

TokenMark类

十进制数Double

二进制数String

十六进制数String

八进制数String

变量Variable

函数Function

操作符Operator

开括号String

闭括号String

逗号String

用以表示函数、操作符和变量类的定义如清单1所示：

清单on、Operator和Variable类的定义

publicclassFunction

{

publicStringfunction;

publicintnumber_of_arguments;

publicFunction(Stringfunction,intnumber_of_arguments)

{

on=function;

_of_arguments=number_of_arguments;

}

publicStringtoString()

{

returnfunction;

}

}

publicclassOperator

{

publicStringoperator;

publicbytepriority;

publicOperator(Stringoperator,bytepriority)

{

or=operator;

ty=priority;

}

publicStringtoString()

{

returnoperator;

}

}

publicclassVariable

{

publicStringvariable;

publicdoublevalue;

publicVariable(Stringvariable,doublevalue)

{

le=variable;

=value;

}

publicStringtoString()

{

returnvariable;

}

}

Token类如清单2所示。

清单类

publicclassToken

{

publicObjecttoken;

publiccharmark;

publicintposition;

publicintlength;

publicToken(Objecttoken,charmark,intposition,intlength)

{

=token;

=mark;

on=position;

=length;

}

publicStringtoString()

{

ng()+";"+mark+";"+position+";"+length+"

";

}

}

表达式检查

检查正规表达式正确性的所有代码都在一个独立的类中。详细的表达式检查能够确定错误确

切的类型和位置。错误检查有七类：

括号检查。W3Eval的表达式可以包含三种括号：标准圆括号、方括号和花括号。如果表达

式包含相同数量的开括号和闭括号，并且每个开括号与一个相应的同种闭括号相匹配，则表

达式的括号语法正确。三种括号在语义上等价，如下面的代码段所示。

清单3.三种括号

;

publicclassParenthes_check

{

publicstaticbooleanis_open_parenthesis(charc)

{

if(c=='('&line;&line;c=='['&line;&line;c=='{')

returntrue;

el

returnfal;

}

publicstaticbooleanis_clod_parenthesis(charc)

{

if(c==')'&line;&line;c==']'&line;&line;c=='}')

returntrue;

el

returnfal;

}

privatestaticbooleanparenthes_match(charopen,charclod)

{

if(open=='('&&clod==')')

returntrue;

elif(open=='['&&clod==']')

returntrue;

elif(open=='{'&&clod=='}')

returntrue;

el

returnfal;

}

publicstaticbooleanparenthes_valid(Stringexp)

{

Stacks=newStack();

inti;

charcurrent_char;

Characterc;

charc1;

booleanret=true;

for(i=0;i{

current_char=(i);

if(is_open_parenthesis(current_char))

{

c=newCharacter(current_char);

(c);

}

elif(is_clod_parenthesis(current_char))

{

if(y())

{

ret=fal;

break;

}

el

{

c=(Character)();

c1=lue();

if(!parenthes_match(c1,current_char))

{

ret=fal;

break;

}

}

}

}

if(!y())

ret=fal;

returnret;

}

}

token检查。检查表达式语法。确保表达式所有部分都被认为是合法的。

表达式开头的检查（请参阅清单4）。确保表达式从合法的符号开始。不可以用操作符、逗

号或闭括号作为表达式的开始符。

清单4.正确的表达式开头的检查

privatestaticbooleanbegin_check(Vectortokens,Ranger,StringBuffer

err)

{

charmark;

Tokent;

t=(Token)tAt(0);

mark=;

if(mark=='P')

(_operator);

elif(mark==')')

(_parenthesis);

elif(mark=='Z')

(_comma);

el

returntrue;

=0;

=;

returnfal;

}

表达式末尾的检查。确保表达式以合法符号结束。不可以用操作符、函数、逗号或开括号作

为表达式结束符。

符号序列的检查。检查表达式中的符号序列。在下面的表格中，若X轴上的符号和Y轴上

的符号对应的交界处用X作了记号，则相应X轴上的符号可以接在Y轴上符号的后面。

表2.合法的符号序列

_DBHOVFP()Z

D______犠_犠犠

B______犠_犠犠

H______犠_犠犠

O______犠_犠犠

V______犠_犠犠

F_______犠__

P犠犠犠犠犠犠_犠__

(犠犠犠犠犠犠_犠__

)______犠_犠犠

Z犠犠犠犠犠犠_犠__

函数检查。确保表达式中所有函数的自变量数量正确。

逗号检查。逗号只能用于分隔函数的自变量。若用于表达式其它地方，就不合法。

一步一步的求值

只有能顺利通过以上概括的所有检查的表达式，W3Eval才求值。从而确保内建于W3Eval中

的前提条件不会出现问题。后面的算法用于单步执行表达式求值：

1.找出嵌入最深的那对括号。

2.在这对括号中，找出优先级最高的操作符。

3.若这对括号中没有操作符：

o如果表达式再不包含任何其它的括号，求值（过程）完成。

o如果表达式包含括号，但不包含操作符，则存在一个函数。对函数求值，然

后转到步骤5。

4.获取操作数并执行运算。

5.从向量中除去用过的符号并在同一位置放入结果。

6.除去冗余括号。

7.将向量中剩余的符号结合到字符串并在屏幕上显示结果。

现在，我们将更为详细的查看算法的每一步，同时查看大部分有意思的代码片段。

步骤1：为避免括号的处理，W3Eval确定哪个子表达式处于嵌套最深的那对括号中。这项

任务需要两步。第一步，W3Eval必须找出第一个闭括号：

清单5.找出第一个闭括号

publicstaticintpos_first_clod_parenthesis(Vectortokens)

{

Tokent;

for(inti=0;i{

t=(Token)tAt(i);

if(==')')

returni;

}

return0;

}

第二步，找出与第一步找到的闭括号相匹配的开括号，如清单6所示。

清单6.找出匹配的开括号

publicstaticintpos_open_parenthesis(Vectortokens,int

clod_parenthesis)

{

inti;

Tokent;

i=clod_parenthesis-2;

while(i>=0)

{

t=(Token)tAt(i);

if(=='(')

{

returni;

}

i--;

}

return0;

}

步骤2：要实现求值的单步执行，W3Eval在嵌套最深的那对括号中找出优先级最高的操作

符。（操作符的优先级已硬编码到applet中；请参阅参考资料以获取完整的代码清单。）

清单7.找出优先级最高的操作符

publicstaticintpos_operator(Vectortokens,Ranger)

{

bytemax_priority=_VALUE;

intmax_pos=0;

bytepriority;

Stringoperator;

Tokent;

for(inti=+2;i{

t=(Token)tAt(i);

if(!='P')

continue;

priority=((Operator)).priority;

operator=((Operator)).operator;

if(("**"))&&priority==

max_priority)

{

max_priority=priority;

max_pos=i;

}

}

returnmax_pos;

}

步骤3：如果表达式中不包含其它括号，求值的过程就完成。如果表达式包含括号，但不包

含操作符，则存在需要求值的函数。

清单8.检查是否还有其它操作符

...

intpoz_max_op=pos_operator(tokens,range);

//iftherearenooperators

if(poz_max_op==0)

{

if(no_more_parenthes)

{

returnfal;

}

el

{

doubleresult;

result=function_result(tokens,-1);

function_tokens_removal(tokens,-1);

t=newToken(newDouble(result),'D',0,0);

mentAt(t,-1);

parenthes_removal(tokens,-1);

returntrue;

}

}

...

步骤4：所有的操作符都是二元的，也就是说第一个操作数位于操作符之前，第二个操作符

位于操作符之后。

清单9.获取操作数并执行运算

...

doubleoperand1,operand2;

//firstoperandisbefore...

t=(Token)tAt(poz_max_op-1);

operand1=operand_value(t);

//...andcondoperandisafteroperator

t=(Token)tAt(poz_max_op+1);

operand2=operand_value(t);

//operator

t=(Token)tAt(poz_max_op);

Stringop=((Operator)).operator;

doubleresult=operation_result(operand1,operand2,op);

ElementAt(poz_max_op+1);

ElementAt(poz_max_op);

t=newToken(newDouble(result),'D',0,0);

mentAt(t,poz_max_op-1);

parenthes_removal(tokens,poz_max_op-1);

...

操作数可以是变量，还可以是十进制、十六进制、八进制或二进制数。

清单10.获取操作数

publicstaticdoubleoperand_value(Tokent)

{

if(=='V')

return((Variable)).value;

elif(=='D')

return((Double)).doubleValue();

elif(=='H')

returnba_convert(((String)).substring(2),16);

elif(=='O')

returnba_convert(((String)).substring(2),8);

elif(=='B')

returnba_convert(((String)).substring(2),2);

}

接下来的方法将不同计数制的数转化为十进制的形式。

清单11.将数转化为十进制数

publicstaticlongba_convert(Strings,intba)

{

longr=0;

inti,j;

for(i=()-1,j=0;i>=0;i--,j++)

r=r+digit_weight((i))*(long)(ba,j);

returnr;

}

publicstaticintdigit_weight(charc)

{

if(t(c))

returnc-48;

elif('A'returnc-55;

elif('a'returnc-87;

return-1;

}

一旦确定操作数和操作符后，就可以执行运算了，如清单12所示。

步骤5：在这步中，W3Eval从向量中除去用过的符号并在同一位置放入结果。对于函数求

值这类情况，除去的是函数、括号、自变量和逗号；而对于操作符求值这类情况而言，除去

的则是操作数和操作符。

步骤6：在求值的这一步，W3Eval从表达式中除去冗余括号。

清单13.除去冗余括号

privatestaticvoidparenthes_removal(Vectortokens,intpos)

{

if(

pos>1&&

amp;&&

amp;

((Token)tAt(poz-2)).mark!='F'&&

amp;&&

amp;

((Token)tAt(poz-1)).mark=='('&&

amp;&&

amp;

((Token)tAt(poz+1)).mark==')'

&line;&line;

pos==1&&

amp;&&

amp;

((Token)tAt(0)).mark=='('&&

amp;&&

amp;

((Token)tAt(2)).mark==')'

)

{

ElementAt(poz+1);

ElementAt(poz-1);

}

return;

}

步骤7：在求值的最后一步，向量中剩余的符号被结合到字符串，并在屏幕上显示。

清单14.结合符号并显示结果

publicstaticStringtoken_join(Vectortokens)

{

Stringresult=newString();

Tokent;

for(inti=0;i{

t=(Token)tAt(i);

if(=='D')

{

doublen=((Double)).doubleValue();

result=result+formated_number(n);

}

el

result=result+;

if(th(".0"))

result=ing(0,()-2);

result=result+"";

}

returnresult;

}