在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的数组

• 如果备忘录已输入，则返回备忘录[输入]

• 对于范围在0到输入字符串大小的i-

• 数组part1：= solve（输入的子串从0到i-1）

• 数组part2：= solve（从i到字符串结尾的输入子字符串）

• 对于范围0到第1部分大小的j

• 如果输入[i]是加法，则

• 如果输入[i]是乘法，则

• 如果输入[i]是减法，则

• 执行part [j] + part [k]并添加到ret

• 执行part [j] * part [k]并添加到ret

• 执行part [j]-part [k]并添加到ret

• 对于范围0至第2部分大小的k

• 如果input [i]是任何受支持的运算符，则

• 如果ret为空，则以整数形式返回输入字符串

• memo [input]：= ret，然后返回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, ]