C ++中的表达式加运算符

假设我们有一个仅包含0到9之间数字的字符串,并且给出了一个目标值。我们必须返回所有可能的方法,以将二进制运算符+,-和*添加到数字中以获得目标值。因此,如果输入像“ 232”并且目标是8,则答案将是[“ 2 * 3 + 2”,“ 2 + 3 * 2”]

为了解决这个问题,我们将遵循以下步骤-

  • 定义一个名为的方法solve(),它将采用索引s,curr,target,temp,mult-

  • 如果idx> = s的大小,那么,

    • 在ret的末尾插入temp

    • 如果目标与curr相同,则

    • 返回

    • aux:=空字符串

    • 用于初始化i:= idx,当i <s的大小时,将i增加1做-

      • 调用solve(i + 1,s,curr + aux为整数,target,temp +“ +” + aux,aux为整数)

      • 调用solve(i + 1,s,curr-aux为整数,target,temp +“-” + aux,-aux为整数)

      • 调用solve(i + 1,s,curr-mult + mult * aux为整数,目标,温度+“ *” + aux,mult * aux为整数)

      • 调用solve(i + 1,s,aux为整数,target,aux,aux为整数)

      • 跳到下一个迭代,忽略后面的部分

      • aux = aux + s [i]

      • 如果aux [0]与'0'相同且aux> 1的大小,则

      • 如果idx与0相同,则

      • 除此以外

      • 从主要方法调用solve(0,num,0,target,空字符串,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, ]