在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