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

二、问题解析

  分治法是基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同的或相似的子问题，知道最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治算法三步走：

1. 分解：按运算符分成左右两部分，分别求解
2. 解决：实现一个递归函数，输入算式，返回算式解
3. 合并：根据运算符合并左右两部分的解，得出最终解

  该题采用分治法，将字符串按运算符进行拆分为左右子字符串，左右子字符串类推拆分，直至字符串内没有运算符，将数字作为结果返回。将返回的结果集按照运算符进行合并，所得结果集继续返回运算即可。

三、代码示例

vector<int> diffWaysToCompute(string input) {
    vector<int> vec = {};

    for (int i = 0; i < input.length(); i++) {
        char c = input.at(i);

        if (c == '-' || c == '+' || c == '*') {//对于每个运算符号采取分治
            vector<int> left = diffWaysToCompute(input.substr(0, i));
            vector<int> right = diffWaysToCompute(input.substr(i + 1));
            for (int l : left){
                for (int r : right) {
                    switch (c)
                    {
                    case '+':
                        vec.push_back(l + r);
                        break;
                    case '-':
                        vec.push_back(l - r);
                        break;
                    case '*':
                        vec.push_back(l * r);
                        break;
                    default:
                        break;
                    }
                }
            }
        }
    }
    if (vec.size() == 0) {//input没有符号 则为数字
    /*    stringstream ss;
        int0<< input;
        ss >> a;*/
        vec.push_back(stoi(input));
    }
    return vec;
}