Sep 20, 2017

# 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"
Output: [0, 2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2


Example 2:

Input: "2*3-4*5"
Output: [-34, -14, -10, -10, 10]
Explanation:
(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


1. 先算第一个，再算第三个，最后算第二个
2. 先算第三个，再算第一个，最后算第二个

1
\
2
\
3

    2
/   \
1     3

  1
\
3
/
2

   1
/
3
\
2

     3
/
2
/
1


vector<int> nums;
vector<char> ops;
vector<int> diffWaysToCompute(string input) {
vector<int> res;

int num; char op;
stringstream ss(input);

ss >> num;
nums.push_back(num);
while(ss >> op >> num) {
nums.push_back(num);
ops.push_back(op);
}

helper(0, ops.size(), res);
return res;
}

int calc(char op, int i1, int i2) {
int res = 0;
switch(op) {
case '+': res = i1 + i2; break;
case '-': res = i1 - i2; break;
case '*': res = i1 * i2; break;
}
return res;
}

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

vector<int> lefts;
vector<int> rights;

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

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

for(auto l: lefts) {
for(auto r: rights) {
outputs.push_back(calc(ops[i], l, r));
}
}
}

}


int beg = 0, end = 0;
for(;end < input.size(); end++) {
if (input[end] == '+' || input[end] == '-' || input[end] == '*') {
nums.push_back(stoi(input.substr(beg, end - beg)));
ops.push_back(input[end]);
beg = end + 1;
}
}
nums.push_back(stoi(input.substr(beg, end - beg)));

LeetCodeLeetCode

3Sum