24点游戏解法

如果说工作是为了更好地玩，那当玩的不开心时，比如24点，还是要用工作技能去处理，下面代码质量不高，纯属娱乐，欢迎指点批评：

public class Main {
 
    private static final double TARGET=24;
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] nums = Arrays.stream(in.nextLine().split(" ")).mapToInt(
                                 Integer::parseInt).toArray();
 
        ScriptEngine nashorn = new ScriptEngineManager().getEngineByName("nashorn");
        Main m = new Main();
        // 15<=>1111
        System.out.println(m.dfs(nums, new ArrayList<>(), 15, nashorn));
    }
 
    /**
     *
     * @param nums
     * @param formula   list 存储表达式子项，之所有选用 List 是为了兼容数字大于9的情况
     * @param selected  记录选择标志位
     * @param nashorn
     * @return
     */
    public boolean dfs(int[] nums, List formula, int selected, ScriptEngine nashorn) {
        if (selected == 0) {
            if (formula.size() < 7) {
                return false;
            }
            // todo test
//            System.out.println("complete formula: " + formula);
            String f = found24(formula, nashorn);
            boolean b = !f.isEmpty();
            if (b) {
                System.out.println(f);
            }
            return b;
        }
        boolean ret = false;
        for (int i = 0; i < nums.length; ++i) {
            int select = nums[i];
            int newSelect = setI(i, selected);
            if (selected == 15) {//1111
                formula.add(String.valueOf(select));
                if (!(ret |= dfs(nums, formula, newSelect, nashorn))) {
                    formula.remove(formula.size() - 1);
                    continue;
                }else{
                    return true;
                }
            }
            if (!checkI(i, selected)) {
                continue;
            }
            // addition
            formula.add("+");
            formula.add(String.valueOf(select));
            ret |= dfs(nums, formula, newSelect, nashorn);
            if (!ret) {
                formula.remove(formula.size() - 1);
                formula.remove(formula.size() - 1);
            } else {
                return true;
            }
            // subtraction
            formula.add("-");
            formula.add(String.valueOf(select));
            ret |= dfs(nums, formula, newSelect, nashorn);
            if (!ret) {
                formula.remove(formula.size() - 1);
                formula.remove(formula.size() - 1);
            } else {
                return true;
            }
            // multiplication
            formula.add("*");
            formula.add(String.valueOf(select));
            ret |= dfs(nums, formula, newSelect, nashorn);
            if (!ret) {
                formula.remove(formula.size() - 1);
                formula.remove(formula.size() - 1);
            } else {
                return true;
            }
            // division
            formula.add("/");
            formula.add(String.valueOf(select));
            ret |= dfs(nums, formula, newSelect, nashorn);
            if (!ret) {
                formula.remove(formula.size() - 1);
                formula.remove(formula.size() - 1);
            } else {
                return true;
            }
        }
        return false;
    }
 
    /**
     * 校验（从右到左）第 i 位是否为1
     * @param i
     * @param selected
     * @return
     */
    public boolean checkI(int i, int selected) {
        return ((selected >> i) & 1) == 1;
    }
 
    /**
     * 从右到左 第 i 位置为0
     * @param i
     * @param selected
     * @return
     */
    public int setI(int i, int selected) {
        int c = ~(1 << i);
        return selected & c;
    }
 
    /**
     * 枚举各种括号，找出带括号计算后可以得到 24 点的表达式
     * @param formula   包含表达式符号的集合
     * @param nashorn
     * @return          可得 24 点的表达式
     */
    public String found24(List formula, ScriptEngine nashorn) {
        boolean ret = checkValue(calc(formula, nashorn) ,TARGET);
        if (ret) {
            return buildFormula(formula, null);
        }
        ArrayList tempFormu = new ArrayList<>();
        // (AB)CD A(BC)D AB(CD)
        for (int i = 0; i < 3; ++i) {
            int end = 3 + i * 2;
            int start = end - 3;
            // 拼接表达式，一下类似，不重复注释
            tempFormu.addAll(formula.subList(0, start));
            tempFormu.add("("+String.valueOf(calc(formula.subList(start, end), nashorn)) + ")");
            tempFormu.addAll(formula.subList(end, 7));
 
            ret = checkValue(calc(tempFormu,nashorn),TARGET);
            if (ret) {
                return buildFormula(formula, Arrays.asList(Arrays.asList(start, end)));
            }
            tempFormu.clear();
        }
        // (AB)(CD)
        tempFormu.add("("+String.valueOf(calc(formula.subList(0, 3), nashorn)) + ")");
        tempFormu.addAll(formula.subList(3, 4));
        tempFormu.add("("+String.valueOf(calc(formula.subList(4, 7), nashorn))+")");
        ret = checkValue(calc(tempFormu,nashorn),TARGET);
 
        tempFormu.clear();
        if (ret) {
            return buildFormula(formula, Arrays.asList(Arrays.asList(0, 3), Arrays.asList(4, 7)));
        }
        // (ABC)D A(BCD)
        for (int i = 0; i < 2; ++i) {
            int end = 5 + i * 2;
            int start = end - 5;
            tempFormu.addAll(formula.subList(0, start));
            tempFormu.add("("+String.valueOf(calc(formula.subList(start, end), nashorn))+")");
            tempFormu.addAll(formula.subList(end, 7));
            ret = checkValue(calc(tempFormu,nashorn),TARGET);
            tempFormu.clear();
            if (ret) {
                return buildFormula(formula, Arrays.asList(Arrays.asList(start, end)));
            }
        }
        return "";
    }
 
    /**
     * 校验值 误差 < 1e-6
     * @param value
     * @param target
     * @return
     */
    public boolean checkValue(double value, double target){
        return Math.abs(target-value)<1e-6;
    }
 
    /**
     * 构建公式的字符串表达式（含有符号）
     * @param formulas
     * @param idxes     插入括号的下标（两层为了兼容双括号 (AB)(CD)）
     * @return
     */
    public String buildFormula(List formulas, List> idxes) {
        if (idxes == null) {
            return formulas.stream().collect(Collectors.joining());
        }
        StringBuilder formula = new StringBuilder();
 
        List ids = idxes.get(0);
        if (idxes.size() == 1) {
            List l1 = formulas.subList(0, ids.get(0));
            List l2 = formulas.subList(ids.get(0), ids.get(1));
            List l3 = formulas.subList(ids.get(1), 7);
            formula.append(l1.stream().collect(Collectors.joining()));
            formula.append("(" + l2.stream().collect(Collectors.joining()) + ")");
            formula.append(l3.stream().collect(Collectors.joining()));
        } else {//双括号只有一种可能
            List l1 = formulas.subList(ids.get(0), ids.get(1));
            List l2 = formulas.subList(idxes.get(1).get(0), idxes.get(1).get(1));
            formula.append("(" + l1.stream().collect(Collectors.joining()) + ")");
            formula.append(formulas.get(3));
            formula.append("(" + l2.stream().collect(Collectors.joining()) + ")");
        }
        return formula.toString();
    }
 
    public double calc(List formula0, ScriptEngine nashorn) {
        try {
            String formula = formula0.stream().collect(Collectors.joining());
            // todo Test
//            System.out.println("calculating : " + formula);
            Object result = nashorn.eval(formula);
            if (result instanceof Integer) {
                return (Integer) result;
            }
            if (result instanceof Double) {
                double d = (Double) result;
                return d;
            }
            return 0;
        } catch (ScriptException e) {
            return 0;
        }
    }
}

一般的算法练习，会让你校验，数字是否满足 24 点规则，参考leetcode679.

牛客上也有相关题目 HJ67，只不过是用例不全的阉割版，用半成品算法也能通过，参考我这篇

靠着上述代码，总算通关了 24 点游戏 160+32 个关卡，姑且一乐，需者自取。