每日题解:LeetCode 241. 为运算表达式设计优先级

题目地址
个人博客地址

题目描述

定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

示例 1:

输入: "2-1-1"
输出: [0, 2]
解释: 
((2-1)-1) = 0 
(2-(1-1)) = 2

示例 2:

输入: "2*3-4*5"
输出: [-34, -14, -10, -10, 10]
解释: 
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

解法

class Solution {
public:
    vector<int> helper(vector<int>& nums, vector<int>& ops, int l, int r){
        vector<int> ans;
        if(l == r) {
            ans.push_back(nums[l]);
        }else{
            for(int i = l; i < r; i++) {
                //左
                vector<int> ls = helper(nums, ops, l, i);
                //右
                vector<int> rs = helper(nums, ops, i+1, r);
                for (int j = 0; j <  ls.size(); ++j) {
                    for (int k = 0; k < rs.size(); ++k) {
                        switch(ops[i]) {
                            case 0: ans.push_back(ls[j] + rs[k]); break;
                            case 1: ans.push_back(ls[j] - rs[k]); break;
                            case 2: ans.push_back(ls[j] * rs[k]); break;
                            default: break; // error.
                        }
                    }
                }

            }
        }
        return ans;
    }
    vector<int> diffWaysToCompute(string input) {
        vector<int> nums,ops;
        int val=0;
        for(auto &c:input){
            if(isdigit(c)){
                val = 10 * val + c - '0';
            } else{
                nums.push_back(val);
                val=0;
                switch (c) {
                    case '+':ops.push_back(0);break;
                    case '-':ops.push_back(1);break;
                    case '*':ops.push_back(2);break;
                    default:break;
                }
            }
    
        }
          nums.push_back(val);
            vector<int> res = helper(nums, ops, 0, nums.size() - 1);
            return res;
    }
};

解题思路

分治算法

我们来进行分治算法三步走：
分解：按运算符分成左右两部分，分别求解
解决：实现一个递归函数，输入算式，返回算式解
合并：根据运算符合并左右两部分的解，得出最终解

以例子 "2-1-1"为例子，以运算符为分割符号字符串，得到如下的结果

变相理解为2-0；1-1两个左右计算后的结果进行合并

1、那么就需要将字符串进行分解，得到数值和运算符，然后按照运算符计算

vector<int> nums,ops;
        int val=0;
        for(auto &c:input){
            if(isdigit(c)){
                val = 10 * val + c - '0';
            } else{
                nums.push_back(val);
                val=0;
                switch (c) {
                    case '+':ops.push_back(0);break;
                    case '-':ops.push_back(1);break;
                    case '*':ops.push_back(2);break;
                    default:break;
                }
            }
        }
        nums.push_back(val);

2、分解字符为左右两个部分，然后按照运算符计算值，最后就是合并
需要判断单个数值的情况，直接存入到结果返回

   vector<int> ans;
        if(l == r) {
        ans.push_back(nums[l]);
        }
  

其他情况就需要按照运算符进行分解，进行结算

 for(int i = l; i < r; i++) {
 //分成左右两个部分计算结果
                vector<int> ls = helper(nums, ops, l, i);
                vector<int> rs = helper(nums, ops, i+1, r);
                for (int j = 0; j <  ls.size(); ++j) {
                    for (int k = 0; k < rs.size(); ++k) {
                    //按照分割符计算左右结果
                        switch(ops[i]) {
                            case 0: ans.push_back(ls[j] + rs[k]); break;
                            case 1: ans.push_back(ls[j] - rs[k]); break;
                            case 2: ans.push_back(ls[j] * rs[k]); break;
                            default: break;
                        }
                    }
                }

            }