给定多项式任意加括号求所有输出结果

问题描述

20171223103914818.png

基本思路：分治

代码

class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        vector<int> res;
        for(int i = 0; i < input.size(); ++i)//枚举串的每个位置
        {
            //如果是操作符，就将左右两边分开
            if(isOperator(input[i]))
            {
                //返回左边和右边的所有可能结果
                vector<int> lhs = diffWaysToCompute(input.substr(0, i));
                vector<int> rhs = diffWaysToCompute(input.substr(i + 1));
                //依次组合，因为返回之前考虑了为空的情况，所以这里无需判断是否为空
                for(auto n1 : lhs)//对于左边的每一个数，枚举右边的数，记录这两个数进行第i位操作符后产生的结果
                {
                    for(auto n2 : rhs)
                    {
                        if(input[i] == '+') res.emplace_back(n1 + n2);
                        else if(input[i] == '-')    res.emplace_back(n1 - n2);
                        else    res.emplace_back(n1 * n2);
                    }
                }
            }
        }
        if(res.empty())
        {
            //可以添加一条语句判断input是空字符的情况
            //if(input.empty()) input.append(1, '0');
            int n = 0;
            sscanf(input.c_str(), "%d", &n);
            res.emplace_back(n);
        }
        return res;
    }
private:
    bool isOperator(char op)
    {
        return op == '+' || op == '-' || op == '*';
    }
};

举例子

23-45
如果现在是第一个*
左边就是2，右边就是3-45，对于右边的递归调用 可能是-5，-17，然后用动态数组res添加枚举的两个数，即2-5与2*-17