前缀、中缀、后缀表达式

对于未经训练的用户来说，计算机科学领域中数学表达式求值的传统方法即不顺手又难以使用；软件工程师 Nikola.Stepan
旨在改变这些传统方法。他的 applet W3Eval
对表达式求值与您用纸笔计算的一系列步骤完全一致，但更快并且没有错误。请往下读，了解这一挑战 — 人类易读的数学到 Java 代码的转换。

还记得在您的第一台科学计算器上用逆波兰表示法奋斗的经历吗？W3Eval applet 无法让您可信赖的 HP-41 更易用，正如它的名称所暗示
— 一个只能运行于 Web 的表达式求值程序。但它的确提供了一种方法 — 人类更易于遵循的对表达式一步一步的求值。

W3Eval的方法与传统计算器不同，却和人类的计算方式一致。当您用传统的计算器计算时，每输入一个新数，前一个数就看不到了。如果在输入一个长表达式中出了错，就
得全部重来。有了
W3Eval，您就能看到参与计算的所有东西，还能轻松的编辑表达式。它独特的能力（一步一步的对表达式求值）非常容易实现，因为用户能看到求值的每一
步，包括临时结果。

本文将让您从头至尾认识 W3Eval 功能性的要点；您将看到一些用于表达式求值的代码。不过，我们还是先看看表达式求值的经典算法，这样您就会明白 W3Eval 方法的差异究竟有多少。

表达式求值的经典算法
编写代码对算术表达式求值的经典方法由 Donald Knuth 描述于 1962 年（请参阅参考资料）。Knuth 将此概括为三个步骤：

• 对中缀表达式进行语法分析
• 中缀表达式到后缀表达式的转换
• 对后缀表达式求值

注意到我们谈到的这个经典算法有些简化：算术表达式只包含操作数、二元操作符和一种括号。此外，对于每个操作数和操作符，只用单个字符表示，使语法分析直观。

表达式表示法
算术表达式中最常见的表示法形式有中缀、前缀和后缀表示法。中缀表示法是书写表达式的常见方式，而前缀和后缀表示法主要用于计算机科学领域。

中缀表示法
中缀表示法是算术表达式的常规表示法。称它为中缀表示法是因为每个操作符都位于其操作数的中间，这种表示法只适用于操作符恰好对应两个操作数的时候（在操作符是二元操作符如加、减、乘、除以及取模的情况下）。对以中缀表示法书写的表达式进行语法分析时，需要用括号和优先规则排除多义性。

Syntax: operand1 operator operand2 Example: (A+B)*C-D/(E+F)

前缀表示法
前缀表示法中，操作符写在操作数的前面。这种表示法经常用于计算机科学，特别是编译器设计方面。为纪念其发明家 — Jan Lukasiewicz（请参阅参考资料），这种表示法也称波兰表示法。

Syntax : operator operand1 operand2 Example : -*+ABC/D+EF

后缀表示法
在后缀表示法中，操作符位于操作数后面。后缀表示法也称逆波兰表示法（reverse Polish notation，RPN），因其使表达式求值变得轻松，所以被普遍使用。

Syntax : operand1 operand2 operator Example : AB+C*DEF+/-

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

• 操作数的顺序与等价的中缀表达式中操作数的顺序一致
• 不需要括号
• 操作符的优先级不相关

中缀表达式到后缀表达式的转换
要把表达式从中缀表达式的形式转换成用后缀表示法表示的等价表达式，必须了解操作符的优先级和结合性。优先级或者说操作符的强度决定求值顺序；优先级高的操作符比优先级低的操作符先求值。 如果所有操作符优先级一样，那么求值顺序就取决于它们的结合性。操作符的结合性定义了相同优先级操作符组合的顺序（从右至左或从左至右）。

Left associativity : A+B+C = (A+B)+C Right associativity : A^B^C = A^(B^C)

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

1. 初始化一个空堆栈，将结果字符串变量置空。 
2. 从左到右读入中缀表达式，每次一个字符。
3. 如果字符是操作数，将它添加到结果字符串。
4. 如果字符是个操作符，弹出（pop）操作符，直至遇见开括号（opening parenthesis）、优先级较低的操作符或者同一优先级的右结合符号。把这个操作符压入（push）堆栈。
5. 如果字符是个开括号，把它压入堆栈。
6. 如果字符是个闭括号（closing parenthesis），在遇见开括号前，弹出所有操作符，然后把它们添加到结果字符串。
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 类的定义

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==‘(‘ &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 检查。检查表达式语法。确保表达式所有部分都被认为是合法的。

表达式开头的检查（请参阅清单 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 中的前提条件不会出现问题。后面的算法用于单步执行表达式求值：

1. 找出嵌入最深的那对括号。
2. 在这对括号中，找出优先级最高的操作符。
3. 若这对括号中没有操作符：
   • 如果表达式再不包含任何其它的括号，求值（过程）完成。
   • 如果表达式包含括号，但不包含操作符，则存在一个函数。对函数求值，然后转到步骤 5。
4. 获取操作数并执行运算。
5. 从向量中除去用过的符号并在同一位置放入结果。
6. 除去冗余括号。
7. 将向量中剩余的符号结合到字符串并在屏幕上显示结果。

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

步骤 1：为避免括号的处理，W3Eval 确定哪个子表达式处于嵌套最深的那对括号中。这项任务需要两步。第一步，W3Eval 必须找出第一个闭括号：

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

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; }

第二步，找出与第一步找到的闭括号相匹配的开括号，如清单 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 { 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：如果表达式中不包含其它括号，求值的过程就完成。如果表达式包含括号，但不包含操作符，则存在需要求值的函数。

清单 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‘ return c-55; else if ( ‘a‘ 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==‘)‘ &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; }

结论
本文分析了一个 applet ，它能一步一步的对算术表达式求值。同时还按顺序回顾了最有意思的代码片段，并论述了两种不同的表达式求值方法。

下一版 W3Eval 有望在各方面得到增强，包括有能力添加用户定义的功能；支持分数、复数和矩阵；改良的图形用户界面（GUI）；大小和速度优化以及安全性方面的增强。我鼓励您提供您自己对于增强方面的设想。

我希望您会发现 W3Eval 是个对表达式求值有益的在线工具，它在某种程度上比经典的方法更简单自然。我还期待这里谈到的代码和算法使您明白 Java 语言有助于处理数学问题。

参考资料

• W3Eval applet 是免费的，它的帮助有助于您解决问题。
• 这张表格展示了 W3Eval 操作符的优先级。
• 请阅读波兰数学家 Jan Lukasiewicz 的传记。
• Donald Knuth，计算机科学领域卓越的学者，曾详尽的就算法的设计和分析撰写和演讲。他的主页提供最近出版的有关其作品的论文和信息的链接。
• 有兴趣随意编写 applet 吗？可以查看我们的教程 Building a Java applet（developerWorks，1999 年）以获得一步一步的指导。
• 您会觉得 Java FAQ 很有用。
• 还有很多有关 applet 的信息在 Peter Van Der Linden（Prentice Hall PTR/Sun Microsystems 出版社出版，1998 年 12 月）的Just Java 2 中。
• 由 Ken Arnold、James Gosling 和 David Holmes 撰写的 The Java Programming Language（Addison Wesley 出版社出版，2000 年 12 月）包含有益的关于集合的信息。
• 学习 Martin Bastiaan 的“A Walk in the Park”（developerWorks，1998 年 1 月），了解更多有关 applet 的知识。
• VisualAge for Java 使 applet 的开发变得轻而易举。
• 在 developerWorks Java 技术专区查找更多 Java 参考资料。

关于作者 Nikola Stepan 是 ABIT Ltd. 的软件工程师，他在那里从事银行业软件的设计和开发。他有广博的信息系统方面的学术背景和丰富的编程经验（从低级编程到信息系统）。他特别喜欢面向对象编 程语言、关系数据库、因特网编程和系统编程。他于 1999 年在克罗地亚 Varazdin 的 Faculty of Organisation and Informatic 获得信息系统学士学位。他会说克罗地亚语、英语和一点德语。请通过 [e-mail] 与 Nikola 联系。