นิพจน์เพิ่มตัวดำเนินการใน C++

สมมติว่าเรามีสตริงที่เก็บเฉพาะตัวเลขตั้งแต่ 0 ถึง 9 และให้ค่าเป้าหมายหนึ่งค่า เราต้องคืนค่าความเป็นไปได้ทั้งหมดเพื่อเพิ่มตัวดำเนินการไบนารี +, - และ * ลงในตัวเลขเพื่อรับค่าเป้าหมาย ดังนั้นหากอินพุตเป็น “232” และเป้าหมายคือ 8 คำตอบจะเป็น [“2*3+2”, “2+3*2”]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดวิธีการที่เรียกว่า Solve() ซึ่งจะใช้ index, s, curr, target, temp, mult -

• ถ้า idx>=ขนาดของ s แล้ว

  • ถ้าเป้าหมายเหมือนกับ curr แล้ว

    • ใส่ temp ที่ท้าย ret

  • กลับ

• aux :=สตริงว่าง

• สำหรับการเริ่มต้น i :=idx เมื่อ i

  • aux =aux + s[i]

  • ถ้า aux[0] เหมือนกับ '0' และขนาดของ aux> 1 แล้ว

    • ข้ามไปยังการวนซ้ำถัดไป ละเว้นส่วนต่อไปนี้

  • ถ้า idx เท่ากับ 0 แล้ว

    • แก้การโทร (i + 1, s, aux เป็นจำนวนเต็ม, เป้าหมาย, aux, aux เป็นจำนวนเต็ม)

  • มิฉะนั้น

    • call Solve (i + 1, s, curr + aux เป็นจำนวนเต็ม, เป้าหมาย, temp + " + " + aux, aux asinteger)

    • แก้การโทร (i + 1, s, curr - aux เป็นจำนวนเต็ม, เป้าหมาย, temp + " - " + aux, - aux asinteger)

    • แก้การโทร (i + 1, s, curr - mult + mult * aux เป็นจำนวนเต็ม, เป้าหมาย, temp + " * " +aux, mult * aux เป็นจำนวนเต็ม)

• จากการเรียกเมธอดหลัก แก้(0, num, 0, เป้าหมาย, สตริงว่าง, 0)

• รีเทิร์น

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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, ]