在C ++中打印所有求值到目标的可能表达式
在这个问题中，我们得到了一个从0到9的整数字符串和一个目标值。我们必须打印出使用+，-和*运算生成表达式的方式，这些运算的值等于目标值。
让我们举个例子来更好地理解这个话题-
Input: string = “123” , target= 6
Output: { “1+2+3”, “1*2*3” }为了解决此问题，我们将通过在数字之间放置所有可能的二进制运算符来创建表达式，然后使用目标值检查表达式的结果。
我们将所有值传递给将评估结果表达式的递归方法。如果数字从0开始，那么我们将忽略它。
示例
#include <bits/stdc++.h>
using namespace std;
void generateExpressionForTarget(vector<string>& res, string curExp,
string input, int target, int pos,int curVal, int last){
if (pos == input.length()){
if (curVal == target)
res.push_back(curExp);
return;
}
for (int i = pos; i < input.length(); i++){
if (i != pos && input[pos] == '0')
break;
string part = input.substr(pos, i + 1 - pos);
int cur = atoi(part.c_str());
if (pos == 0)
generateExpressionForTarget(res, curExp + part, input, target, i + 1, cur, cur);
else{
generateExpressionForTarget(res, curExp + "+" + part, input, target, i + 1, curVal + cur, cur);
generateExpressionForTarget(res, curExp + "-" + part, input, target, i + 1, curVal - cur, -cur);
generateExpressionForTarget(res, curExp + "*" + part, input, target, i + 1, curVal - last + last * cur, last * cur);
}
}
}
vector<string>generateExpression(string input, int target){
vector<string> res;
generateExpressionForTarget(res, "", input, target, 0, 0, 0);
return res;
}
int main(){
string input = "345";
int target = 12;
cout<<"The expressions are: \n";
vector<string> res = generateExpression(input, target);
for (int i = 0; i < res.size(); i++)
cout << res[i] << " ";
cout << endl;
return 0;
}输出结果
表达式是-
3+4+5