leetcode做题记录 —— different-ways-to-add-parentheses

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

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

Output: [0, 2]

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

1.(2*(3-(4*5))) = -34
2.((2*3)-(4*5)) = -14
3.((2*(3-4))*5) = -10
4.(2*((3-4)*5)) = -10
5.(((2*3)-4)*5) = 10

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

different-ways-to-add-parentheses

给定一个表达式，要求返回所有不同括号划分后计算的的结果。

解法

解法类似 leetcode-unique-binary-search-trees-ii

1. 对原始的字符串进行处理，把数字和操作符分别用一个数组存储
2. 循环 1 -> nums.length -1 之间的所有数字，比如标记为i 
   
   • 分别递归计算 i 左边和右边的所有数字
   • 取得当前 i 对应的运算符
   • 用当前的运算符对所有左边和右边的计算结果进行计算，添加到结果数组里
   • 返回数组

1.//Javascript
2./**
3. * @param {string} input
4. * @return {number[]}
5. */
6.var operate = function(num1, num2, operator) {
7.    let res = 0;
8.    switch (operator) 
9.    {
10.        case "+":
11.            res = num1 + num2;
12.            break;
13.        case "-":
14.            res = num1 - num2;
15.            break;
16.        case "*":
17.            res = num1 * num2;
18.            break;
19.        default: 
20.            res = 0;
21.            break;
22.    }
23.    return res;
24.};
25.var compute = function(nums, operators) {
26.    let len = nums.length;
27.    if( len === 1 )
28.    {
29.        return nums;
30.    }
31.    if( len === 2 )
32.    {
33.        return [operate(nums[0], nums[1], operators[0])];
34.    }
35.    let res = [];
36.    for( let i = 1; i < len; i++ )
37.    {
38.        let operator = operators[i - 1];
39.        let leftRes = compute(nums.slice(0, i), operators.slice(0, i - 1));
40.        let rightRes = compute(nums.slice(i, len), operators.slice(i));
41.        for( let l = 0; l < leftRes.length; l++ ) 
42.        {
43.            for( let r = 0; r < rightRes.length; r++ ) 
44.            {
45.                res.push(operate(leftRes[l], rightRes[r], operator));
46.            }
47.        }
48.    }
49.    return res;
50.};
51.var diffWaysToCompute = function(input) {
52.    let nums = input.match(/\d+/g).map(e=>+e);
53.    let operators = input.match(/[\+\-\*]/g);
54.    return compute(nums, operators);
55.};

End