遍历每个算符，每个算符把表达式分成左右两个子问题。

逻辑表达式加括号的方式数

给定只有0、1、&、|、^ 的布尔表达式，和期望的结果result，求加括号的方式数。如 countEval("1^0|0|1", false) -> 2，countEval("0&0&0&1^1|1", true) -> 10

int countEval(String s, boolean result) {
    if (s.length() == 0) return 0;
    if (s.length() == 1) return s.equals("1") == result ? 1 : 0;

    int ways = 0;
    for (int i = 1; i < s.length(); i += 2) { // 遍历每个算符
        char c = s.charAt(i);
        String left = s.substring(0, i);
        String right = s.substring(i + 1, s.length());

        int leftTrue = countEval(left, true);
        int leftFalse = countEval(left, false);
        int rightTrue = countEval(right, true);
        int rightFalse = countEval(right, false);
        int total = (leftTrue + leftFalse) * (rightTrue + rightFalse);

        int totalTrue = 0;
        if (c == '&') {
            totalTrue = leftTrue * rightTrue;
        } else if (c == '|') {
            totalTrue = leftTrue * rightTrue + leftFalse * rightTrue + leftTrue * rightFalse;
        } else if (c == '^') {
            totalTrue = leftTrue * rightFalse + leftFalse * rightTrue;
        }

        ways += result ? totalTrue : total - totalTrue;
    }
    return ways;
}

会重复计算子问题，要用备忘录memo缓存计算结果（s+result => count）。

加减乘表达式加括号计算的所有结果

vector<int> diffWaysToCompute(string input) {
    vector<int> ans;
    for (int i = 0; i < input.size(); i++) {
        char c = input[i];
        if (c == '+' || c == '-' || c == '*') { // 分治
            auto ans1 = diffWaysToCompute(input.substr(0, i));
            auto ans2 = diffWaysToCompute(input.substr(i + 1));
            for (auto n1 : ans1) {
                for (auto n2 : ans2) {
                    if (c == '+') {
                        ans.push_back(n1 + n2);
                    } else if (c == '-') {
                        ans.push_back(n1 - n2);
                    } else {
                        ans.push_back(n1 * n2);
                    }
                }
            }
        }
    }
    if (ans.empty()) { // input是纯数字串
        ans.push_back(stoi(input));
    }
    return ans;
}