วิธีต่างๆ ในการเพิ่มวงเล็บใน 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

• หากบันทึกมีอินพุต ให้ส่งคืนบันทึก[input]

• สำหรับฉันในช่วง 0 ถึงขนาดของสตริงอินพุต -

  • หาก input[i] เป็นโอเปอเรเตอร์ที่รองรับแล้ว

    • อาร์เรย์ part1 :=แก้ (สตริงย่อยของอินพุตจาก 0 ถึง i - 1)

    • อาร์เรย์ part2 :=แก้ (สตริงย่อยของอินพุตจาก i ไปยังจุดสิ้นสุดของสตริง)

    • สำหรับ j ในช่วง 0 ถึงขนาดของ part1

      • สำหรับ k ในช่วง 0 ถึงขนาดของ part2

        • ถ้าอินพุต[i] เป็นส่วนเสริม ดังนั้น

          • ดำเนินการ part[j] + part[k] และเพิ่มลงใน ret

        • ถ้า input[i] เป็นการคูณ ดังนั้น

          • ดำเนินการ part[j] * part[k] และเพิ่มลงใน ret

        • ถ้า input[i] เป็นการลบ ดังนั้น

          • ดำเนินการ part[j] - part[k] และเพิ่มลงใน ret

• หาก 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, ]