前文请查看:从零开始撸一个可扩展函数的数学公式解析轮子(第1部分)

3. 实现语法树转换

在令牌流的实现中我们讨论了对公式的基本验证,但是对于复杂逻辑的验证,光令牌流则并不能满足需求。比如,我们想要验证多层函数在令牌流层面上实现就很不舒服。所以我们还需要在这之上进行语法树解析。

3.1. 实现原理

首先由于我们需求并不需要实现平衡树,所以只需要实现一个多叉树即可。下面举几个从令牌流解析成树形结构栗子:

比如公式:a+b*30-abs(a-b, c, count(d))
转换为令牌流为(以|分割令牌字符):

a|+|b|*|30|-|abs(|a|-|b|,|c|,|count(|d|)|)

注意这里的函数部分

而我们把令牌流转换为树状图时,需要转换为类似的树形结构

           -
     *              abs
  +     30    -      c     count
a   b       a   b        d

转换逻辑是从左至右读取令牌,每读取一个按照逻辑进行树的插入或者变换(稍后我们会说明该逻辑)。最终形成一个多叉的树状结构。通过最上的根节点往下进行遍历,我们就可以计算出最终的结果了(验证也是该道理)。

可以试着自己解析几个公式熟悉一下

3.2. 实现逻辑

在该部分,我们会从某些特殊公式的令牌节点开始说明变换和插入的逻辑

后文会提及最后根节点概念,作为标识下次应该开始的位置

3.2.1. 直接插入

当令牌类型为TYPE_OPERAND(数字或变量,如1a)或TYPE_OP_PRE(前置操作符,如-)时,我们需要直接往下插入节点(同时更新一下最后根节点)。

如公式1+1中,当在解析+后的1时,语法树情况为:

   +  <-- 最后根节点
1

往下插入变为

   +
1    1 <-- 最后根节点

如公式3*-1中,当在解析*后的-时,语法树情况为:

   *   <-- 最后根节点
3

往下插入变为

   *
3    -  <-- 最后根节点

进一步处理变为

   *
3     -
   1    <-- 最后根节点

3.2.2. 操作符的变换与回滚

当令牌类型为TYPE_OP_IN(中置操作符,如+)或TYPE_OP_POST(后置操作符,如%)时,我们需要处理两种不同情况。

  1. 前一位为顶点情况

如公式1+1中,第一个1为顶点,则应该直接变换两个的位置。

  1. 非顶点情况
    当为非顶点时,我们需要往上回滚,直到一个小于等于当前的符号优先级的符号位置,然后该位置进行变换(这里需要注意回滚顶点的处理)。符号优先级定义如下:
符号 优先级
逻辑符号(如>=) 1
+ 1
- 2
* 3
/ 3
^ 4
% 5
其余 0

例如公式1-5^3+4,当到^符号时,语法树为:

  +
1   5  <-- 最后根节点

此时^符号以5为起始,往上查询到最近符号为-,由于优先级^较高,则停止,直接和5进行变换,转换为

   -
1     ^  <-- 最后根节点
   5

继续到+时,语法树为:

   -
1     ^
   5    3  <-- 最后根节点

此时以3开始往上查找,发现^优先级高,继续查找,发现-优先级高,继续查找到根级直接进行变换,形成:

      +  <-- 最后根节点
   -
1     ^
   5    3

最终变为

      +
   -      4  <-- 最后根节点
1     ^
   5    3

3.2.3. 函数/子表达式/集合的插入与回滚

当令牌类型为TYPE_FUNCTION(函数,如abc())、TYPE_SUBEXPR(子表达式,如())、TYPE_SET(集合,如{测试,测试2})时,我们需要区分开始和结束,用以进行内嵌操作。

  1. 如果是起始,则直接向下插入(同3.2.1)。

如公式1+abc(123),当到abc(之后时,为:

  +
1  abc <-- 最后根节点
  1. 如果是结束,则回滚到最近一个起始节点

如公式1+abc((3+a), count(b)),当到第一个结束符(a))时,语法树为

   +
1      abc
     (
   +
 3   a  <-- 最后根节点

经过回滚后,变为

   +
1      abc
     (  <-- 最后根节点
   +
 3   a

3.2.4. 参数标识符

当令牌类型为TYPE_ARGUMENT(参数时,如,),将会回滚到最近一个函数起始,如上面的公式继续解析会变为:

   +
1      abc <-- 最后根节点
     (
   +
 3   a

3.3. 使用

经过解析后,我们生成了一个如下形式的语法树结构:

export interface INodeItem {
    token: ITokenItem; // 节点信息
    children: INodeItem[]; // 子节点信息
}

接下来就可以通过遍历该语法树愉快的进行检测和处理了。

源码地址

最后多谢阅读,希望能有帮助