หาผลลัพธ์ทั้งหมดที่เป็นไปได้ของนิพจน์คณิตศาสตร์โดยไม่มีวงเล็บใน C++

นิพจน์คณิตศาสตร์โดยไม่มีวงเล็บ เช่น "1+2*3-4" สามารถตีความได้หลายแบบ ต้องการหาผลลัพธ์ทั้งหมดที่เป็นไปได้

ตัวอย่าง 1+2*3-4 มีผลลัพธ์ที่เป็นไปได้:

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

อัลกอริทึม (Divide & Conquer)

สำหรับตัวดำเนินการแต่ละตัวในนิพจน์
คำนวณผลลัพธ์ทั้งหมดทางด้านซ้าย (L) และขวา (R) แบบ Recursive
นำค่าใน L และ R มารวมกันด้วยตัวดำเนินการปัจจุบัน
รวบรวมผลลัพธ์ทั้งหมด

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

#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;
    return 0;
}

vector evaluateAll(string expr, int low, int high) {
    vector 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 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++)
                res.push_back(solve(L[s1], expr[i], R[s2]));
    }
    return res;
}

int main() {
    string expr = "1+2*3-4";
    vector ans = evaluateAll(expr, 0, expr.length() - 1);
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << endl;
    return 0;
}

ผลลัพธ์

หมายเหตุ

โค้ดต้นฉบับมีฟังก์ชันชื่อ getAllResults เรียก evaluateAll ซึ่งไม่ได้ประกาศ เราแก้ไขให้เรียกตัวเอง (Recursive) โดยตรง