Tìm tất cả kết quả có thể của biểu thức số học trong C++

Cho biểu thức số học không có dấu ngoặc. Tìm tất cả các giá trị có thể thu được bằng cách đặt ngoặc khác nhau. Ví dụ: 1+2*3-4 có các kết quả: -1, -3, 3, 5, 3.

Đệ quy: Với mỗi toán tử, tách biểu thức thành hai phần trái/phải. Đệ quy tính tất cả giá trị của phần trái (L) và phần phải (R). Kết hợp mọi cặp (l ∈ L, r ∈ R) bằng toán tử hiện tại.

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> evaluateAll(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<int> 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 = evaluateAll(expr, 0, expr.length() - 1);
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << endl;
}

Kết quả