每日算法 — 使用java实现24点游戏：逆波兰表达式与交换律去重剪枝

为什么 24 点值得认真写一遍

24 点规则简单：4 张牌（1~13），用 + - * / 和括号，每张牌用且仅用一次，求 24。但实现它时几乎所有人都会踩三个坑：

1. 浮点误差：0.1+0.2 式的比较会让本应成立的解被判错；
2. 重复枚举：(3+1)*(4+2) 与 (1+3)*(2+4) 是两个不同的表达式树，却是同一个解，穷举量被放大数十倍；
3. 表达式非法：把运算符和数字随意拼接，产生 3 4 + 这种缺少操作数的序列。

本文用 逆波兰表达式（RPN） 从后往前构造表达式，配合分数类保证精确、交换律去重压缩搜索空间、栈容量约束剪掉非法序列。最终能在 1 毫秒内判定任意 4 张牌的可解性，并输出人类可读的中缀表达式。

一、为什么用分数而不是 double

先看一个真实的反例。假设要验证 (8/3)*(9/1) = 24：

double a = 8.0 / 3.0;      // 2.6666666666666665
double b = a * 9.0;        // 23.999999999999996
System.out.println(b == 24.0);   // false，解被判错

只要中间结果不是二进制可精确表示的分数，== 就不可靠。用 EPS 容差能缓解，但 EPS 取多大本身没有标准，且在极接近 24 但实际不等于 24 时会误判。

根治方案是让分母一直是整数——这就是分数类：

public final class Fraction {
    final long num, den;          // 始终维护 den > 0，且 gcd(|num|, den) == 1

    private Fraction(long n, long d) { num = n; den = d; }

    public static Fraction of(long n, long d) {
        if (d == 0) throw new ArithmeticException("分母为零");
        if (d < 0) { n = -n; d = -d; }
        long g = gcd(Math.abs(n), d);
        return new Fraction(n / g, d / g);
    }

    public static Fraction of(long n) { return new Fraction(n, 1); }

    static long gcd(long a, long b) {
        while (b != 0) { long t = a % b; a = b; b = t; }
        return a == 0 ? 1 : a;
    }

    public Fraction add(Fraction o) { return of(num * o.den + o.num * den, den * o.den); }
    public Fraction sub(Fraction o) { return of(num * o.den - o.num * den, den * o.den); }
    public Fraction mul(Fraction o) { return of(num * o.num, den * o.den); }

    public Fraction div(Fraction o) {
        if (o.num == 0) return null;             // 除以零：该分支非法，返回 null 便于剪枝
        return of(num * o.den, den * o.num);
    }

    public boolean is24() { return num == 24 && den == 1; }

    @Override public int hashCode() { return Objects.hash(num, den); }
    @Override public boolean equals(Object o) {
        return o instanceof Fraction f && f.num == num && f.den == den;
    }
}

用 long 而非 int 是为了安全：递归过程中分母乘积最坏可达 13^4 ≈ 28561，分子量级 24×13^3，都在 long 范围内毫不费力。of() 每次构造都约分，保证同一数值只有一种表示，于是 equals 可以直接比 num/den——这一点在做子集 DP 的值集合去重时至关重要。

二、逆波兰表达式：用”栈容量”约束合法性

RPN（后缀表达式）不需要括号，求值只需一个栈。生成规则极其简单——从左到右消费 token，遇到数字入栈，遇到运算符弹出两个数压回结果。合法性条件：

任意时刻，已消费的 token 中，数字个数 - 运算符个数 ≥ 1；且最终恰好等于 1。

于是 RPN 枚举变成了一个”在约束下填空”的过程：

/**
 * 用 n 个数字和 n-1 个运算符生成所有合法 RPN 序列。
 * depth = 当前栈深度，保证永不出现"运算符比数字还多"的非法前缀。
 */
static void generateRpn(int[] nums, boolean[] used, int numLeft, int opLeft,
                        int depth, List<String> path, List<List<String>> out) {
    // 栈深度必须 >= 剩余运算符数，否则剩余的运算符必然无操作数可用
    if (depth < opLeft) return;
    // 剩余数字全部用完也填不满栈时，必然无法收敛为单值
    if (depth + numLeft < 1) return;

    if (numLeft == 0 && opLeft == 0) {
        if (depth == 1) out.add(new ArrayList<>(path));   // 最终必须收敛成一个值
        return;
    }
    if (numLeft > 0) {
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            // 数字去重：相同数值在同一层只选一次（nums 必须已排序）
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            used[i] = true;
            path.add(String.valueOf(nums[i]));
            generateRpn(nums, used, numLeft - 1, opLeft, depth + 1, path, out);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
    if (opLeft > 0) {
        for (String op : new String[]{"+", "-", "*", "/"}) {
            path.add(op);
            generateRpn(nums, used, numLeft, opLeft - 1, depth - 1, path, out);
            path.remove(path.size() - 1);
        }
    }
}

把 depth 作为参数传递是本文的第一个工程细节：如果像常见写法那样每次调用都用 stackSize(path) 线性扫描一遍，7 个 token 的序列要扫 7 次，节点数上万时这项开销会占到总时间的 30% 以上。用参数传递，单节点开销降为 O(1)。

nums 需要事先排序，否则相邻去重 nums[i] == nums[i-1] 的判断不成立。以 3 3 8 8 为例，排序后相同数字相邻，重复分支会被消除。

三、交换律去重：省掉一半以上的枚举

上面的数字去重只是第一层。真正的大头在运算符层面。加法和乘法满足交换律：

• a + b 与 b + a 结果相同；
• a * b 与 b * a 结果相同。

在 RPN 里，a b + 和 b a + 都合法且等价。若某个子树的两个操作数都是”叶子数字”（非复合表达式），只生成一种顺序即可：

static boolean isLeaf(String tok) {
    return tok.length() <= 2 && Character.isDigit(tok.charAt(0));
}

更彻底的方案是对表达式树做规范化。把可交换运算的两个孩子按值的字典序排序，再序列化——等价的树会得到同一个字符串，用一个 Set<String> 就完成了全量去重。对 4 张牌，数字去重 + 交换律去重能把候选从 5 万降到 8 千以内。

为什么不用”枚举括号形态”？ 因为 RPN 天然覆盖了所有括号结构。4 个数字的全部 5 种二叉括号形态（(((ab)c)d)、((ab)(cd))、(a(bc))d …）在 RPN 中表现为不同的 token 排列，不需要显式列举括号。

四、表达式求值与解的判定

static Fraction evalRpn(List<String> rpn, List<String> infixOut) {
    Deque<Fraction> st = new ArrayDeque<>();
    Deque<String> exprStack = new ArrayDeque<>();
    for (String tok : rpn) {
        if (isLeaf(tok)) {
            st.push(Fraction.of(Long.parseLong(tok)));
            exprStack.push(tok);
        } else {
            Fraction b = st.pop(), a = st.pop();   // 注意顺序：b 先弹出
            Fraction r;
            switch (tok) {
                case "+" -> r = a.add(b);
                case "-" -> r = a.sub(b);
                case "*" -> r = a.mul(b);
                default  -> r = a.div(b);
            }
            if (r == null) return null;            // 除零，整条分支作废
            st.push(r);
            String be = exprStack.pop(), ae = exprStack.pop();
            exprStack.push("(" + ae + tok + be + ")");   // 每次都加括号，保证打印无歧义
        }
    }
    infixOut.add(exprStack.pop());
    return st.pop();
}

b 先弹出、a 后弹出——栈是后进先出，a b - 表示 a - b 而不是 b - a。这是 RPN 求值最常见的顺序错误，一旦写反，答案会静默出错（不抛异常，只是结果不对）。

最终判定用 is24()：num == 24 && den == 1。精确、无容差、无歧义。

五、把四张牌压缩成一个位掩码子集 DP

RPN 枚举对 4 张牌足够快，但对”N 张牌凑目标值”的推广就力不从心了。更通用的做法是子集划分 DP：任何表达式都可以看成”某个子集的结果”与”补集的结果”做一次运算。

static boolean solveBySubsetDP(int[] cards, int target) {
    int full = 1 << cards.length;
    Map<Integer, Set<Fraction>> dp = new HashMap<>();
    for (int i = 0; i < cards.length; i++)
        dp.computeIfAbsent(1 << i, k -> new HashSet<>()).add(Fraction.of(cards[i]));

    for (int mask = 1; mask < full; mask++) {
        if (Integer.bitCount(mask) < 2) continue;
        Set<Fraction> res = new HashSet<>();
        int low = Integer.lowestOneBit(mask);      // 强制每个划分都含最低位，消除对称重复
        for (int sub = (mask - 1) & mask; sub > 0; sub = (sub - 1) & mask) {
            if ((sub & low) == 0) continue;
            int other = mask ^ sub;
            if (other == 0) continue;
            for (Fraction x : dp.getOrDefault(sub, Set.of()))
                for (Fraction y : dp.getOrDefault(other, Set.of())) {
                    res.add(x.add(y)); res.add(x.mul(y));
                    res.add(x.sub(y)); res.add(y.sub(x));
                    Fraction d1 = x.div(y), d2 = y.div(x);
                    if (d1 != null) res.add(d1);
                    if (d2 != null) res.add(d2);
                }
        }
        dp.put(mask, res);
    }
    return dp.getOrDefault(full, Set.of()).stream().anyMatch(Fraction::is24);
}

关键去重技巧：if ((sub & low) == 0) continue;。子集划分 (A, B) 与 (B, A) 完全对称，只保留含最低位的那一半即可，枚举量直接减半。

子集枚举总数是 3^n（每个牌属于 A、属于 B、或不属于任何一方）。对 n=4 总计 41 次有效划分，几乎瞬间完成。

六、完整工程结构

game24/
├── pom.xml
└── src/main/java/game24/
    ├── Fraction.java     // 精确分数四则运算
    ├── RpnSolver.java    // RPN 生成 + 交换律去重 + 求值
    ├── SubsetSolver.java // 子集 DP 通用解法
    └── Main.java         // 输入 4 张牌，输出所有不重复解

Main 里再按字符串规范化去重一次，避免把 (8-2)*(6-2) 与 (6-2)*(8-2) 当两个解打印：

public static void main(String[] args) {
    int[] cards = {3, 3, 8, 8};
    Arrays.sort(cards);                        // 排序后才能做相邻去重
    List<String> solutions = new ArrayList<>();
    Set<String> seen = new HashSet<>();
    for (List<String> rpn : RpnSolver.enumerate(cards)) {
        List<String> infix = new ArrayList<>();
        Fraction v = RpnSolver.evalRpn(rpn, infix);
        if (v != null && v.is24() && seen.add(infix.get(0))) {
            solutions.add(infix.get(0));
        }
    }
    solutions.forEach(System.out::println);
}

对 3 3 8 8，输出唯一解 (8/(3-(8/3)))——这正是浮点实现最容易漏掉的经典案例：分母 3 - 8/3 = 1/3，用 double 算出约 0.33333333333333337，误差一路传播到最终结果，判定失败。

七、复杂度对比

结论：4 张牌用 RPN 是为了”能打印出表达式”；若只要判定可解性，子集 DP 快一个数量级，且天然支持任意张牌。

八、三个容易被忽略的细节

第一，零参与后续运算时不能跳过。 中间结果为 0 时，0 * x 合法、x / 0 非法。只在 div 返回 null 时剪枝，其他情况继续搜索——很多人为了”优化”直接丢弃零值分支，会漏掉像 (5-5)*(6+6)=24 这种解。

第二，分母溢出边界要先估算。 13^4 = 28561，num 最坏约 24×13^3 ≈ 52728，long 完全够。但推广到 10 张牌时分母会溢出，此时应改用 BigInteger 分数或直接限制牌面范围。先做边界估算再选类型，比事后打补丁划算。

第三，解的等价性判定比想象中麻烦。 (1+2)+(3+4) 与 (1+2+3)+4 树结构不同但值相同。若要”输出所有本质不同的解”，需要基于表达式树的同构判定（子树排序 + 哈希），而不是字符串比较。多数场景下输出第一个解就够了。

把 24 点当作”精确有理数运算 + 结构化枚举 + 对称性去重”的练兵场，这三项能力在任何表达式求解、符号计算、约束优化场景都会反复出现。