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]
這里使用遞歸來完成，從左往右遍歷字符串瑟幕，每讀到一個(gè)符號(hào)就計(jì)算出他左邊算式可能的所有值和右邊所有可能的值能扒，并使用這個(gè)符號(hào)將所有左邊可能的值和右邊可能的值加起來來得到所有可能的結(jié)果腹纳。
比如對(duì)于一個(gè)算式4-3-2-1
最頂層我們會(huì)分成這樣幾種情況舔亭，然后對(duì)于每個(gè)子式子蝗碎，我們?cè)龠f歸的拿到它們所有可能的值
(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);
//對(duì)于每個(gè)操作符
if('+' === c || '-' === c || '*' === c) {
var lv = input.substring(0, i);
var rv = input.substring(i+1);
//計(jì)算左邊式子所有可能值
var lefts = diffWaysToCompute(lv);
//計(jì)算右邊式子所有可能值
var rights = diffWaysToCompute(rv);
//把所有可能值通過這個(gè)操作符進(jìn)行運(yùn)算
//得到當(dāng)前輸入的式子的所有結(jié)果
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都沒有值的話那就意味著當(dāng)前input是沒有操作符的
//也就意味著只有一個(gè)數(shù)字
//那就把這個(gè)數(shù)字塞到數(shù)組里返回
if(res.length===0){
res.push(Number(input));
}
return res;
};
