震惊？编译器居然不会小学生都会的加减乘除？（解析数学表达式）

站长

2024年06月18日 14:53 · 阅读数 52

声明：本文代码使用java-JDK8，并且已给出全部代码，可直接执行

前言

我是标题党，编译器当然能识别+-*/但是遇到字符串的公式就需要我们自己解析。

今天刚好遇到一个需求，用户输入任意公式，返回计算结果，于是上网找了几个方案

例子:

工资 = "出勤天数 * 基本工资/当月工作日 + 绩效奖金 - 迟到早退扣钱"

利用JS-Engine

这个是相当不推荐了

缺点：

兼容性问题，js engine在未来的jdk可能不再支持
性能差
输入变量麻烦，需要额外输入js的赋值代码
精度丢失，如 0.1 + 0.2 = 0.30000000000000004
需要自己转换类型，结果有可能是Integer，有可能是Double看你的公式。

代码如下

<dependency>
  <groupId>org.springframework</groupId>
  <artifactId>spring-expression</artifactId>
  <version>5.3.21</version>
</dependency>

public static void main(String[] args) throws ScriptException {
    ScriptEngineManager manager = new ScriptEngineManager();
    ScriptEngine engine = manager.getEngineByName("javascript");
    Long start = System.currentTimeMillis();
    for (int i = 0; i < 1000000; i++) {
        Double hour = (Double) engine.eval("a = 5 ; b = 10 ; c = a * b + 3 / 5");
    }
    Long consumeSecond = (System.currentTimeMillis() - start) ; // 大约5秒
    System.out.println(consumeSecond);
}

SpringEl

大家做项目应该也用spring吧，用的话它自带了一个表达式语言，很容易实现我们的需求

优点：

灵活
功能强大，可以使用调用代码中的任意静态方法，如，Math.max , Math.min。
性能优秀

缺点：

表达式的表达较为繁琐
- 变量一般需要加前缀#
- 使用非根对象的方法则需要补全包路径，如： T(java.lang.Math).max(1,5)
依然有精度丢失问题 , 如 0.1 + 0.2 = 0.30000000000000004

public static void main(String[] args) throws Exception {
    ExpressionParser parser = new SpelExpressionParser();
    StandardEvaluationContext ctx = new StandardEvaluationContext();

    Long start = System.currentTimeMillis();
    Expression expression = parser.parseExpression("#a * #b+ 3.0 / 5");
    for (int i = 0; i < 1000000; i++) {
        ctx.setVariable("a", 5);
        ctx.setVariable("b", 10);
        Double value = expression.getValue(ctx, Double.class);
    }
    Long consumeSecond = (System.currentTimeMillis() - start); // 0.5秒左右
    System.out.println(consumeSecond);
}

使用第三方包

EvalEx，这个应该是功能比较强大的包了，甚至支持逻辑运算。有兴趣自行了解

缺点：

需要额外引用第三方包
额外的学习成本
性能一般，下面的例子居然用了6秒，难道我的测试方法有问题？⊙﹏⊙∥

这里贴一下例子

    <dependency>
      <groupId>com.ezylang</groupId>
      <artifactId>EvalEx</artifactId>
      <version>3.2.0</version>
    </dependency>

public static void main(String[] args) throws Exception {

    Long start = System.currentTimeMillis();
    Expression expression = new Expression(" a * b + 3 / 5");
    for (int i = 0; i < 1000000; i++) {
        EvaluationValue result = expression
                .with("a", 5)
                .with("b", 10).evaluate();
        result.getNumberValue();
    }
    Long consumeSecond = (System.currentTimeMillis() - start); // 6秒左右
    System.out.println(consumeSecond);

}

自行解析

我个人比较喜欢折腾，因此也选用的这种方式。这里分享一个解析数学表达式的方法，我这里使用的是递归下降解析器（recursive descent parser）的解析方法，这是一种自顶向下的解析方法，实际上编辑器分析代码的时候也是用这种方法。

优点

极其灵活
性能优秀
可以解决精度丢失问题

缺点

要自己写解析代码

EBNF

首先介绍一下EBNF(扩展巴科斯范式 , Extended Backus–Naur Form) , 它是一种表达形式语言文法的代码。有点类似于正则表达式

简单举几个例子

# 表示字母 
letter = 'a'|'b'|'c'|'d'|'e'|'f'|'g'|'h'|'i'|'j'|'k'|'l'|'m'|'n'|'o'|'p'|'q'|'r'|'s'|'t'|'u'|'v'|'w'|'x'|'y'|'z'|'A'|'B'|'C'|'D'|'E'|'F'|'G'|'H'|'I'|'J'|'K'|'L'|'M'|'N'|'O'|'P'|'Q'|'R'|'S'|'T'|'U'|'V'|'W'|'X'|'Y'|'Z';
# 等同于letter = 'a' ... 'z' | 'A' ... 'Z' ;

# 表示数字 1-9
nonzero_digit = '1'...'9' ;

# 表示数字 0-9
digit =  '0' | nonzero_digit ;
# 表示单词
word = (letter | '_') { '_' | letter | digit } ;
# 表示整数
int = '0' | ['+'|'-'] nonzero_digit { digit } ;

| 表示或
... 表示范围，可用于表示连续的字符
{} 花括号表示出现0次或多次，类似正则的*
'' 表示字符串
[] 表示可选，类似正则的?

基本运算公式的EBNF

通过上面的例子，大家应该大概明白ebnf的机制，这里我们写一下包含+-*/运算表达式的ebnf

digit = '0'...'9' ;
nonzero_digit = '1'...'9';
factor = nonzero_digit ['.' {digit} ] ;  #这里表示小数
term = factor { ('*'|'/') factor } ; # 解析乘法
expression = term { ('+'|'-') term } ; # 解析加法

这里大家应该可以发现，优先级越高的运算符需要优先计算；+-优先级最低，因此放在最外层的expression中。在日常生活的口算中，我们应该也会把term中的*/优先计算，再做+-运算

如：

res = 1 + 2 * 3 + 4 * 5     \
    =  1 + 6 + 20

# 这里的 1，6，20 相当于term
# 2，3，4 ，5 相当于factor

代码实现

版本一

到这里我们得出了运算表达式的ebnf，接下来我们来实现一个简单的解析器

public class SimpleExpressionParser {

    SimpleExpressionParser() {
    }

    int ch, pos = -1;
    String str;
    
    /**
     * 遍历输入公式，从左到右逐个遍历
     */
    void nextChar() {
        ch = (++pos < str.length()) ? str.charAt(pos) : -1;
    }
    
    /**
     * 判断当前字符是否符合预期，如果是空格跳到下一个继续判断
     */
    boolean expect(char expectChar) {
        while (ch == ' ') nextChar();
        if (ch == expectChar) {
            nextChar();
            return true;
        }
        return false;
    }

    public static BigDecimal parse(String str) {
        SimpleExpressionParser parser = new SimpleExpressionParser();
        parser.str = str;
        parser.nextChar();
        return parser.parseExpression();
    }

    /**
     * expression = term { ('+'|'-') term } ;
     */
    BigDecimal parseExpression() {
        BigDecimal x = parseTerm();
        for (; ; ) {
            if (expect('+')) x = x.add(parseTerm());
            else if (expect('-')) x = x.subtract(parseTerm());
            else return x;
        }
    }

    /**
     * term = factor { ('*'|'/') factor } ;
     */
    BigDecimal parseTerm() {
        BigDecimal x = parseFactor();
        for (; ; ) {
            if (expect('*')) x = x.multiply(parseFactor());
            else if (expect('/')) x = x.divide(parseFactor(), 4, BigDecimal.ROUND_HALF_UP); //保留4位小数
            else return x;
        }
    }

    /**
     * factor = nonzero_digit ['.' {digit} ] ;
     */
    BigDecimal parseFactor() {
        BigDecimal x;
        // 跳过空格
        while (ch == ' ') nextChar();

        int startPos = this.pos;
        if ('0' <= ch && ch <= '9' || ch == '.') {
            while ('0' <= ch && ch <= '9' || ch == '.') nextChar();
            x = new BigDecimal(str.substring(startPos, this.pos));
        } else {
            throw new RuntimeException("Unexpected: " + (char) ch);
        }
        return x;
    }

    /**
     * 测试
     */
    public static void main(String[] args) {
        System.out.println(SimpleExpressionParser.parse(" 1 + 2*3-4.5/5"));
    }
}

结合ebnf范式去实现代码，我们应该可以很清晰的看到每一步要做什么。

版本二

上面的代码有些问题，比如没有处理括号，没有处理负数，这些问题，这里我们来改进一下

ebnf范式

先按自己的理解写下ebnf范式

digit = '0'...'9' ;
letter = 'a'...'z' | 'A'...'Z';
nonzero_digit = '1'...'9';
variable = (letter | '_') { '_' | letter | digit } ; #这里表示变量
num = nonzero_digit ['.' {digit} ]

factor = ['+'|'-'] ( variable | num | '(' expression ')' ) ;
term = factor { ('*'|'/') factor } ;
expression = term { ('+'|'-') term } ;

代码实现

鉴于我们只改了factor的范式，因此我们只需要改一下parseFactor()方法即可

代码如下

public class SimpleExpressionParser1 extends SimpleExpressionParser {

    Map<String, BigDecimal> map;

    public static BigDecimal parse(String str, Map<String, BigDecimal> map) {
        SimpleExpressionParser1 parser = new SimpleExpressionParser1();
        parser.str = str;
        parser.map = map;
        parser.nextChar();
        return parser.parseExpression();
    }

    private static boolean isLetter(int ch) {
        return 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z';
    }

    private static boolean isNum(int ch) {
        return '0' <= ch && ch <= '9';
    }

    /**
     * factor = ['+'|'-'] ( variable | num | '(' expression ')' ) ;
     */
    BigDecimal parseFactor() {
        if (expect('+')) return parseFactor();
        if (expect('-')) return parseFactor().negate();

        BigDecimal x;
        int startPos = this.pos;
        if (expect('(')) {
            x = parseExpression();
            if (!expect(')')) throw new RuntimeException("Expected ')'");
        } else if (isNum(ch) || ch == '.') { //解析数字
            while (isNum(ch) || ch == '.') nextChar();
            x = new BigDecimal(str.substring(startPos, this.pos));
        } else if (isLetter(ch) || ch == '_') {  // 解析变量
            while (isLetter(ch) || isNum(ch) || ch == '_') nextChar();
            String var = str.substring(startPos, this.pos);
            x = map.get(var);
            if (x == null) {
                throw new RuntimeException("Unknown variable: " + var);
            }
        } else {
            throw new RuntimeException("Unexpected: " + (char) ch);
        }
        return x;
    }

    /**
     * 测试代码
     */
    public static void main(String[] args) {
        // 预期值， 5
        System.out.println(SimpleExpressionParser1.parse("-a * ( a * -(-5+10*a))", new HashMap<>() {{
            put("a", new BigDecimal(1));
        }}));
        // 预期值，11
        System.out.println(SimpleExpressionParser1.parse("a * -b + c - (-d) * 3", new HashMap<>() {{
            put("a", new BigDecimal(1));
            put("b", new BigDecimal(2));
            put("c", new BigDecimal(3));
            put("d", new BigDecimal(-4));
        }}));
        
        Long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            SimpleExpressionParser1.parse("a * b + 3 / 5", new HashMap<>() {{
                put("a", new BigDecimal(5));
                put("b", new BigDecimal(10));
            }});
        }
        Long consumeSecond = (System.currentTimeMillis() - start);
        System.out.println(consumeSecond); // 0.3秒左右
    }
}

到目前为止我们实现了一个简单的表达式解析器。有兴趣可以再自行实现一下位运算(>>,<<)，逻辑运算（&&,||,!），三目运算符(?:)，函数调用（如求和，求最大/小值，开方），关系运算符（>,<,=）等。

可以尝试实现解析： a > b ? max(1,2,3,4*(5+3)%2,min(7,sqrt(5))) : 20

参考资料

[1] [维基百科：递归下降解析器](zh.wikipedia.org/wiki/%E9%80…
[2] [How to evaluate a math expression given in string form?] stackoverflow.com/questions/3…
[3] [巴科斯範式(BNF/EBNF/ABNF)] hackmd.io/@ShenTengTu…
[4] [The language of languages] matt.might.net/articles/gr…
[5] [BNF Syntax Validator and Formatter] www.icosaedro.it/bnf_chk/#eb…
[6] [EBNF: A Notation to Describe Syntax] ics.uci.edu/~pattis/ICS…

转载自:https://juejin.cn/post/7380771735681957907