前缀中缀后缀表达式.docx
《前缀中缀后缀表达式.docx》由会员分享，可在线阅读，更多相关《前缀中缀后缀表达式.docx（19页珍藏版）》请在冰点文库上搜索。
前缀中缀后缀表达式
前缀、中缀、后缀表达式
对于未经训练的用户来说，计算机科学领域中数学表达式求值的传统方法即不顺手又难以使用；软件工程师Nikola.Stepan旨在改变这些传统方法。
他的appletW3Eval对表达式求值与您用纸笔计算的一系列步骤完全一致，但更快并且没有错误。
请往下读，了解这一挑战—人类易读的数学到Java代码的转换。
还记得在您的第一台科学计算器上用逆波兰表示法奋斗的经历吗？
W3Evalapplet无法让您可信赖的HP-41更易用，正如它的名称所暗示—一个只能运行于Web的表达式求值程序。
但它的确提供了一种方法—人类更易于遵循的对表达式一步一步的求值。
W3Eval的方法与传统计算器不同，却和人类的计算方式一致。
当您用传统的计算器计算时，每输入一个新数，前一个数就看不到了。
如果在输入一个长表达式中出了错，就
得全部重来。
有了W3Eval，您就能看到参与计算的所有东西，还能轻松的编辑表达式。
它独特的能力（一步一步的对表达式求值）非常容易实现，因为用户能看到求值的每一
步，包括临时结果。
本文将让您从头至尾认识W3Eval功能性的要点；您将看到一些用于表达式求值的代码。
不过，我们还是先看看表达式求值的经典算法，这样您就会明白W3Eval方法的差异究竟有多少。
表达式求值的经典算法
编写代码对算术表达式求值的经典方法由DonaldKnuth描述于1962年（请参阅参考资料）。
Knuth将此概括为三个步骤：
∙对中缀表达式进行语法分析
∙中缀表达式到后缀表达式的转换
∙对后缀表达式求值
注意到我们谈到的这个经典算法有些简化：
算术表达式只包含操作数、二元操作符和一种括号。
此外，对于每个操作数和操作符，只用单个字符表示，使语法分析直观。
表达式表示法
算术表达式中最常见的表示法形式有中缀、前缀和后缀表示法。
中缀表示法是书写表达式的常见方式，而前缀和后缀表示法主要用于计算机科学领域。
中缀表示法
中缀表示法是算术表达式的常规表示法。
称它为中缀表示法是因为每个操作符都位于其操作数的中间，这种表示法只适用于操作符恰好对应两个操作数的时候（在操作符是二元操作符如加、减、乘、除以及取模的情况下）。
对以中缀表示法书写的表达式进行语法分析时，需要用括号和优先规则排除多义性。
Syntax:
operand1operatoroperand2
Example:
（A+B）*C-D/（E+F）
前缀表示法
前缀表示法中，操作符写在操作数的前面。
这种表示法经常用于计算机科学，特别是编译器设计方面。
为纪念其发明家—JanLukasiewicz（请参阅参考资料），这种表示法也称波兰表示法。
Syntax:
operatoroperand1operand2
Example:
-*+ABC/D+EF
后缀表示法
在后缀表示法中，操作符位于操作数后面。
后缀表示法也称逆波兰表示法（reversePolishnotation，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、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类的定义
publicclassFunction
{
publicStringfunction;
publicintnumber_of_arguments;
publicFunction（Stringfunction,intnumber_of_arguments）
{
this.function=function;
this.number_of_arguments=number_of_arguments;
}
publicStringtoString（）
{
returnfunction;
}
}
publicclassOperator
{
publicStringoperator;
publicbytepriority;
publicOperator（Stringoperator,bytepriority）
{
this.operator=operator;
this.priority=priority;
}
publicStringtoString（）
{
returnoperator;
}
}
publicclassVariable
{
publicStringvariable;
publicdoublevalue;
publicVariable（Stringvariable,doublevalue）
{
this.variable=variable;
this.value=value;
}
publicStringtoString（）
{
returnvariable;
}
}
Token 类如清单2所示。
清单2.Token类
publicclassToken
{
publicObjecttoken;
publiccharmark;
publicintposition;
publicintlength;
publicToken（Objecttoken,charmark,intposition,intlength）
{
this.token=token;
this.mark=mark;
this.position=position;
this.length=length;
}
publicStringtoString（）
{
returntoken.toString（）+";"+mark+";"+position+";"+length+"
";
}
}
表达式检查
检查正规表达式正确性的所有代码都在一个独立的类中。
详细的表达式检查能够确定错误确切的类型和位置。
错误检查有七类：
括号检查。
W3Eval的表达式可以包含三种括号：
标准圆括号、方括号和花括号。
如果表达式包含相同数量的开括号和闭括号，并且每个开括号与一个相应的同种闭括号相匹配，则表达式的括号语法正确。
三种括号在语义上等价，如下面的代码段所示。
清单3.三种括号
importjava.util.Stack;
publicclassParentheses_check
{
publicstaticbooleanis_open_parenthesis（charc）
{
if（c==‘（‘&line;&line;c==‘[‘&line;&line;c==‘{‘）
returntrue;
else
returnfalse;
}
publicstaticbooleanis_closed_parenthesis（charc）
{
if（c==‘）‘&line;&line;c==‘]‘&line;&line;c==‘}‘）
returntrue;
else
returnfalse;
}
privatestaticbooleanparentheses_match（charopen,charclosed）
{
if（open==‘（‘&&closed==‘）‘）
returntrue;
elseif（open==‘[‘&&closed==‘]‘）
returntrue;
elseif（open==‘{‘&&closed==‘}‘）
returntrue;
else
returnfalse;
}
publicstaticbooleanparentheses_valid（Stringexp）
{
Stacks=newStack（）;
inti;
charcurrent_char;
Characterc;
charc1;
booleanret=true;
for（i=0;i{
current_char=exp.charAt（i）;
if（is_open_parenthesis（current_char））
{
c=newCharacter（current_char）;
s.push（c）;
}
elseif（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;
returnret;
}
}
token检查。
检查表达式语法。
确保表达式所有部分都被认为是合法的。
表达式开头的检查（请参阅清单4）。
确保表达式从合法的符号开始。
不可以用操作符、逗号或闭括号作为表达式的开始符。
清单4.正确的表达式开头的检查
privatestaticbooleanbegin_check（Vectortokens,Ranger,StringBuffererr）
{
charmark;
Tokent;
t=（Token）tokens.elementAt（0）;
mark=t.mark;
if（mark==‘P‘）
err.append（Messages.begin_operator）;
elseif（mark==‘）‘）
err.append（Messages.begin_parenthesis）;
elseif（mark==‘Z‘）
err.append（Messages.begin_comma）;
else
returntrue;
r.start=0;
r.end=t.length;
returnfalse;
}
表达式末尾的检查。
确保表达式以合法符号结束。
不可以用操作符、函数、逗号或开括号作为表达式结束符。
符号序列的检查。
检查表达式中的符号序列。
在下面的表格中，若X轴上的符号和Y轴上的符号对应的交界处用X作了记号，则相应X轴上的符号可以接在Y轴上符号的后面。
表2.合法的符号序列
_
D
B
H
O
V
F
P
（
）
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_closed_parenthesis（Vectortokens）
{
Tokent;
for（inti=0;i{
t=（Token）tokens.elementAt（i）;
if（t.mark==‘）‘）
returni;
}
return0;
}
第二步，找出与第一步找到的闭括号相匹配的开括号，如清单6所示。
清单6.找出匹配的开括号
publicstaticintpos_open_parenthesis（Vectortokens,intclosed_parenthesis）
{
inti;
Tokent;
i=closed_parenthesis-2;
while（i>=0）
{
t=（Token）tokens.elementAt（i）;
if（t.mark==‘（‘）
{
returni;
}
i--;
}
return0;
}
步骤2：
要实现求值的单步执行，W3Eval在嵌套最深的那对括号中找出优先级最高的操作符。
（操作符的优先级已硬编码到applet中；请参阅参考资料以获取完整的代码清单。
）
清单7.找出优先级最高的操作符
publicstaticintpos_operator（Vectortokens,Ranger）
{
bytemax_priority=Byte.MAX_VALUE;
intmax_pos=0;
bytepriority;
Stringoperator;
Tokent;
for（inti=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（priorityoperator.equals（"**"））&&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_parentheses）
{
returnfalse;
}
else
{
doubleresult;
result=function_result（tokens,range.start-1）;
function_tokens_removal（tokens,range.start-1）;
t=newToken（newDouble（result）,‘D‘,0,0）;
tokens.setElementAt（t,range.start-1）;
parentheses_removal（tokens,range.start-1）;
returntrue;
}
}
...
步骤4：
所有的操作符都是二元的，也就是说第一个操作数位于操作符之前，第二个操作符位于操作符之后。
清单9.获取操作数并执行运算
...
doubleoperand1,operand2;
//firstoperandisbefore...
t=（Token）tokens.elementAt（poz_max_op-1）;
operand1=operand_value（t）;
//...andsecondoperandisafteroperator
t=（Token）tokens.elementAt（poz_max_op+1）;
operand2=operand_value（t）;
//operator
t=（Token）tokens.elementAt（poz_max_op）;
Stringop=（（Operator）t.token）.operato
升级会员 