阅读 77

算法应用之自定义公式计算

实现效果

实现代码:github.com/winniecjy/f…
demo:winniecjy.github.io/formula-cal…

demo

业务背景

最近的业务涉及到了很多数据的计算,数据库提供了一些基础数据,基于这些数据和公式运算才可以得出最终的目标数据。
在目标数据量较少的前提下简单粗暴的计算就可以实现功能了,随着目标数据越来越多样,涉及到越来越多的基础数据,问题就随之而来了:

  • 基础数据可能来源于不同的数据表不同字段。
  • 公式只是基本的四则运算但是数量较多,而且后续可能会有所增减。

这些问题导致代码越来越长,可读性降低,而且后续修改成本越来越大。如果有别的同学要介入这个项目,光找公式具体在哪里进行计算就要花老半天。这个功能很容易实现,但是要随着公式数量增加和使用到的字段增多,代码就会越来越丑陋。
最终方案是:将公式作为配置项抽离出来,方便后续增加/修改。基于固定格式的公式配置来进行运算得出目标结果

四则运算实现

要对公式进行运算,首先需要实现基础的四则运算(包含符号()+-*/),用于解析一个字符串的计算式子(如:'(7+5)/3-1')。算法思路如下:

第一步:中缀表达式转后缀表达式

中缀表达式是利于人理解的表达方式,而后缀表达式更方便计算机的运算。所以首先将中缀表达式转换成后缀表达式。这个过程需要一个辅助处理的栈,从左到右扫描表达式里的每一个字符,执行以下操作:

  • 为数字,直接添加到后缀表达式末尾
  • 为+-*/运算符,弹出所有优先级大于或者等于该运算符的辅助栈顶元素到后缀表达式中,然后将该运算符入栈
  • 为左括号(,直接入栈
  • 为右括号),弹出栈顶元素到后缀表达式中,直到匹配到第一个左括号,括号不输出到后缀表达式

遍历完成后,将辅助栈中的元素输出,则得到后缀表达式。
说明:操作符优先级为:() < +- < */
以A*(B-C)/D为例,处理过程如下:

当前字符 后缀表达式 辅助栈
A A
* A *
( A *(
B AB *(
- AB *(-
C ABC *(-
) ABC- *
/ ABC-* /
D ABC-*D /
ABC-*D/
function infixToPostfix(infix, postfix) {
    let postfixHelper = Stack()
    for (let i=0; i<infix.length; i++) {
        let c = infix[i]
        if (!isOper(c)) { // 处理操作数
            let operands = ""
            while (i<infix.length && !isOper(infix[i])) {
                operands += infix[i++]
            }
            postfix.push(operands)
        } else { // 处理操作符做出处理
            handlerSymbol(c, postfixHelper, postfix)
        }
    }
    // 如果输入结束,将栈内元素全部弹出,加入后缀表达式中
    while (!postfixHelper.empty()) {
        let c = postfixHelper.top()
        postfix.push(c)
        postfixHelper.pop()
    }
}
复制代码

第二步:计算后缀表达式

计算后缀表达式,同样需要一个辅助处理的栈,从左到右遍历字符,遇到操作数压入辅助栈中;遇到操作符则从栈顶取出两个元素,第一个为右运算数,第二个为左运算数(注意这个顺序在除法中是结果相关的)。运算后的结果入栈。遍历完成后,辅助栈顶的元素则为所求。

function calcPostFix(postfix, data) {
  let helperStack = Stack()
  for (let i=0; i<postfix.length; i++) {
    let c = postfix[i]
    // 如果是操作数,压入栈中
    if (!isOper(c)) {
        let op = formatData(c, data) // 根据公式规则获取具体数据
        helperStack.push(op)
    } else {
      // 如果是操作符,从栈中弹出元素进行计算
      let op1 = helperStack.top()
      helperStack.pop()
      let op2 = helperStack.top()
      helperStack.pop()
      if (op1 === null || op2 === null) {
        helperStack.push(null)
      } else {
        switch (c) {
          case "+":
            helperStack.push(op2 + op1)
            break
          case "-":
            helperStack.push(op2 - op1)
            break
          case "*":
            helperStack.push(op2 * op1)
            break
          case "/":
            helperStack.push(op2 / op1) // 注意是op2(op)op1而不是op1(op)op2
            break
        }
      }
    }
  }
  return helperStack.top()
}
复制代码

公式的配置规则

实现了四则运算后,我们的主体功能已经基本完成只差临门一脚了。细心的同学会发现,在计算后缀表达式的时候,操作数入栈之前先使用formData构造数据,我们的公式数据匹配就在这里实现。
目前比较简单的匹配思路是以[数据表名称]_[字段名]为固定格式,入参data格式为:

const data  = {
    [数据表名称]: {
        [字段1]: 123,
        [字段2]: 456,
        ...
    }
}
复制代码

通过正则匹配,可以获取数据表名称和字段名,从data中获取到正确操作数。

总结

关于扩展

目前该功能只是后台简单应用,可以保证公式合法性。后续可能将该功能可暴露给业务使用者,让业务使用者可以自定义获取想要的数据和公式。
如果后续有需求,需要将这个简陋的功能再包装一层,保证公式的合法性,同时需要考虑数据安全性问题。

关于eval

以目前的公式配置原则,直接通过db1.field1-db2.field2的格式,以eval计算字符串也可以得出结果。基于以下的考虑没有使用:

  • eval是一个比较危险的函数,该功能后续考虑开放给用户,不建议使用。
  • 目前的计算规则比较简单,因为数据表之间有同一个关键字段进行匹配,确保返回数据只有一条,后续如有其他变动,目前正则的形式扩展性更好。