Các cách khác nhau để thêm dấu ngoặc đơn trong C ++

Giả sử chúng ta có một chuỗi số và toán tử, chúng ta phải tìm tất cả các kết quả có thể có từ việc tính toán tất cả các cách có thể khác nhau để nhóm các số và toán tử. Ở đây các toán tử hợp lệ là +, - và *. Vì vậy, nếu đầu vào là “2 * 3-4 * 5”, thì đầu ra sẽ là [-34, -14, -10, -10, 10]. Điều này là do -

• (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

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một bản đồ được gọi là bản ghi nhớ.

• Định nghĩa một phương thức được gọi là giải quyết (). Thao tác này sẽ lấy chuỗi đầu vào làm đầu vào.

• tạo một mảng được gọi là ret

• nếu ghi nhớ có đầu vào, thì trả về ghi nhớ [input]

• cho tôi trong phạm vi 0 đến kích thước của chuỗi đầu vào -

  • nếu đầu vào [i] là bất kỳ toán tử nào được hỗ trợ thì

    • một mảng part1:=giải quyết (chuỗi con của đầu vào từ 0 đến i - 1)

    • một mảng part2:=giải quyết (chuỗi con của đầu vào từ i đến cuối chuỗi)

    • cho j trong phạm vi 0 đến kích thước của part1

      • cho k trong phạm vi 0 đến kích thước của part2

        • nếu đầu vào [i] là phần bổ sung thì

          • thực hiện part [j] + part [k] và thêm vào ret

        • nếu đầu vào [i] là phép nhân thì

          • thực hiện part [j] * part [k] và thêm vào ret

        • nếu đầu vào [i] là phép trừ thì

          • thực hiện part [j] - part [k] và thêm vào ret

• nếu ret trống, thì trả về chuỗi đầu vào dưới dạng số nguyên

• memo [input]:=ret, and return ret

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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"));
}

Đầu vào

"2*3-4*5"

Đầu ra

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