Different Ways to Add Parentheses

一道初看上去有点儿难度的题目，其实想明白了也不算太难。首先上题目：

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1:

Input: "2-1-1"
Output: [0, 2]
Explanation: 
((2-1)-1) = 0 
(2-(1-1)) = 2

Example 2:

Input: "2*3-4*5"
Output: [-34, -14, -10, -10, 10]
Explanation: 
(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) {
    if (input.empty()) {
        return vector<int>();
    }
    vector<int> res;
    for (int i = 0; i < input.size(); i++) {
        if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
            // Split strings
            auto lnums = diffWaysToCompute(input.substr(0, i));
            auto rnums = diffWaysToCompute(input.substr(i + 1, input.size() - 1 - (i + 1) + 1));
            for (auto ln : lnums) {
                for (auto rn : rnums) {
                    int rr = 0;
                    if (input[i] == '+') {
                        rr = ln + rn;
                    } else if (input[i] == '-') {
                        rr = ln - rn;
                    } else if (input[i] == '*') {
                        rr = ln * rn;
                    }
                    res.push_back(rr);
                }
            }
        }
    }
    if (res.empty()) {
        res.push_back(atoi(input.c_str()));
    }
    return res;
}