241. Different Ways to Add Parentheses

The key is to treat each operator as the last one to process, divide the problem into two problems, i.e. get the left and right results around the operator, and then iterate the left and right results to conquer the final solution. Also, don't forget if there is no operator, we need to atoi the string. This is a very important step to make the divide and conquer method work.

1:  class Solution {  
2:  public:  
3:    vector<int> diffWaysToCompute(string input) {  
4:      vector<int> res;  
5:      for (int i = 0; i < input[i]; i++) {  
6:        if (input[i] < '0' || input[i] > '9') {  
7:          vector<int> left = diffWaysToCompute(input.substr(0, i));  
8:          vector<int> right = diffWaysToCompute(input.substr(i+1));  
9:          for (int l = 0; l < left.size(); l++) {  
10:            for (int r = 0; r < right.size(); r++) {  
11:              if (input[i] == '+') res.push_back(left[l] + right[r]);  
12:              else if (input[i] == '-') res.push_back(left[l] - right[r]);  
13:              else if (input[i] == '*') res.push_back(left[l] * right[r]);  
14:            }  
15:          }  
16:        }  
17:      }  
18:      if (res.empty()) {  
19:        res.push_back(atoi(input.c_str()));  
20:      }  
21:      return res;  
22:    }  
23:  };