Description of the Problem
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.
Example 1
Input: "2-1-1".
((2-1)-1) = 0
(2-(1-1)) = 2
Output: [0, 2]
Example 2
Input: "2x3-4x5"
(2x(3-(4x5))) = -34
((2x3)-(4x5)) = -14
((2x(3-4))x5) = -10
(2x((3-4)x5)) = -10
(((2x3)-4)x5) = 10
Output: [-34, -14, -10, -10, 10]
Solution1 : Divide and Conquer (Wrong Answer 19/25)
Decompose the problem into smaller and similar parts.
Realizing that the result is certain when there are 2 operators, so we want to make whatever input we get into the pattern of 2 operators.
For example, an expression of 4 operators A op B op C op D can be divided into expressions of 3 operators:
- (A op B) op C op D
- A op (B op C) op D
- A op B op (C op D)
Which can be furtherly divided into expressions of 2 operators:
Take 1 for example:
1.1 ((A op B) op C) op D
1.2 (A op B) op (C op D)
Whose result would then be unique.
class Solution {
public:
vector<int> diffWaysToCompute(string input) {
vector<int> results;
vector<int> operators;
vector<char> operations;
vector<string> expressions;
bool flag; // check if the input has only one operator.
for (int i = 0; i < input.size(); i++) {
if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
flag = false;
break;
}
flag = true;
}
if (flag) {
results.push_back(stoi(input));
return results;
}
int LastBegin = 0; // begin index of the last operator
string oprt = "";
for (int i = 0; i < input.length(); i++) { // get all operators and operations.
if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
operations.push_back(input[i]);
oprt = input.substr(LastBegin, i-LastBegin);
operators.push_back(stoi(oprt));
LastBegin = i + 1;
}
}
oprt = input.substr(LastBegin, input.length() - LastBegin);
operators.push_back(stoi(oprt));
DivideAndConquer(operators, operations, results, expressions);
return results;
}
void DivideAndConquer(vector<int> operators, vector<char> operations, vector<int>& results, vector<string>& expressions) {
int result;
if (operators.size() == 2) { // unique result
stringstream ss;
string expression = "";
if (operations[0] == '+') {
result = operators[0] + operators[1];
ss << (operators[0]);
ss << '+';
ss << (operators[1]);
expression = ss.str();
}
else if (operations[0] == '-') {
result = operators[0] - operators[1];
ss<<(operators[0]);
ss<< '-';
ss<<(operators[1]);
expression = ss.str();
}
else if (operations[0] == '*') {
result = operators[0] * operators[1];
ss << (operators[0]);
ss << '*';
ss << (operators[1]);
expression = ss.str();
}
if (!FindExpression(expression, expressions)) {
results.push_back(result);
expressions.push_back(expression);
}
return;
}
vector<int> NextRoundOperators;
vector<char> NextRoundOperations;
for (int i = 0; i < operations.size(); i++) { // calculate in different orders
NextRoundOperations.clear();
NextRoundOperators.clear();
if (operations[i] == '+')
result = operators[i] + operators[i + 1];
else if (operations[i] == '-')
result = operators[i] - operators[i + 1];
else if (operations[i] == '*')
result = operators[i] * operators[i + 1];
for (int j = 0; j< operators.size(); j++) {
if (j != i && j != i + 1)
NextRoundOperators.push_back(operators[j]);
}
vector<int>::iterator it = NextRoundOperators.begin();
int temp = i;
while (temp--)
it++;
NextRoundOperators.insert(it, result);
for (int k = 0; k < operations.size(); k++) {
if (k != i)
NextRoundOperations.push_back(operations[k]);
}
DivideAndConquer(NextRoundOperators, NextRoundOperations, results, expressions);
}
}
bool FindExpression(string exp, vector<string> exps) {
for (int i = 0; i < exps.size(); i++) {
if (exp == exps[i])
return true;
}
return false;
}
};
Solution 2
Every time we encounter an operator, record it and divide the expression into 2 parts [exp1 op exp2] by the operator.
For each part, which is also an expression, would have its calculating result, so the expression [exp1 op exp2] would also have its result.
class Solution {
public:
vector<int> diffWaysToCompute(string input) {
vector<int> result;
int size = input.size();
for (int i = 0; i < size; i++) {
char cur = input[i];
if (cur == '+' || cur == '-' || cur == '*') {
// Split input string into two parts and solve them recursively
vector<int> result1 = diffWaysToCompute(input.substr(0, i));
vector<int> result2 = diffWaysToCompute(input.substr(i+1));
for (auto n1 : result1) {
for (auto n2 : result2) {
if (cur == '+')
result.push_back(n1 + n2);
else if (cur == '-')
result.push_back(n1 - n2);
else
result.push_back(n1 * n2);
}
}
}
}
// if the input string contains only number
if (result.empty())
result.push_back(atoi(input.c_str()));
return result;
}
};
