# [recommend for beginners]clean C++ implementation with detailed explanation

• ``````class Solution {
public:
vector<int> diffWaysToCompute(string input) {
int size=input.size();
vector<int> result;
for(int i=0; i<size; i++){
if(ispunct(input[i])){
for(int a : diffWaysToCompute(input.substr(0, i)))
for(int b : diffWaysToCompute(input.substr(i+1))){
if(input[i]=='+')  result.push_back(a+b);
if(input[i]=='-')  result.push_back(a-b);
if(input[i]=='*')  result.push_back(a*b);
}
}
}
/*** the base case is that there are no operator-char ***/
/*** we return vector<int>{stoi(input)} when this happens ***/
return result.size() ? result : vector<int>{stoi(input)};
}
};``````

• The key to the solution is that we need to return

``````   return result.size() > 0 ? result : vector<int>{ stoi(input) };
``````

The return value is really important .....

The recursion solution is similiar to construct all the binary tree using {1, 2... , n}

Here is the AC implementation

``````class Solution {
public:
vector<int> diffWaysToCompute(string input) {
int size_str = input.size();
vector<int> result;
for(int i = 0; i < size_str; i++) {
if(isOperator(input[i])) {
vector<int> left = diffWaysToCompute(input.substr(0, i));
vector<int> right = diffWaysToCompute(input.substr(i + 1));
for(int a : left) {
for(int b : right) {
if(input[i] == '+')  result.push_back(a + b);
if(input[i] == '-')  result.push_back(a - b);
if(input[i] == '*')  result.push_back(a * b);
}
}
}
}
return result.size() > 0 ? result : vector<int>{ stoi(input) };
}

bool isOperator(char c) {
return  !(c >= '0' && c <= '9');
}
};
``````

• I forget to use stoi(string) to change from string to int value ....

• This is a typical divide and conquer solution to solve this problem....

• ``````class Solution {
public:
vector<int> diffWaysToCompute(string input) {
vector<int> result;
/** check if the string contains operators **/
if (input.size() == to_string(stoi(input)).size()) return vector<int>({stoi(input)});
for (int i = 0; i < input.size(); i++) {
if (isdigit(input[i])) continue;
vector<int> lefts = diffWaysToCompute(input.substr(0, i));
vector<int> rights = diffWaysToCompute(input.substr(i + 1));
for (int left : lefts) {
for (int right : rights) {
switch(input[i]) {
case '+': result.push_back(left + right); break;
case '-': result.push_back(left - right); break;
case '*': result.push_back(left * right); break;
}
}
}
}
return result;
}
};``````

• This is so clean, a solution should be. Awesome, dude!

• @RainbowSecret But there can be some performance problem, isn't it?

• repeatedly `substr` which can be replaced by `index range`
• each time the left `a` moves forward, the `right` substring will have to do another computation

• @RainbowSecret Here is a solution paying attention to efficiency and of course result in best submission as follows:

``````class Solution {
private:
int sLen;
vector<int> helper(const string& s, int begin, int end)
{
vector<int> v;
if(begin > end) return v;
for(int i = begin; i <= end; ++i)
{
if(!isdigit(s[i]))
{
vector<int> l = helper(s, begin, i-1), r = helper(s, i+1, end);
for(int j = 0; j < l.size(); ++j)
{
for(int k = 0; k < r.size(); ++k)
{
switch(s[i])
{
case '-': v.push_back(l[j]-r[k]); break;
case '+': v.push_back(l[j]+r[k]); break;
case '*': v.push_back(l[j]*r[k]); break;
}
}
}
}
}
return v.size()? v : vector<int>{stoi(s.substr(begin, end-begin+1))};
}
public:
vector<int> diffWaysToCompute(string input) {
sLen = input.length();
return helper(input, 0, sLen-1);
}
};
``````

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