Kotlin 高效解析数学表达式(支持函数)

源码:github gist
⚠️ 源码根据使用场景定制,为最大化效率没有使用抽象等结构,如需使用请酌情优化。

需求

由于项目需求,需要在低性能设备高频率地解析计算数学表达式,所以重量级的比如词法分析,语法分析,抽象语法树🌲三件套就不太合适了。(当然也不是不行,只是有点大材小用,而个人能力又有限,对于ANTLR调优之类不太擅长)

说起数学公式解析,当然离不开老朋友逆波兰表达式,也就是后缀表达式,他能忽略括号等优先级问题,按照顺序一一计算。本次也打算从这里入手,慢慢再加入其他一些特性。

先总结下需求:

  • 支持加减乘除与括号,以及括号嵌套。
  • 支持负数/负表达式以及连续负号。比如 1*-2=-2, 1*--2=2, 1*-(2+3)=-5
  • 支持固定的函数,以及函数与表达式的相互嵌套。比如 1+abs(-2-3)=6
  • 支持常量,例如 pi, e

因为使用场景频率较高,所以解析过程中不要使用临时对象,如果非要使用要建立对象池避免 GC 压力过大。

基础实现

首先是最基本的,中缀转后缀表达式。再捋一下基本思想:

准备一个 OP 栈存放操作符。从头开始扫描字符串,遇到数字则直接输出(暂且称之为输出),否则假设 OP 栈顶元素为 A,扫描到的标识符为 B:

  1. 若 B 是右括号,则将栈中元素依次出栈输出,直到左括号。括号出栈不输出。
  2. 若 A 为空 或 A 是左括号 或 B 是左括号,则 B 入栈。
  3. 若 B 优先级大于 A,则 B 入栈。
  4. 否则 A 出栈输出并循环,直到满足上述条件之一。

扫描结束后将 OP 元素全部出栈输出,得到完整的后缀表达式。

按照上述算法,表达式 2*(3+4) 转换后输出为 234+*。然后只需要按顺序扫描输出,遇到数字入栈,遇到运算符出栈操作数,然后将计算结果再入栈,最后栈中唯一元素就是答案了。

不难看出这种方法相当于遍历了两遍。其实我们可以再准备一个表达式 exp 栈,在输出的过程中直接入 exp,如果遇到操作符,则进行计算再将结果入 exp。这样只需要遍历一遍就能得到答案。

💡 Tips

复盘 B 入栈的条件,可以发现栈中可能存在的元素包含运算符与左括号。右括号永远不会入栈。也就是说 A 可能的值为运算符与左括号。反直觉地,我们只需要将左括号(定义为优先级最低,即可将括号也作为运算符看待一并计入优先级比较,避免一小段特殊逻辑代码。
但请注意 AB 都是左括号时,虽然优先级相等,但是 B 应当入栈而不是 A 出栈。 因此相比于直接定义 int 优先级,我更偏向于定义一个二维 bool 数组,用于快捷查找任意两个符号比较,应当出栈还是入栈。

到此为止已经解决了四则运算与括号的问题。

额外需求

函数

我的基本思想就是将函数作为一个特殊的操作符(和加号一样)处理。那么就会产生几个问题:

  1. 函数的操作数都在操作符的后面。
  2. 函数的优先级如何定义。
  3. 参数的分隔符,怎么办。
  4. 函数什么时候可以出栈?

第一个问题其实不影响什么。我们思考一下常规减号-的处理流程。首先将左边操作数输出,然后将减号入栈,最后输出右边操作数。对比一下函数:首先将函数(特殊操作符)入栈,然后将参数依次输出(当作操作数)。显然,两者最终的输出以及栈是一样的,即:操作数从左至右依次输出,操作符入栈。因此操作数与操作符的相对位置并不重要。

问题二则更简单,显然函数的优先级应该是最高,遇到直接入栈就完事了,但是两个函数之间该如何比较?其实这种情况根本不可能发生,因为函数后必定紧跟着一个左括号(,一旦左括号入栈,则后续的操作符必定直接入栈。因此函数入栈时,栈顶不可能也是函数。

至于参数分隔符,我将其视为一个表达式的结束。因为每一个参数都可能是一个嵌套的表达式,我们知道函数在执行前必须先计算出所有参数的值。如此一来,参数分隔符,和右括号)一样不需要入栈,同时要弹出栈中的其他元素,直到遇左括号(但是不要把左括号出栈,因为左括号和函数是一体的,分隔符只是参数的结束,并不是函数的结束。

最后,既然函数的优先级最高,那么什么时候才能轮到它出栈呢?显而易见肯定不能等最后集中出栈,否则就成了薛定谔的参数了。之前讨论到函数的操作数都在右边,换句话说,当操作数全部输出时,就应该立即让函数出栈。答案呼之欲出:当函数结束的时候函数本身应该出栈,而右括号)就是函数的结束符。这个符号在基础章节已经被定义过了,遇到右括号,我们要循环出栈直到左括号。此时应该加上一条:左括号出栈后如果栈顶元素是函数,那么将其出栈并输出。 这就能保证在后缀表达式中函数可以紧挨着它的所有参数。

负号

负号可以视为一个单目运算符,为了区别于减号(-),这里用波浪线(~)指代负号。那么只需解决两个问题:

  1. 什么情况下减号需要视为负号?
  2. 负号优先级如何?

先来解决简单的,负号优先级应该是最高(除了函数之外)。因为负号总是和后面的数或表达式结合,不受前方运算符的影响。比如 1*~2=2

下面为了解决问题一,我罗列了整个表达式中所有可能的数据类型,然后一一判断此时减号应该如何解释。

前方符号 语义
左括号 ( 负号
其他运算符 +-x/ 负号
数字 减号
右括号) 额外判断

右括号等情况稍微复杂,正常来说前面是个表达式,那么后边应该为减号。但是我们的语法允许空括号 (),这种表达式经过解析后其实什么都没有。所以遇到右括号)得额外判断 exp 栈,如果栈不为空且栈顶是数字则为负号~,否则为减号-

这样我们就需要用一个变量来记录上一个符号的类型,以便判断语义时使用。连续负号情况不需要额外处理。

常量

常量可以说是最简单的额外需求了,简单到甚至不需要额外处理。读取到常量后直接视为数字处理就行了。

解析问题

最后来说一下解析问题。因为一个 Token 可能由多个字符组成,例如数字 12.3 有4个字符,函数 abs 有3个字符。所以本质上我们要手写一个定制的词法解析器,因为语法相对简单,所以难度不算太大。考虑到使用场景,这里的宗旨是整个字符串只扫描一遍,不回退不预读。 容错就不过多考虑了,最外层之间 try 一下。

首先是最简单的常量与函数解析。先来明确下他们的语法定义:以字母开头,只能包含字母数字与下划线_,大小写敏感。我们就可以提炼出下面的特征:(为了便于描述,这里把常量和函数名统称为标识符id)

  • 遇到的第一个字母一定是 id 的开头。
  • 之后遇到的第一个非字母数字下划线一定表示 id 结束。

那么算法就水到渠成了。为了提高 id 拼凑效率,我在外部定义了一个 StringBuilder 用来拼接。当然,还有其他方案,例如记录 id 首末 index 然后一次性提取等。


接下来是识别数字,包括小数。数字可以包含数字和小数点.。类似的,遇到的一个数字或小数点.表示一个数字的开始,之后遇到的第一个非数字且非小数点表示数字的结束。

可以用上面 id 的方法来记录数字字符串,最后一次性地调用 kotlin 标准库函数转换为 double 类型。不过这里扣个字眼:标准库转换的时候必然要扫描字符串,而我们已经扫描一遍了,所以做了重复工作。为此,我定义一个 double 变量 num=0,以及一个表示小数位数的 double fraction=1。扫描到数字后将 num *10 然后加上当前数字。若在小数点之后,则先把 fraction / 10,然后乘以当前数字最后加到 num 上。

如此一来,在扫描的同时我们就实现了字符串到数字类型的转换。

发表评论

邮箱地址不会被公开。 必填项已用*标注