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