数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究用 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
更新于： 2020 年 1 月 17 日
237 次查看
广告