241. Different Ways to Add Paren

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: "23-45"
(2(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)5) = 10
Output: [-34, -14, -10, -10, 10]

这里使用递归来完成，从左往右遍历字符串，每读到一个符号就计算出他左边算式可能的所有值和右边所有可能的值，并使用这个符号将所有左边可能的值和右边可能的值加起来来得到所有可能的结果。
比如对于一个算式4-3-2-1
最顶层我们会分成这样几种情况，然后对于每个子式子，我们再递归的拿到它们所有可能的值
(4)-(3-2-1)
(4-3)-(2-1)
(4-3-2)-(1)

var diffWaysToCompute = function(input) {
    var res = [];  
    //遍历所有字符
    for(var i = 0;i < input.length;i++){  
        var c = input.charAt(i);  
        //对于每个操作符
        if('+' === c || '-' === c || '*' === c) {  
            var lv = input.substring(0, i);  
            var rv = input.substring(i+1);  
            //计算左边式子所有可能值
            var lefts = diffWaysToCompute(lv);  
            //计算右边式子所有可能值
            var rights = diffWaysToCompute(rv);  
            //把所有可能值通过这个操作符进行运算
            //得到当前输入的式子的所有结果
            for(var j = 0;j<lefts.length;j++) {  
                for(var k = 0;k<rights.length;k++){  
                    var temp = 0;  
                    switch(c){  
                        case'+':   
                            temp = lefts[j]+rights[k];  
                            break;  
                        case'-':   
                            temp = lefts[j]-rights[k];  
                            break;  
                        case'*': 
                            temp = lefts[j]*rights[k];  
                    }  
                    res.push(temp);  
                }  
            }  
        }  
    }  
    //如果到这里res都没有值的话那就意味着当前input是没有操作符的
    //也就意味着只有一个数字
    //那就把这个数字塞到数组里返回
    if(res.length===0){  
        res.push(Number(input));  
    }  
    return res;  
};