24點撲克牌遊戲算法實現：窮舉搜索 + 逆波蘭式

問題建模

給定 4 個整數（1~9），用 + - * / 和括號構成表達式，判斷能否得 24。推廣到任意 4 整數、任意目標值。

三步走策略

1. 數字全排列：4 個數共有 P(4,4)=24 種排列（去重後更少）
2. 運算符組合：3 個運算符位置，每位 4 選 1 → 4³=64 種
3. 括號/優先級處理：引入後綴表達式（逆波蘭式 RPN）消除括號與優先級

逆波蘭式求值

中綴 ((1+2)+3)*4 → 後綴 1 2 + 3 + 4 *

棧式求值算法：

• 遇數字 → 入棧
• 遇運算符 → 彈出兩數運算，結果入棧
• 最終棧頂即結果

搜索樹構建：遞歸生成所有合法 RPN

狀態：(剩餘數字隊列, 剩餘運算符隊列, 當前棧)

遞歸分支：

1. 做運算：若棧≥2 且有剩餘運算符 → 彈出兩數、取運算符、算、結果入棧、遞歸
2. 進數字：若有剩餘數字 → 取數字入棧、遞歸

終止條件：運算符用盡、數字用盡、棧剩 1 個元素 → 比對目標值。

核心代碼

#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <algorithm>
#include <cmath>

#define OP_SIZE 4
#define TARGET 24
#define EQ(a,b) (fabs((a)-(b)) < 1e-5)

char ops_char[OP_SIZE] = {'+','-','*','/'};
std::vector<std::string> solutions;

void solve_rpn(std::stack<double>& st, std::queue<int>& q,
               std::vector<int> nums, std::vector<char> ops) {
    if (ops.empty()) {
        if (nums.empty() && st.size()==1 && EQ(st.top(), TARGET)) {
            std::string s;
            while (!q.empty()) { s += char(q.front()); q.pop(); }
            solutions.push_back(s);
        }
        return;
    }

    auto save = [&](auto& v) { return v; };  // 複製狀態

    // 分支 1：做運算
    if (st.size() >= 2) {
        auto st2 = st, q2 = q, ops2 = ops;
        double b = st2.top(); st2.pop();
        double a = st2.top(); st2.pop();
        char op = ops2.front(); ops2.erase(ops2.begin());
        double r = 0;
        switch (op) {
            case '+': r = a + b; break;
            case '-': r = a - b; break;
            case '*': r = a * b; break;
            case '/': if (!EQ(b,0)) r = a / b; else return;
        }
        st2.push(r);
        q2.push(op);
        solve_rpn(st2, q2, nums, ops2);
    }

    // 分支 2：進數字
    if (!nums.empty()) {
        auto st2 = st, q2 = q, nums2 = nums;
        int val = nums2.front(); nums2.erase(nums2.begin());
        st2.push(val);
        q2.push(val + '0');  // 單位數字轉字符
        solve_rpn(st2, q2, nums2, ops);
    }
}

void search(std::vector<int> nums, int pos, std::vector<char> ops) {
    if (pos == nums.size() - 1) {
        std::stack<double> st;
        std::queue<int> q;
        solve_rpn(st, q, nums, ops);
        return;
    }
    for (int i = pos; i < nums.size(); ++i) {
        // 去重：同層遞歸中相同數字只用第一個
        bool dup = false;
        for (int k = pos; k < i; ++k) if (nums[k] == nums[i]) { dup = true; break; }
        if (dup) continue;
        std::swap(nums[pos], nums[i]);
        for (char op : ops_char) {
            ops.push_back(op);
            search(nums, pos+1, ops);
            ops.pop_back();
        }
        std::swap(nums[pos], nums[i]);
    }
}

int main() {
    std::vector<int> nums = {1,2,3,4};
    search(nums, 0, {});
    for (auto& s : solutions) std::cout << s << '\n';
    return 0;
}

關鍵優化點

• 數字去重：避免 {1,5,5,5} 產生重複排列
• 浮點數比較：用 EPS 判等，避免精度問題
• 除零保護：除數接近 0 時剪枝
• RPN 合法性隱式保證：棧深度檢查確保運算時有足夠操作數

擴展方向

1. 支持多位數：隊列存 string 而非 char
2. 輸出中綴表達式：RPN → 語法樹 → 中綴打印（加括號）
3. 任意 N 數字：排列 + 運算符組合 + RPN 搜索通用化
4. 剪枝優化：預估剩餘數字能達到的值域範圍，提前終止