Divide and Conquer Solution

• ``````vector<char> op_vec;
vector<int> num_vec;

int NUM(string::const_iterator &iter)
{
int result = 0;
while('0'<=*iter && *iter<='9')
result = result*10 + *(iter++)-'0';
return result;
}

void Lexer(const string& input)
{
string::const_iterator iter = input.begin();

num_vec.push_back( NUM(iter) );

while(*iter)
{
op_vec.push_back(*iter++);
num_vec.push_back( NUM(iter) );
}
}

int basic_calc(char op, int n1, int n2)
{
if(op == '+') return n1 + n2;
if(op == '-') return n1 - n2;
if(op == '*') return n1 * n2;
if(op == '/') return n1 / n2;
}

vector<int> calculate(int start_op_id, int end_op_id)
{
if(start_op_id == end_op_id)
{
vector<int> result;
int op_id = start_op_id;
result.push_back( basic_calc(op_vec[op_id], num_vec[op_id], num_vec[op_id+1]) );
return result;
}

vector<int> result;
for(int op_id = start_op_id; op_id <= end_op_id; op_id++)
{
vector<int> r1;
if(start_op_id > op_id-1) r1.push_back( num_vec[start_op_id] );
else                      r1 = calculate(start_op_id, op_id-1);

vector<int> r2;
if(op_id+1 > end_op_id)   r2.push_back( num_vec[end_op_id+1] );
else                      r2 = calculate(op_id+1, end_op_id);

for(vector<int>::const_iterator iter1 = r1.begin(); iter1 != r1.end(); iter1++)
for(vector<int>::const_iterator iter2 = r2.begin(); iter2 != r2.end(); iter2++)
result.push_back( basic_calc(op_vec[op_id], *iter1, *iter2) );
}

return result;
}

vector<int> diffWaysToCompute(string input)
{
Lexer(input);
if( !op_vec.size() ) return num_vec;
return calculate(0, op_vec.size()-1);
}``````

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