# [C++] Three different clean solutions

• ``````class Solution {
public:
vector<int> diffWaysToCompute(string input) {
return method3(input); // or method2(input), or method1(input)
}
private:
//------------------------------------------------------------
// Method1: Brute-force (Recursive)
vector<int> method1(string &input) {
int n = input.size();
return helper1(0, n-1, input);
}
vector<int> helper1(int start, int end, string &input) {
if (start > end) return {};
vector<int> results;
for (int i = start; i <= end; i++)
if (input[i] == '+' || input[i] == '-' || input[i] == '*')
for (int a : helper1(start, i - 1, input))
for (int b : helper1(i + 1, end, input))
input[i] == '+' ? results.push_back(a + b) :
input[i] == '-' ? results.push_back(a - b) : results.push_back(a * b);
if (results.empty())
results.push_back(stoi(input.substr(start, end - start + 1)));
return results;
}

//------------------------------------------------------------
// Method2: Dynamic Programming (Top-down, Recursive + Memoization)
vector<int> method2(string &input) {
int n = input.size();
vector<vector<vector<int>>> mem (n, vector<vector<int>>(n));
return helper2(0, n-1, input, mem);
}
vector<int> helper2(int start, int end, string &input, vector<vector<vector<int>>> &mem) {
if (!mem[start][end].empty())
return mem[start][end];
for (int i = start; i <= end; i++)
if (input[i] == '+' || input[i] == '-' || input[i] == '*')
for (int a : helper2(start, i - 1, input, mem))
for (int b : helper2(i + 1, end, input, mem))
input[i] == '+' ? mem[start][end].push_back(a + b) :
input[i] == '-' ? mem[start][end].push_back(a - b) : mem[start][end].push_back(a * b);
if (start <= end && mem[start][end].empty())
mem[start][end].push_back(stoi(input.substr(start, end - start + 1)));
return mem[start][end];
}

//------------------------------------------------------------
// Method3: Dynamic Programming (Bottom-up, Iterative)
vector<int> method3(string &input) {
std::istringstream iss (input + '.'); // adding a dummy operator
vector<int> operands;
vector<char> operators;
int num;
char op;
while (iss >> num && iss >> op) {
operands.push_back(num);
operators.push_back(op);
}
operators.pop_back(); // removing the dummy operator
int n = operands.size();
vector<vector<vector<int>>> dp (n, vector<vector<int>>(n));
for (int i = 0; i < n; i++)
dp[i][i].push_back(operands[i]);

for (int l = 1; l < n; l++)
for (int i = 0; i < n - l; i++) {
int j = i + l;
for (int k = i; k < j; k++)
for (int a : dp[i][k])
for (int b : dp[k+1][j])
operators[k] == '+' ? dp[i][j].push_back(a + b) :
operators[k] == '-' ? dp[i][j].push_back(a - b) : dp[i][j].push_back(a * b);
}
return dp[0][n-1];
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.