如果你编过24点小游戏,就知道,这其实是一个解析表达式的问题。
人类比较习惯于使用中缀表达式,例如你所给的字符串,实际就是一个中缀表达式,操作符放在操所数的中间。
但是中缀表达式计算机处理起来并是很好,而且,如果表达式含有括号(指定优先级),则计算顺序就的重新安排。
因此,计算机处理中缀表达式时,会将其进行预处理,转换为后缀表达法,然后再用一个算法计算,这个算法在下面的算法介绍中做了详细介绍。
如果可能的话,你可以在网上搜索以下现成的表达式解析程序,或者你就按照下面的方法,自己编写一个程序来进行处理。
我这里只有JAVA的解析器,不知道你想不想要,若需请告知邮箱。
下面给出了算法知识。
对于未经训练的用户来说,计算机科学领域中数学表达式求值的传统方法即不顺手又难以使用;软件工程师 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)
转换过程包括用下面的算法读入中缀表达式的操作数、操作符和括号:
初始化一个空堆栈,将结果字符串变量置空。
从左到右读入中缀表达式,每次一个字符。
如果字符是操作数,将它添加到结果字符串。
如果字符是个操作符,弹出(pop)操作符,直至遇见开括号(opening parenthesis)、优先级较低的操作符或者同一优先级的右结合符号。把这个操作符压入(push)堆栈。
如果字符是个开括号,把它压入堆栈。
如果字符是个闭括号(closing parenthesis),在遇见开括号前,弹出所有操作符,然后把它们添加到结果字符串。
如果到达输入字符串的末尾,弹出所有操作符并添加到结果字符串。
后缀表达式求值
对后缀表达式求值比直接对中缀表达式求值简单。在后缀表达式中,不需要括号,而且操作符的优先级也不再起作用了。您可以用如下算法对后缀表达式求值:
初始化一个空堆栈
从左到右读入后缀表达式
如果字符是一个操作数,把它压入堆栈。
如果字符是个操作符,弹出两个操作数,执行恰当操作,然后把结果压入堆栈。如果您不能够弹出两个操作数,后缀表达式的语法就不正确。
到后缀表达式末尾,从堆栈中弹出结果。若后缀表达式格式正确,那么堆栈应该为空。