solved 'Different Ways to Add Parentheses' on LeetCode https://leetcode.com/problems/different-ways-to-add-parentheses/

ways_to_compute.cc

// Simple recursive algorithm. Didn't use DP considering that
// it needs to store a list for every DP entry (n * n).
class Solution {
 public:
  vector<int> diffWaysToCompute(string input) {
    tokens_ = parse(input);
    return diffWaysToCompute(0, tokens_.size());
  }

 private: 
  // Assume expression is always valid, transform into 
  // a vector of operators and operands.
  static vector<string> parse(string expr) {
    vector<string> tokens;
    string curr_num_str;
    for (char ch : expr) {
      if (ch >= '0' && ch <= '9') {
        curr_num_str += ch;
      } else {
        // Process previous number.
        tokens.push_back(curr_num_str);
        curr_num_str.clear();
        // Push operators.
        tokens.push_back(string(1, ch));
      }
    }
    tokens.push_back(curr_num_str);
    return tokens;
  }
  
  // Evaluate a ternary expression.
  static inline int eval(string op, int operand1, int operand2) {
    switch (op[0]) {
      case '+':
        return operand1 + operand2;
      case '-':
        return operand1 - operand2;
      case '*':
        return operand1 * operand2;
    }
    // Never happened.
    return 0;
  }
  
  vector<int> diffWaysToCompute(int start, int end) {
    vector<int> results;
    if (start + 1 == end) {
      // Single number.
      results.push_back(atoi(tokens_[start].c_str()));
    } else {
      // Process every operator.
      for (int i = start + 1; i < end; i += 2) {
        vector<int> results_left = diffWaysToCompute(start, i);
        vector<int> results_right = diffWaysToCompute(i + 1, end);
        // Cartesian product of left and right answers.
        for (int left : results_left) {
          for (int right : results_right) {
            results.push_back(eval(tokens_[i], left, right));
          }
        }
      }
    }
    return results;
  }

  vector<string> tokens_;
};