为运算表达式设计优先级为什么可以用分治？如何避免重复计算？

简化版

表达式不同加括号方式可以按每个运算符切分：把运算符左边和右边分别递归求出所有可能结果，再两两组合。数字片段是递归出口。因为同一子表达式会被多次计算，应加记忆化缓存，key 可以是子串或区间 [l,r]。

详细版

表达式 2*3-4*5 的不同括号方式，本质是选择“最后执行哪个运算符”。如果最后执行 -，左边是 2*3 的所有结果，右边是 4*5 的所有结果，组合后得到一种结果。枚举每个运算符作为最后合并点，就覆盖所有二叉表达式树。

递归函数 solve(expr) 返回当前子表达式所有可能结果。扫描子串，遇到 + - * 就切成左右两段，递归求 leftResults 和 rightResults，再按当前运算符两两计算。若扫描不到运算符，说明当前子串是数字，直接返回该数字。

没有缓存时，像 3-4*5 这样的子表达式可能被多个切分重复求解。加 Map<String, List<Integer>> memo 后，每个子表达式只计算一次。

完整版教学

一、为什么“加括号”可以转成“选择最后一个运算符”

任何完整加括号的表达式，最外层一定对应某个最后执行的运算符。比如 (2*(3-4))*5 最后执行的是最外层 *；(2*3)-(4*5) 最后执行的是中间的 -。这个最后运算符把表达式切成左子表达式和右子表达式。

因此我们可以反过来枚举：假设某个运算符是最后执行的，把它左边所有结果和右边所有结果组合起来。枚举所有运算符，就覆盖所有可能的括号结构。

2 * 3 - 4 * 5
    ^
若 '-' 最后执行：
左: 2*3 -> [6]
右: 4*5 -> [20]
结果: 6-20 = -14

二、分治函数返回什么

分治函数不能只返回一个值，因为同一个子表达式可能有多种加括号结果。它应该返回“当前区间内所有可能计算结果”的列表。

例如 solve("2*3-4") 有两种结果：(2*3)-4 = 2，2*(3-4) = -2，所以返回 [2, -2]。上层拿到这个列表后，会和右侧结果继续做笛卡尔积组合。

记忆钩子：表达式分治不是求一个最优值，而是求一个“结果集合”；上层负责把左右集合两两合并。

三、递归出口是纯数字片段

当扫描一个子串时，如果里面没有运算符，说明它只是一个数字，比如 "12"。这就是递归出口，返回 [12]。如果漏掉这个出口，递归无法停下；如果把每个字符都当数字，会错误处理多位数。

子串	是否继续切分	返回
`"2"`	否	`[2]`
`"12"`	否	`[12]`
`"3-4"`	是	`[-1]`
`"2*3-4"`	是	`[2,-2]`

多位数处理是常见坑，尤其在手写解析时不能只用 char - '0'。

四、代码模板

下面用子串作为缓存 key。若追求性能，也可以先 token 化，再用 [l,r] 区间做 key，避免频繁创建子串。

Map<String, List<Integer>> memo = new HashMap<>();

List<Integer> diffWaysToCompute(String expression) {
    if (memo.containsKey(expression)) return memo.get(expression);
    List<Integer> res = new ArrayList<>();

    for (int i = 0; i < expression.length(); i++) {
        char ch = expression.charAt(i);
        if (ch == '+' || ch == '-' || ch == '*') {
            List<Integer> left = diffWaysToCompute(expression.substring(0, i));
            List<Integer> right = diffWaysToCompute(expression.substring(i + 1));
            for (int a : left) {
                for (int b : right) {
                    if (ch == '+') res.add(a + b);
                    else if (ch == '-') res.add(a - b);
                    else res.add(a * b);
                }
            }
        }
    }

    if (res.isEmpty()) res.add(Integer.parseInt(expression));
    memo.put(expression, res);
    return res;
}

这段代码的结构就是“枚举切分点、递归左右、组合结果、缓存当前子表达式”。

五、为什么需要记忆化

表达式切分会产生大量重叠子问题。以 2*3-4*5 为例，子表达式 3-4 可能在不同的外层切分里出现。没有缓存时，它会被重复递归计算；有缓存时第一次算完后直接复用。

solve(2*3-4*5)
  切 '*': solve(3-4*5)
  切 '-': solve(2*3) + solve(4*5)
  切 '*': solve(2*3-4)

solve(3-4) 这类中间子表达式会在更长表达式里反复出现

缓存不会改变输出规模，因为所有结果仍然要生成；它减少的是同一子表达式被重复拆解和组合的成本。

六、常见误区与追问

误区：按运算符优先级先算乘法。 题目要求所有加括号方式，括号可以改变默认优先级，不能按常规表达式求值。
误区：函数只返回一个结果。 一个子表达式可能对应多个括号结构，必须返回列表。
误区：把多位数拆成多个数字。 没有运算符的子串要整体 parse 成整数。
追问：复杂度是多少？ 结果数量与不同二叉括号结构相关，接近 Catalan 数级别；缓存只能减少重复子问题，不能压缩必须输出的结果。
追问：如何优化 substring 开销？ 先把表达式解析成数字和运算符数组，用区间 [l,r] 做记忆化 key。
追问：它和动态规划有什么关系？ 若用区间长度从小到大填表，就是区间 DP；递归加缓存是自顶向下版本。

七、加强记忆

表达式加括号分治记成“枚举最后执行的运算符，左右结果集合做笛卡尔积”。纯数字是出口，运算符是切分点，返回的是所有可能结果列表。因为子表达式会重复出现，务必加记忆化；它本质上也可以改写成区间 DP。

简化版

详细版