为运算表达式设计优先级 图解题解

这道题到底在问什么

输入

expression="2-1-1"

输出

[0,2] （(2-(1-1))=2、((2-1)-1)=0）

输入

expression="11"

输出

[11] （没有运算符，直接是数字本身）

最优解：一步一步想明白

1. 3记住这套「在运算符处劈开 → 递归两边 → 两两组合」，每个运算符当根就得到一棵表达式树，下面逐棵看。
2. 4整个表达式 2-1-1 就是要解的根。它有两个减号，意味着有两个位置可以「最后算」，对应两种加括号方式、两棵表达式树。我们一棵棵展开。
3. 5第一种：在第 1 个减号处劈开。左边是数字 2（叶子，直接得 [2]，存进 memo），右边是子表达式 1-1，还要继续往下算（标灰待展开）。
4. 6展开右子 1-1：它在自己的减号处再劈成两个叶子 1 和 1。现在这棵树长全了，开始从最底层往上算。
5. 7先算右子树：两个叶子都是 1，1 - 1 = 0。子表达式 1-1 算完得 [0]，连同叶子 1 一起存进 memo。
6. 8再算根：左边 2 减去 右子树算出的 0，2 - 0 = 2。第一种加括号 (2-(1-1)) = 2，记入结果。
7. 9第二种：改在第 2 个减号处劈开。左边是子表达式 2-1（待展开），右边是数字 1。注意右边 dfs("1") 之前算过，直接命中 memo 取 [1]，不重复递归。
8. 10展开左子 2-1：劈成叶子 2 和 1。这两个 dfs("2")、dfs("1") 也都在 memo 里，命中缓存直接取值，省掉重复计算。
9. 11先算左子树：2 - 1 = 1。子表达式 2-1 得 [1]，存进 memo。
10. 12再算根：左子树的 1 减去 右边 1，1 - 1 = 0。第二种 ((2-1)-1) = 0。两种方式都算完，根表达式 2-1-1 的全部结果也存入 memo。
11. 13两种加括号分别得到 2 和 0，全部结果 = [0, 2]（每种括号方式各贡献一个值、有重复也全保留，本例正好没有重复）。memo 里五条缓存都还在，子表达式只算了一次。回头看：这个例子里两个减号各当一次根、正好得到两棵树；表达式更长时，每个顶层根还要递归展开左右两边、把两边的多个结果两两组合，所以一个根可能对应多棵树、多个结果。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
from functools import lru_cache
class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        @lru_cache(None)
        def dfs(s: str):
            ans = []
            for i, ch in enumerate(s):
                if ch in '+-*':
                    for a in dfs(s[:i]):
                        for b in dfs(s[i+1:]):
                            ans.append(a + b if ch == '+' else a - b if ch == '-' else a * b)
            return tuple(ans or [int(s)])
        return list(dfs(expression))

#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
    unordered_map<string, vector<int>> memo;
public:
    vector<int> diffWaysToCompute(string expression) {
        if (memo.count(expression)) return memo[expression];
        vector<int> ans;
        for (int i = 0; i < (int)expression.size(); ++i) {
            char op = expression[i];
            if (op == '+' || op == '-' || op == '*') {
                auto left = diffWaysToCompute(expression.substr(0, i));
                auto right = diffWaysToCompute(expression.substr(i + 1));
                for (int a : left) for (int b : right) ans.push_back(op == '+' ? a + b : op == '-' ? a - b : a * b);
            }
        }
        if (ans.empty()) ans.push_back(stoi(expression));
        return memo[expression] = ans;
    }
};

import java.util.*;
class Solution {
    private final Map<String, List<Integer>> memo = new HashMap<>();
    public List<Integer> diffWaysToCompute(String expression) {
        if (memo.containsKey(expression)) return memo.get(expression);
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < expression.length(); i++) {
            char op = expression.charAt(i);
            if (op == '+' || op == '-' || op == '*') {
                for (int a : diffWaysToCompute(expression.substring(0, i))) {
                    for (int b : diffWaysToCompute(expression.substring(i + 1))) {
                        ans.add(op == '+' ? a + b : op == '-' ? a - b : a * b);
                    }
                }
            }
        }
        if (ans.isEmpty()) ans.add(Integer.parseInt(expression));
        memo.put(expression, ans);
        return ans;
    }
}

复杂度

面试官可能追问