24點遊戲核心算法實現：窮舉排列組合與表達式解析器的 Java 實戰

前言

「24點」是經典數學遊戲：給定 4 個數字，使用 + - * / 和括號運算得出 24。本文深度解析遊戲核心邏輯 —— 如何判斷 4 個數能否算出 24，以及 如何驗證用戶輸入表達式的合法性與計算結果。代碼採用「預計算所有可解組合 + 表達式語法分析」雙軌制，邏輯嚴密，適合算法入門與編譯原理初探。

一、核心類設計：Check

封裝三大核心能力：

1. 數字全排列生成：4! = 24 種順序，硬編碼避免遞歸開銷。
2. 運算符全排列生成：4³ = 64 種組合（三個運算位，各 4 選 1）。
3. 五種括號結構窮舉計算：覆蓋所有合法二元樹結構。

1. 數字排列

private float[] number(float[] a, int i) {
    final float[] arr = new float[4];
    // switch-case 硬編碼 24 種排列，i=0..23
    // 例：case 0: a[0],a[1],a[2],a[3]; case 1: a[0],a[1],a[3],a[2] ...
    return arr;
}

2. 運算符排列

private char[][] Calculate() {
    char[][] ops = new char[64][3];
    int[][] idx = new int[64][3];
    int t = 0;
    for (int i=0;i<4;i++) for (int j=0;j<4;j++) for (int k=0;k<4;k++) {
        idx[t][0]=i; idx[t][1]=j; idx[t][2]=k;
        for (int l=0;l<3;l++) ops[t][l] = mapOp(idx[t][l]); // 0:+,1:-,2:*,3:/
        if (++t == 64) return ops;
    }
    return ops;
}

3. 五種括號結構（二元樹形態）

對於 4 個數 a,b,c,d 和 3 個運算符 op1,op2,op3，合法括號化對應 5 種二元樹結構：

1. ((a op1 b) op2 c) op3 d — 左傾鏈
2. (a op1 b) op2 (c op3 d) — 平衡雙分支
3. (a op1 (b op2 c)) op3 d — 右子樹優先
4. a op1 ((b op2 c) op3 d) — 右側左傾
5. a op1 (b op2 (c op3 d)) — 右傾鏈

代碼中依次計算，任一結果 == 24 即返回 true 並記錄表達式字符串 outputs。

4. 基礎運算單元

private float Run(float a, float b, char op) {
    switch(op) { case '+': return a+b; case '-': return a-b; case '*': return a*b; case '/': return a/b; }
    return 0;
}

二、用戶表達式驗證與計算：string_float

採用語法分析 + 優先級計算 兩階段：

階段 1：詞法掃描與合法性校驗

• 提取 4 個數字、3 個運算符、括號位置。
• 校驗：數字必須與發牌數字一致（順序無關）、運算符數量=3、括號匹配且位置合法（左括號只能在運算符/數字前，右括號只能在運算符/數字後）。

階段 2：優先級確定與計算

根據括號層級、乘除優先於加減，為 3 個運算符分配優先級 1/2/3，構成 3 位數編碼 abc（如 321 表示第3運算符優先級最高）。通過 switch(abc) 直接映射到 6 種計算順序（對應上述 5 種括號結構 + 1 種無括號左結合）。

// 例：優先級編碼 321 -> 計算順序對應 ((a op1 b) op2 c) op3 d
case 321: return Run(Run(Run(n[0],n[1],op[0]),n[2],op[1]),n[3],op[2]);

三、界面交互模組（節選）

• MsgDlg/MasgDlg：結果彈窗（成功/失敗/超時），控制「確定」「重新開始」按鈕狀態。
• MyTimer：Swing Timer 實現分鐘:秒 計時顯示。

四、算法複雜度與優化方向

優化建議：

• 使用 double 替代 float 減少精度誤差（如 8/(3-8/3)=24 含循環小數）。
• 引入表達式樹 / Shunting-yard 算法替代硬編碼 switch，支持任意長度表達式。
• 緩存所有 4 數組合的可解表達式，發牌直接查表 O(1)。

總結

本項目展示了「組合窮舉 + 語法分析」解決約束求解問題的經典模式：

1. 領域建模：數字排列、運算符排列、括號結構 → 狀態空間完備覆蓋。
2. 工程落地：硬編碼常數空間換時間、雙軌驗證（系統預解 + 用戶輸入解析）。
3. 擴展性：可遷移至 N 數字、任意目標值、自定義運算符的通用表達式求解器。

完整源碼下載：https://down.51cto.com/data/318971