C++で括弧を追加するさまざまな方法

一連の数値と演算子があるとすると、数値と演算子をグループ化するためのさまざまな可能な方法をすべて計算することで、考えられるすべての結果を見つける必要があります。ここで、有効な演算子は+、-、および*です。したがって、入力が「2 * 3-4 * 5」の場合、出力は[-34、-14、-10、-10、10]になります。これは-

• （2 *（3-（4 * 5）））=-34

• （（2 * 3）-（4 * 5））=-14

• （（2 *（3-4））* 5）=-10

• （2 *（（3-4）* 5））=-10

• （（（2 * 3）-4）* 5）=10

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

• メモと呼ばれる地図を定義します。

• Solve（）というメソッドを定義します。これにより、入力文字列が入力として使用されます。

• ret

  という配列を作成します

• メモに入力がある場合は、memo [input]

  を返します。

• 0から入力文字列のサイズまでの範囲のiの場合-

  • input [i]がサポートされている演算子の場合、

    • 配列part1：=solve（0からi-1までの入力の部分文字列）

    • 配列part2：=resolve（iから文字列の終わりまでの入力の部分文字列）

    • 0からpart1のサイズまでの範囲のjの場合

      • 0からpart2のサイズまでの範囲のkの場合

        • input [i]が加算の場合、

          • part [j] + part [k]を実行し、retに追加

        • input [i]が乗算の場合、

          • part [j] *part[k]を実行してretに追加

        • input [i]が減算の場合、

          • part [j]--part[k]を実行してretに追加

• retが空の場合、入力文字列を整数として返します

• memo [input]：=ret、return ret

例（C ++）

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

#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;
}
class Solution {
   public:
   map <string, vector<int>> memo;
   vector<int> diffWaysToCompute(string input) {
      vector <int> ret;
      if(memo.count(input)) return memo[input];
      for(int i = 0; i < input.size(); i++){
         if(input[i] == '+' || input[i] == '*' || input[i] == '-'){
            vector <int> part1 = diffWaysToCompute(input.substr(0, i));
            vector <int> part2 = diffWaysToCompute(input.substr(i + 1));
            for(int j = 0; j < part1.size(); j++ ){
               for(int k = 0; k < part2.size(); k++){
                  if(input[i] == '+'){
                     ret.push_back(part1[j] + part2[k]);
                  }
                  else if(input[i] == '*'){
                     ret.push_back(part1[j] * part2[k]);
                  } else {
                     ret.push_back(part1[j] - part2[k]);
                  }
               }
            }
         }
      }
      if(ret.empty()){
         ret.push_back(stoi(input));
      }
      return memo[input] = ret;
   }
};
main(){
   Solution ob;
   print_vector(ob.diffWaysToCompute("2*3-4*5"));
}

入力

"2*3-4*5"

出力

[-34, -10, -14, -10, 10, ]