Different Ways to Add Parentheses

开始每天坚持刷OJ和Paper吧。

今天的题目是 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:

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

Example 2:

1
Input: "2*3-4*5"
2
Output: [-34, -14, -10, -10, 10]
3
Explanation:
4
(2*(3-(4*5))) = -34
5
((2*3)-(4*5)) = -14
6
((2*(3-4))*5) = -10
7
(2*((3-4)*5)) = -10
8
(((2*3)-4)*5) = 10

太久没刷过题的后果就是之前掌握的一些解题思路好像有点生疏了，但还是勉强完成了这道题，首先从两个Example开始分析，第一个太简单好像看不出什么，我们分析一下第二个，我们可以看到，(2*(3-(4*5))) = -34是先算第二个*，然后再算-，最后算第一个*。大概可以猜出来我们需要穷举所有运算顺序，但应该不是全排列，因为当运算符个数为3时，他的运算顺序只有5个，而不是6个。仔细分析一下可以发现，这是因为已下两种算法是一样的：

先算第一个，再算第三个，最后算第二个
先算第三个，再算第一个，最后算第二个

这就有点像一个二叉树了，层数相同的情况。我们尝试把上面五种运行顺序用二叉树表示出来，首先，分别用1,2,3代替*,-,*:

画出来后，我们很容易的发现，这个问题变成了对平衡二叉树的穷举问题，因此代码如下：

1
vector<int> nums;
2
vector<char> ops;
3
vector<int> diffWaysToCompute(string input) {
4
    vector<int> res;
5

6
    int num; char op;
7
    stringstream ss(input);
8

9
    ss >> num;
10
    nums.push_back(num);
11
    while(ss >> op >> num) {
12
        nums.push_back(num);
13
        ops.push_back(op);
14
    }
15

39 collapsed lines
16
    helper(0, ops.size(), res);
17
    return res;
18
}
19

20
int calc(char op, int i1, int i2) {
21
    int res = 0;
22
    switch(op) {
23
        case '+': res = i1 + i2; break;
24
        case '-': res = i1 - i2; break;
25
        case '*': res = i1 * i2; break;
26
    }
27
    return res;
28
}
29

30
void helper(int first, int last, vector<int> &outputs) {
31
    if (first == last) {
32
        outputs.push_back(nums[first]);
33
        return ;
34
    }
35

36
    vector<int> lefts;
37
    vector<int> rights;
38

39
    for(int i = first; i < last;i++) {
40
        // select ops[i] in this layer
41
        lefts.clear();
42
        rights.clear();
43

44
        helper(first, i, lefts);
45
        helper(i+1, last, rights);
46

47
        for(auto l: lefts) {
48
            for(auto r: rights) {
49
                outputs.push_back(calc(ops[i], l, r));
50
            }
51
        }
52
    }
53

54
}

由于stringstream的效率的确不行，所以我们可以尝试将解析字符串的那段代码改成：

1
int beg = 0, end = 0;
2
for(;end < input.size(); end++) {
3
    if (input[end] == '+' || input[end] == '-' || input[end] == '*') {
4
        nums.push_back(stoi(input.substr(beg, end - beg)));
5
        ops.push_back(input[end]);
6
        beg = end + 1;
7
    }
8
}
9
nums.push_back(stoi(input.substr(beg, end - beg)));