Các cách đặt ngoặc khác nhau (Different Ways to Add Parentheses) trong C++

Mô tả bài toán

Cho biểu thức chuỗi chứa số và toán tử +, -, *. Tìm tất cả kết quả có thể được từ các cách đặt ngoặc khác nhau.

Ví dụ: "2*3-4*5" → [-34, -14, -10, -10, 10] (5 cách đặt ngoặc).

Giải thuật Chia để trị (Divide & Conquer) + Memoization

1. Duyệt chuỗi, tại mỗi toán tử op tại vị trí i:
   • Đệ quy tính tất cả kết quả của phần trái s[0..i-1].
   • Đệ quy tính tất cả kết quả của phần phải s[i+1..end].
   • Kết hợp: với mọi x trong trái, y trong phải, tính x op y.
2. Nếu chuỗi không có toán tử → chuyển thành số, trả về mảng 1 phần tử.
3. Dùng memoization (map string → vector) tránh tính lại.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

void print_vec(vector<int> v) {
    cout << "[";
    for (int x : v) cout << x << ", ";
    cout << "]" << endl;
}

class Solution {
    unordered_map<string, vector<int>> memo;
public:
    vector<int> diffWaysToCompute(string input) {
        if (memo.count(input)) return memo[input];
        vector<int> res;
        for (int i = 0; i < input.size(); i++) {
            char c = input[i];
            if (c == '+' || c == '-' || c == '*') {
                vector<int> left = diffWaysToCompute(input.substr(0, i));
                vector<int> right = diffWaysToCompute(input.substr(i + 1));
                for (int x : left) {
                    for (int y : right) {
                        if (c == '+') res.push_back(x + y);
                        else if (c == '-') res.push_back(x - y);
                        else res.push_back(x * y);
                    }
                }
            }
        }
        if (res.empty()) res.push_back(stoi(input));
        return memo[input] = res;
    }
};

int main() {
    Solution ob;
    print_vec(ob.diffWaysToCompute("2*3-4*5")); // [-34, -10, -14, -10, 10]
    return 0;
}

Độ phức tạp

• Thời gian: Số Catalan (số cách đặt ngoặc) × độ dài biểu thức. Với memo: O(n^3) xấp xỉ.
• Không gian: O(n^2) cho memo.