语法解析一个非常重要的功能就是构建一个树形数据结构，语法解析树。

如图，公式A + B * C解析结果，将公式解析成最小的操作符、操作数，本文以二元操作符加减乘除为例。
A+B*C

由上图推断语法树节点的数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
public static class Exp {
    /** 1.常量值  2.操作符  3.变量值 4.临时存储操作符(加减乘除) */
    int type;
    /** type=1常量值 */
    double value;
    /** type=3 变量名 */
    String varName;
    // type=2 操作符 加减乘除
    char opt;
    // 操作值表达式对象 (常量, 指标值变量, 表达式)
    Exp[] values;
}

解析 5 - ((A + B) * 2 / C) 后的解析树如下图

A+B*C

完整代码实现 Gitee

核心 Java 代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// 判断字符串是否包含加减乘除括号
public static final Pattern EXP_PATTERN = Pattern.compile("^.*?[()*/+\\-].*$");

// 特殊运算符
public static final Set<Character> TOKENS = ImmutableSet.of('(', ')', '*', '/', '+', '-');

private static Exp parseExp(int callTimes, String exp) {
    if (callTimes > 1000) { // 防止死递归
        throw new IllegalStateException("表达式递归解析次数超过1000次");
    }

    exp = exp.trim();
    if (StringUtils.isEmpty(exp)) {
        throw new IllegalStateException("表达式有误请检查");
    }
    // 表达式为常量值 12.31
    if (NumberUtils.isParsable(exp)) {
        Exp expression = new Exp();
        expression.type = 1;
        expression.value = NumberUtils.createDouble(exp);
        expression.segment = exp;
        return expression;
    }

    // 表达式不包含运算符，表达式为变量 (A, B, C)
    if (!EXP_PATTERN.matcher(exp).matches()) {
        Exp expression = new Exp();
        expression.type = 3;
        expression.varName = exp;
        expression.segment = exp;
        return expression;
    }

    // 表达式为计算公式
    List<Exp> segments = new ArrayList<>();

    // begin操作符左边的常量或变量名
    for (int i = 0, len = exp.length(), begin = i; i < len; i++) {
        char c = exp.charAt(i);
        if (!TOKENS.contains(c)) {
            // 最后一个字符，且exp不为常量或变量，作为表达式片段截取
            if (i == len - 1) {
                if (begin > 0 && begin <= i) {
                    segments.add(parseExp(callTimes + 1, exp.substring(begin, len)));
                }
            }
            continue;
        }

        // 字符为操作符

        // 左括号:有表达式片段
        if ('(' == c) {
            // 找右括号 )
            int closeIdx = findCloseIdx(exp, i + 1, '(', ')');
            if (closeIdx < 0) {
                throw new IllegalStateException(String.format("无右括号对应第%d个字符的左括号", i));
            }
            segments.add(parseExp(callTimes + 1, exp.substring(i + 1, closeIdx)));
            i = closeIdx;
            begin = i + 1;
            continue;
        }
        if (')' == c) {
            throw new IllegalStateException(String.format("无左括号对应第%d个字符的右括号", i));
        }

        // 加减乘除操作符
        // 操作符左边值
        if (begin < i) {
            String valueLeft = exp.substring(begin, i);
            if (StringUtils.isNotEmpty(valueLeft.trim())) {
                segments.add(parseExp(callTimes + 1, valueLeft));
            }
        }
        // 操作符
        Exp expS = new Exp();
        expS.type = 4;
        expS.opt = c;
        segments.add(expS);

        begin = i + 1;
    }
    return combineExpSegments(exp, segments);
}