list<int> operand_res;
|
list<char> oper_res;
|
|
void exp_synthesis(const vector<int>& A, int k) {
|
list<char> oper_list;
|
list<int> operand_list;
|
if (!exp_synthesis_helper(A, k, &operand_list, &oper_list, 0, 0)) {
|
cout << "no answer" << endl;
|
}
|
}
|
|
bool exp_synthesis_helper(const vector<int>& A, int k,
|
list<int>* operand_list, list<char>* oper_list,
|
int cur, int level) {
|
cur = cur * 10 + A[level];
|
if (level == A.size() - 1) {
|
operand_list->emplace_back(cur);
|
if (evaluate(*operand_list, *oper_list) == k) { // found a match.
|
// @exclude
|
operand_res = *operand_list, oper_res = *oper_list;
|
// @include
|
// Print the solution.
|
auto operand_it = operand_list->cbegin();
|
cout << *operand_it++;
|
for (const char& oper : *oper_list) {
|
cout << ' ' << oper << ' ' << *operand_it++;
|
}
|
cout << " = " << k << endl;
|
return true;
|
}
|
operand_list->pop_back();
|
} else {
|
// No operator.
|
if (exp_synthesis_helper(A, k, operand_list, oper_list, cur, level + 1)) {
|
return true;
|
}
|
|
// Add operator '+'.
|
operand_list->emplace_back(cur);
|
if (k - evaluate(*operand_list, *oper_list) <=
|
remaining_int(A, level + 1)) { // pruning.
|
oper_list->emplace_back('+');
|
if (exp_synthesis_helper(A, k, operand_list, oper_list, 0, level + 1)) {
|
return true;
|
}
|
oper_list->pop_back(); // revert.
|
}
|
operand_list->pop_back(); // revert.
|
|
// Add operator '*'.
|
operand_list->emplace_back(cur), oper_list->emplace_back('*');
|
if (exp_synthesis_helper(A, k, operand_list, oper_list, 0, level + 1)) {
|
return true;
|
}
|
operand_list->pop_back(), oper_list->pop_back(); // revert.
|
}
|
return false;
|
}
|
|
// Calculate the int represented by A[idx:].
|
int remaining_int(const vector<int>& A, int idx) {
|
int val = 0;
|
for (size_t i = idx; i < A.size(); ++i) {
|
val = val * 10 + A[idx];
|
}
|
return val;
|
}
|
|
int evaluate(list<int> operand_list, const list<char>& oper_list) {
|
// Evaluate '*' first.
|
auto operand_it = operand_list.begin();
|
for (const char& oper : oper_list) {
|
if (oper == '*') {
|
int product = *operand_it;
|
operand_it = operand_list.erase(operand_it);
|
product *= *operand_it;
|
*operand_it = product;
|
} else {
|
++operand_it;
|
}
|
}
|
|
// Evaluate '+' second.
|
return accumulate(operand_list.cbegin(), operand_list.cend(), 0);
|
| } |
