简单 JS 算数表达式求值算法的实现探索

问题

在凤蝶业务中，开发者可以描述运营维护的数据结构，同时希望凤蝶提供描述这些数据结构之间的关系语法。比较常见的场景，有些配置项是在某个开关开启的时候才需要输入的，这里有两个字段的关联，一个是开关，另外一个是开关关联的配置项，关联关系也可能是多个字段相互作用。

这种关系使用 js 算数表达式来描述是最符合开发者思维了，比如 $.a === "foo" || $.b 这样当字段 a 等于 foo 或者 b 为 true 的时候，表达式为 true ，这时候可以显示这个字段。

这个需求我们可以使用函数描述

function evaluate(expr: string, context: object): any;

这里第一个参数是一个简单的 js 表达式，需要能够支持基本的算数、逻辑、比较运算，不需要支持复杂的函数运算。运算支持简单的变量和一些简单的数字、字符串。

如何实现这个运算过程呢？最简单的方式直接用 eval 或者 new Function，但这样意味着开发者可以写任意 js ，太不安全了。

需要有更安全的实现方案，下面首先来看看已有的一些实现方案。

已有方案

已有的实现主要分两种方案

1. 构造一个安全的运行环境运行
2. 使用 js 解析 js 表达式，然后执行

第一种，比如 natevw/evel ，自动生成一个 iframe ，在 iframe 中运行，然后返回结果。同样的 safe-eval，使用 node vm 运行。这些方法实现是可以的，但是整体太重了，而且安全性也不那么可靠。我需要的只是一个简单的表达式运算而已。

第二种方式，有人实现了 expr-eval，看例子 Parser.evaluate('6 * x', { x: 7 }) 还蛮符合需求的。功能很强大，支持大部分所有 js 运算符，还支持很多数学函数运算。

但是稍微有一些不好的是逻辑表达式用and or !，这样比较混乱了，最好全都使用 js 运算符。另外支持一堆的数学运算，对于我的需求是多余的。真正用 js 运算数学那肯定要被坑惨的，这个库更多的偏重数学运算，而我希望要的是一个简单的 js 表达式解析器，更注重的是逻辑运算。

已有的方案都不是很满意，那么尝试一下自己实现一个吧。算数表达式运算是一个比较古老的问题了，应该有不少已有的算法可用。

下面首先看看已有的算法

• Dijkstra’s two-stack algorithm
• Shunting-yard algorithm

Dijkstra’s two-stack algorithm

这个算法特别简单，分几个步骤

1. 初始化两个数组，values，operation，分别存值和运算符
2. 一次读取一个 token，然后判断

• 如果是数字 push 到 values
• 如果是运算符 push 到 operation
• 左括号，忽略
• 右括号，弹出一个运算符和两个值，运算后的结构 push 到 values

1. token 读取结束，返回 values 第一个值

举个简单例子 (1 + (2 * 3))

这种算法很简单，但是问题是必须通过括号把所有运算包裹起来，这不符合普通的书写表达式的方式。这种算法忽略了运算符优先级问题，所有的运算都通过括号来分割。

这种算法虽然不够好，可以基于这种思想，优化一下就可以支持完整的数学表达式了。

Shunting yard algorithm

Shunting yard 算法和前面提到的 Two Stack 类似，也是基于堆栈的方式来运算的，稍微改进一下即可。

Shunting yard 最终产物是一种叫做逆波兰表示法的数据结构。举个例子

1 + 2 * 3 最终转换为 1 2 3 * +，运算过程就可以转换为上面的 Two Stack 类似运算了。

依次 pop 出数据到 values 数组，遇到运算符从 values pop 两个值，运算，然后 push 回到 values 数组，最终运算结束，返回 values 第一个值。

上面的例子，运算过程就是 [1, 2, 3] ，到第四个字符，* ，这时候 pop 出 2 3，把运算结果 push 回去，[1, 6]。下一步遇到 + 运算符，同样运算即可。

那么现在问题转换为如何实现运算表达式转换为逆波兰表示法过程了，Shunting yard 就是这样一种算法。

还是以上面例子为例 1 + 2 * (3 - 4)

这样这个表达式的逆波兰表示法就是 1 2 3 4 - * + 了。递归过程只需要遵循几条原则

遇到运算符，按照以下情况处理

• 如果运算符优先级比 operations 最后一个运算符高或相等，直接 push 到 operations
• 如果更低，则先把 pop 一个出来，放到 values ，继续对比直到优先级不低为止

括号处理稍微有一些区别，遇到左括号直接 push ，后面遇到右括号的时候，依次把 pop 所有运算符到 values ，直到遇到左括号为止。

Wiki 上有一个图

具体实现代码可以参考 simple-evaluate/src/shunting-yard.ts。

算法整体过程还算简单，但是逆波兰表示法还是主要为数学表达式为主的，我们把逻辑运算符放进来也可以运算，优先级也是类似的。但是这种方式都是处理二元运算，对于逻辑运算中的 ! 非运算，和算数中的一元 - 负运算就无法处理了。

负运算也可以直接和数字结合为负数，但是遇到 12 + -(3 - $.a) 这种情况就无解了。

如果要彻底解决解决一元表达式和负号重载的问题，只能通过一个简单的解析器来处理了。下面来看看最终实现方案 simple-evaluate 是如何实现的。

Simple Evaluate

simple evaluate 是我实现的一个简单表达式解析器。前面用的是 Stack 来描述表达式，解析器一般使用树结构来描述。

对于表达式运算，一般都是二元的，可以用一个包含左右节点的 Node 结构描述

interface Node {
  left: Node | string;
  right: Node | string;
  operation: string;
};

比如 1 + 2 ，可以描述为 { operation: '+', left: 1, right: 2 } ，表达式继续增加，可以通过增加节点来描述，运算符优先级可以通过节点位置描述。

比如，1 + 2 3 ，需要增加一个 `{ operation: ‘‘, right: 3 }` 的节点，因为乘法优先级更高，那么新增的节点作为上一个节点的 right 节点。新节点的 left 节点为上一层节点的 right 。

如果新增节点运算符优先级比 root 节点更低或者想到，直接把当前 root 作为新节点的 left 节点。上面的例子，继续增加一个节点 1 + 2 * 3 - 4 ，那么最终语法数结构如下

得到这样的树结构结构后，运算就比较简单了，遍历树节点，运算从底层节点开始，依次往上收。一直到顶层节点，可以拿到最终结果了。

括号处理

上面依次读取 token 过程，没有考虑括号的场景。我们可以括号里面当初一个独立的 node ，那么括号里面的节点就会在节点的最底下了。

举个例子，1 * (2 + 3)，可以看做 1 * x，x 是 2 + 3。在解析步骤

1. 首先读取一个 left 节点 1
2. 读取运算符 *
3. 读取 rigit 节点

• 遇到做括号
• 依次读取，直到遇到右括号，得到节点 { left: 2, right: 3, operation: '+' }
• 返回 right 节点

每次遇到括号，一直解析到括号结束，形成一个大的 node 节点，这样所有解析过程可以看做没有括号了。

一元运算符

一元运算符包括非运算和负运算。因为负运算和减法基本一直，所以可以把负运算作为一个减法的节点，比如 -(1 * 3) * 2 ，可以转换为 (0 - (1 * 3)) * 2，也就是 -x 等于 (0 - x)，用括号括起来，这样保证负运算优先级最高。

减法和负运算的区别也很容易区分，如果 - 符号前面没有运算符，或者是其他运算符，那么就是一元负运算，其他情况都是减法运算。代码示例

// 3 > -12 or -12 + 10
if (token === '-' &&
  (OPERATION[this.prevToken()] > 0 || this.prevToken() === undefined)) {
  return { left: '0', operation: token, right: this.parseStatement(), grouped: true };
}

非运算，非运算很好处理，唯一的区别是只有一个 right 节点

if (token === '!') {
  return { left: null, operation: token, right: this.parseStatement() }
}

总结

最终，一个简单的 js 运算表达解析器 simple-evaluate 实现了。总共代码不到 300 行，非常简单。麻雀虽小五脏俱全，这个个小的解析也包含了完整 token 生成，语法树生成，语法树解析几个过程。这种思路继续扩展，可以实现更强大的语法结构。

对于最初的目标，这样的实现也是足够安全、简单了。Shunting yard 算法很优雅，比起语法树方式更代码量少了30%，如果能够支持一元表达式就更好了，不过我没想到如何处理。