Leetcode 241: different ways to add parenthese

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".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2 Input: "2*3-4*5"

(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

Output: [-34, -14, -10, -10, 10]

这个题目一开始看起来觉得像DFS，想到可以dfs找出所有可能有效的加括号的表达式，然后利用basic caculatorII去计算结果，但是这样做未免太过复杂，觉得肯定有比这个简单的算法。想了下没有想到，看了下网上别人的解决方案，
发现这个题目的思想是divide and conquer， 分而治之，跟 merge sort / quick sort 的思想是相似的， 要想把整个array 排好序，可以先分成左右两个部分，左边排好序，右边排好序，然后再merge 左右两边的sorted array就好了，分而治之就是把一个大问题分成几个小的部分，解决出这个小部分的结果，然后再利用小部分的结果来解决整个问题，处理过程中是需要用到recursion的。 divide and conquer是我自己在算法中掌握得特别不好的部分，练习中要把握好分而治之的思想去解题。

那么这个题目怎么利用分而治之的算法去解题呢？
要计算一个有很多+，-，*的表达式，可以以+，-，*为分界点，将整个表达式分成两个部分，操作符左边的部分，和操作符右边的部分，如果我们可以计算出操作符左边的部分，和操作符右边的部分的结果，那么整个表达式的结果我们就能计算出来了。这个题目就是这个思想，我们可以遍历整个input,对于所有的操作符，都计算出左右两部分的结果，结果也是一个vector<int>因为两部分的结果可能因为操作符计算部分不同而得到不同的结果，最后将这两个结果进行一一计算出来。

注意divide and conquer的算法实现是recursion的思想，所以要注意到base case和recursion rule的处理。 

class Solution {
private:
    int cal(int left, int right, char opt) {
        switch(opt) {
            case '+' : return left + right;
            case '-' : return left - right;
            case '*' : return left * right;
        }
        return -1;
    }
public:
    vector<int> diffWaysToCompute(string input) {
        vector<int> rst;
        //base cae
        int val = 0;
        int idx = 0;
        while (idx < input.size() && isdigit(input[idx])) {
            val *= 10;
            val += input[idx]-'0';
            idx++;
        }
        if (idx == input.size()) {
            rst.push_back(val);
            return rst;
        }
        for (int k = 0; k < input.size(); k++) {
            if (!isdigit(input[k])) {
                vector<int> left = diffWaysToCompute(input.substr(0,k));
                vector<int> right = diffWaysToCompute(input.substr(k+1));
                for (int i = 0; i < left.size(); i++) {
                    for (int j = 0; j < right.size(); j++) {
                        rst.push_back(cal(left[i], right[j], input[k]));
                    }
                }
            }
        }
        return rst;
    }
};