C++での式追加演算子

0から9までの数字のみを保持する文字列があるとします。そして、1つのターゲット値が与えられます。ターゲット値を取得するには、2項演算子+、-、および*を数字に追加するためのすべての可能性を返す必要があります。したがって、入力が「232」のようで、ターゲットが8の場合、答えは[“ 2 * 3 + 2”、“ 2 + 3 * 2”]

これを解決するには、次の手順に従います-

• Solve（）と呼ばれるメソッドを定義します。これは、index、s、curr、target、temp、mult-

  を取ります。

• idx> =sのサイズの場合、

  • ターゲットがcurrと同じ場合、

    • retの最後にtempを挿入します

  • 戻る

• aux：=空の文字列

• i：=idxを初期化するために、i

  • aux =aux + s [i]

  • aux [0]が「0」と同じで、auxのサイズが1より大きい場合、

    • 次の反復にスキップし、次の部分を無視します

  • idxが0と同じ場合、

    • 呼び出しsolve（i + 1、s、aux as integer、target、aux、aux as integer）

  • それ以外の場合

    • 呼び出しsolve（i + 1、s、curr + aux as integer、target、temp + "+" + aux、aux asinteger）

    • 呼び出しsolve（i + 1、s、curr --aux as integer、target、temp + "-" + aux、--aux asinteger）

    • 呼び出しsolve（i + 1、s、curr --mult + mult * aux as integer、target、temp + "*" + aux、mult * aux as integer）

• メインメソッドからsolve（0、num、0、target、empty string、0）

  を呼び出します。

• retを返す

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
typedef long long int lli;
class Solution {
   public:
   vector <string> ret;
   void solve(int idx, string s, lli curr, lli target, string temp, lli mult){
      //cout << temp << " " << curr << endl;
      if(idx >= s.size()){
         if(target == curr){
            ret.push_back(temp);
         }
         return;
      }
      string aux = "";
      for(int i = idx; i < s.size(); i++){
         aux += s[i];
         if(aux[0] == '0' && aux.size() > 1) continue;
         if(idx == 0){
            solve(i + 1, s, stol(aux), target, aux, stol(aux));
         } else {
            solve(i + 1, s, curr + stol(aux), target, temp + "+" + aux, stol(aux));
            solve(i + 1, s, curr - stol(aux), target, temp + "-" + aux, -stol(aux));
            solve(i + 1, s, curr - mult + mult * stol(aux), target, temp + "*" + aux, mult * stol(aux));
         }
      }
   }
   vector<string> addOperators(string num, int target) {
      solve(0, num, 0, target, "", 0);
      return ret;
   }
};
main(){
   Solution ob;
   print_vector(ob.addOperators("232", 8));
}

入力

"232", 8

出力

[2+3*2, 2*3+2, ]