中缀算术表达式的轻量化求值算法

摘要：

针对当前中缀算术表达式求值算法笨重或者复杂的问题，提出了一种轻量化的中缀算术表达式求值算法。该算法基于逆向拆分中缀算术表达式的思路，使用递归解析的方法，等价于中缀算术表达式的构造二叉树表示。实验结果表明，该算法与传统逆波兰表达式（RPN）转换、求值算法相比，该算法无需做逆波兰表达式转换，无需人工栈辅助，实现代码量仅有其1/6，而效率仅下降6.9%。与W3Eval算法相比，该算法无需符号转置表，支持算符自定义或重定义，实现代码量不到其1/2。该算法实现代价低，适用于Web应用的Browser端，及嵌入式应用等轻量化应用场合。

关键词：

轻量化算法；中缀算术表达式；逆向拆分；逆波兰表达式；W3Eval

0引言

中缀算术表达式求值在编译系统以及各种涉及表达式计算的应用系统中被广泛使用。中缀表示法是一种通用的算术式或逻辑式的表示方法，其算符是以中缀形式位于两个算数的中间[1]，例如：2+3。中缀表示法与人类日常习惯相一致，因此最为常用，但在使用计算机对表达式求值时，中缀表示法有诸多不便[2-3]，故当前通用的是Donald Knuth于1962年提出的方法：将中缀表达式转换为后缀表达式，即逆波兰表达式（Reverse Polish Notation，RPN），然后再对RPN求值[1-3]。该方法适应性良好，理论成熟完备，时间复杂度低，适合在编译等复杂系统中使用；但是，其缺点为算法笨重、代码量大，且中缀表达式转换为RPN，以及对RPN求值均需要人工栈辅助[1-3]。

当前，Web应用中的Browser端由ECMA（European Computer Manufacturers Association）脚本实现的算法需满足轻量化的要求[4]，嵌入式应用也要求算法轻量化，即结构简单，实现代价低，代码量小[5]。其中用到中缀算术表达式求值的多为一些人机接口中的内容，并没有类似编译系统这样的复杂需求，故使用RPN求值带来的程序复杂性增加与Web应用Browser端和嵌入式应用的轻量化需求不符。

1轻量化算法研究现状

2001年，ABIT Ltd.的软件工程师Stepan[6]提出了一种名为W3Eval的算法，并在2006年和2007年进行了两次版本升级。根据文献[6]的叙述，该算法对中缀算术表达式求值时，无需做RPN转换，可直接求值，且无需人工栈辅助，其代码量较传统RPN算法有将近2/3的缩减，是一种轻量化的算法。但是，该算法使用了符号转置表[6]对算符、算数以及算符优先级进行标记，在提高算法适应性的同时也增加了复杂性；并且，由于该算法对表达式进行正向解析[6]，使得该算法较为晦涩难懂。当然，该算法有支持符号量运算[6-7]、支持复数和矩阵运算等优势。

此外，还有表达式构造树求值算法[7]、人工智能表达式求值算法[8]等中缀算术表达式求值算法，但此类算法仅适用于一些特殊领域，其代码量较传统RPN求值算法甚至更为笨重和复杂[7-8]，不具备轻量化的特征。

本文针对上述问题，以轻量化为目标，以表达式逆向拆分为方法，做了以下工作：

1）提出了一种无需进行RPN转换、无需人工栈辅助，可直接对中缀算术表达式求值的轻量化算法；

2）采用递归的设计思路，使本文算法的结构得到了进一步的精简；

3）对本文算法的正确性进行了证明；

4）将本文算法与传统RPN算法以及W3Eval算法进行了对比及实验测试。

通过以上工作，本文提出了一种全新轻量化的，适用于Web应用Browser端和嵌入式应用的中缀算术表达式求值算法。

2算法设计

2.1总体思想

定义1设a1、a2为算数，op为二元算术算符，则称形为a1 op a2的中缀算术表达式为最简中缀算术表达式，简称最简式。

引理1退去中缀算术表达式中的括号等价于重定义该括号中的算符。

证明设中缀算术表达式为：

对式（5）的求值与式（3）的求值相同，因此命题成立。证毕。

传统中缀算术表达式求值之所以要先转换为RPN，其原因是中缀算术表达式中的算符有不同的优先级，且可以使用括号来改变优先级，这个规则使用计算机直接处理是非常不便的。相对的，RPN中的算符没有优先级，也不存在括号，使用计算机处理时只需按照压入和弹出人工栈的顺序进行处理，因此比较简单直接。本文采用一种完全不同的思想，根据定理1，将中缀算术表达式按照算符优先级进行递归拆分，即以算符为拆分轴，分层次将中缀算术表达式拆分至定义1所述的最简式，然后由下向上逐层求值。显然，该方法正是手工对中缀算术表达式求值过程的一种逆向模拟。

对于一元算符，可通过添加特殊的左算数将其转换为相应的二元算符，例如-a可表示0-a，+a可表示为0+a，～a（按位取反）可表示为aa（按位与非）或aa（按位或非）等。本文为了论述简明，且不失一般性，仅考虑一元算符“+”和“-”的处理。

因此，本文算法的核心思想是以二元算符为拆分轴，对中缀算术表达式进行逆向拆分，即先拆分优先级低的算符，再拆分优先级高的算符，优先级相同的算符从右到左进行拆分。然后对已拆分的最简式由下向上逐层求值。显然，每次拆分的形式相同，规模在缩小，且有出口，满足递归算法的充要条件，而使用递归设计，可减少代码量，使本文算法进一步轻量化。

例1中缀算术表达式（1+2）*（3^4-（-5-6））+7的递归拆分求值过程。

解：其递归过程示意如图1，S1到S7表示7次递归调用，递归深度为5层。

综上所述，本文算法总体结构描述如下：

步骤1如果中缀算术表达式整体被括号包围，则退去括号。

步骤2在中缀算术表达式中查找优先级最低的算符作为拆分轴，同一优先级的算符以所处位置最右者作为拆分轴，括号内的算符视为优先级最高。

步骤3以查找得到的算符将中缀算术表达式拆分为左式a1、算符op和右式a2，即a1 op a2形式。

步骤4如果算符op为一元算符，则令左式a1为0。

步骤5如果左式a1或右式a2不为最简式，则对左式a1或右式a2分别递归执行步骤1到步骤5，即继续拆分；否则执行步骤6。

步骤6此时左式a1和右式a2均为算数，该中缀算术表达式已是最简式，可直接求值（递归出口），然后回退至上一层递归调用处。

2.2详细算法

根据2.1节的思路，可将本文算法分为3个子算法：1）退去整体包围中缀算术表达式的括号；2）在中缀算术表达式中查找优先级最低、最右且不在括号内的算符；3）拆分中缀算术表达并求值。

2.2.1退括号算法

如果原中缀算术表达式中包含有括号，则在拆分至相应层次时，该括号一定位于拆分后的中缀算术表达式的最外层，需将其退去，即拆分至该层时，括号所标识的优先级已通过拆分顺序所确立（参见2.2.2节）。

由于存在形如（a1 op1 a2） op2 （a3 op3 a4）的中缀算术表达式，因此退括号算法不能简单地通过判定输入中缀算术表达式的起始和结束位置是否为“（”和“）”字符，进而得出是否需要退括号的结论，而需要将输入的中缀算术表达式中的括号进行配对，只有配对过程在输入中缀算术表达式的末尾结束时，才可以退括号。

下文算法1、2和3中，入口参数均为字符串形式的中缀算术表达式。其中字符串的substr（m，n）方法返回该字符串中从第m个到第n个（含第m个和第n个）字符构成的子字符串；字符串的length属性返回该字符串的字符数量；通过索引器[i]可以访问字符串中的任意字符，索引从0开始；函数isNaN（s）返回s是否是一个算数（一般即为实数）。

算法1delBracket（ex），返回退去中缀算术表达式ex整体包围括号后的结果。

说明level用来记录未配对成功的括号层数；步骤5）为true则表示在最外层找到匹配括号或没有括号，然后通过步骤7）做进一步判断。

2.2.2算符查找算法

为了论述简单，本文所述算法仅选择了一些常用算符，其他算符可按照此规则添加，由于本文算法不使用文献[6]算法所采用的符号转置表，因此，所有算符均支持自定义或重定义[2-3]。算符及其优先级见表1。