Tìm tất cả các kết quả có thể có của một biểu thức nhất định trong C ++

Giả sử chúng ta có một biểu thức số học không có dấu ngoặc đơn. Nhiệm vụ của chúng ta là tìm ra tất cả các kết quả có thể có của biểu thức đó. Giả sử biểu thức giống như 1 + 2 * 3-4, điều này có thể được hiểu như bên dưới -

• 1+ (2 * (3-4)) =1 + (2 * -1) =-1
• (1 + 2) * (3-4) =3 * -1 =-3
• 1 + ((2 * 3) -4) =1 + (6 - 4) =3
• ((1 + 2) * 3) -4 =(3 * 3) - 4 =5
• 1+ (2 * 3) -4 =1 + 6 - 4 =3

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

• Ban đầu, đặt res là trống

• Đối với mọi toán tử x, hãy thực hiện như sau -

  • Đánh giá đệ quy tất cả các giá trị có thể có ở bên trái của x, để danh sách các giá trị là L

  • Đánh giá đệ quy tất cả các giá trị có thể có ở bên phải của x, để danh sách các giá trị là R

  • Lặp qua tất cả các giá trị trong L:

    • Lặp qua tất cả các giá trị trong R−

      • Áp dụng toán tử hiện tại x trên phần tử hiện tại trong L và R, đồng thời thêm các giá trị đã đánh giá vào res

• trả về res dưới dạng đầu ra

Ví dụ

#include<iostream>
#include<vector>
using namespace std;
int solve(int a, char op, int b) {
   if (op=='+')
      return a+b;
   if (op=='-')
      return a-b;
   if (op == '*')
      return a*b;
}
vector<int> getAllResults(string expr, int low, int high) {
   vector<int> res;
   if (low == high) {
      res.push_back(expr[low] - '0');
      return res;
   }
   if (low == (high-2)) {
      int num = solve(expr[low]-'0', expr[low+1], expr[low+2]-'0');
      res.push_back(num);
      return res;
   }
   for (int i=low+1; i<=high; i+=2) {
      vector<int> L = evaluateAll(expr, low, i-1);
      vector R = evaluateAll(expr, i+1, high);
      for (int s1=0; s1<L.size(); s1++) {
         for (int s2=0; s2<R.size(); s2++) {
            int val = solve(L[s1], expr[i], R[s2]);
            res.push_back(val);
         }
      }
   }
   return res;
}
int main() {
   string expr = "1+2*3-4";
   vector<int> ans = getAllResults(expr, 0, expr.length()-1);
   for (int i=0; i< ans.size(); i++)
      cout << ans[i] << endl;
}

Đầu ra

2 1 4 3 5 6 7 8