วิธีการวางวงเล็บต่างกันใน C++

ให้สตริงประกอบด้วยตัวเลขและตัวดำเนินการ +, -, * หาผลลัพธ์ทั้งหมดที่เป็นไปได้จากการวางวงเล็บต่างกัน (Different Ways to Add Parentheses)

ตัวอย่าง: "2*3-4*5" → [-34, -14, -10, -10, 10]

ขั้นตอนการแก้ปัญหา (Divide & Conquer + Memoization)

1. Memoization map memo[string] → vector
2. ฟังก์ชัน solve(input):
   • ถ้าใน memo → คืนทันที
   • วนหาตัวดำเนินการใน input:
     • แบ่งเป็น left = solve(input[0..i-1]), right = solve(input[i+1..])
     • รวมทุกคู่: left[j] op right[k] ใส่ผลลัพธ์
   • ถ้าไม่มีตัวดำเนินการ (แค่ตัวเลข) → คืน {stoi(input)}
   • บันทึก memo และคืน

ตัวอย่างโค้ด C++

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

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

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

int main() {
    Solution ob;
    print_vector(ob.diffWaysToCompute("2*3-4*5"));
}

Input

"2*3-4*5"

Output

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