使用DFS求解“扑克牌24点游戏算法”

1.题目描述

计算24点是一种扑克牌益智游戏，随机抽出4张扑克牌，通过加(+)，减(-)，乘(*), 除(/)四种运算法则计算得到整数24，本问题中，扑克牌通过如下字符或者字符串表示，其中，小写joker表示小王，大写JOKER表示大王：
3 4 5 6 7 8 9 10 J Q K A 2 joker JOKER

本程序要求实现：输入4张牌，输出一个算式，算式的结果为24点。

详细说明：

1.运算只考虑加减乘除运算，没有阶乘等特殊运算符号，友情提醒，整数除法要当心；
2.牌面210对应的权值为210, J、Q、K、A权值分别为为11、12、13、1；
3.输入4张牌为字符串形式，以一个空格隔开，首尾无空格；如果输入的4张牌中包含大小王，则输出字符串“ERROR”，表示无法运算；
4.输出的算式格式为4张牌通过+-/四个运算符相连，中间无空格，4张牌出现顺序任意，只要结果正确；
5.输出算式的运算顺序从左至右，不包含括号，如1+2+34的结果为24
6.如果存在多种算式都能计算得出24，只需输出一种即可，如果无法得出24，则输出“NONE”表示无解。

2.分析

这道题跟第67题 有两个地方不同。

• （1） 这道题要打印出计算式
• （2） 这道题要进行字符和数字间的转换，如A转换成1进行计算，输出的时候再把1转成A输出。

在第67题的基础上，（第67题的解法点击这里 ），我们可以新加入一个栈来纪录数字和操作符。最后在将栈打印出来。

3.具体代码

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        out: // 定义外部循环别名
        while (scanner.hasNextLine()) {
            // 初始化数字数组和标志数组以及栈
            String[] split = scanner.nextLine().split(" ");
            int[] nums = new int[4];
            int[] signs = new int[4];
            Stack<Object> stack = new Stack<>();
            for (int i = 0; i < nums.length; i++) {
                int num = str2Num(split[i]); // 字符转数字
                // 如果有鬼牌，输出ERROR，结束处理
                if (num == -1) {
                    System.out.println("ERROR");
                    continue out;
                }
                nums[i] = num;
            }

            for (int i = 0; i < nums.length; i++) {
                signs[i] = 1;
                stack.push(nums[i]);
                if (dfs(nums, signs, nums[i], 24, stack)) {
                    break;
                }
                signs[i] = 0;
                stack.pop();
            }

            if (stack.isEmpty()) {
                System.out.println("NONE");// 如果无法得到24，输出NONE
            } else {
                for (Object o : stack) {
                    if (o instanceof Integer) {
                        o = num2Str((int) o);// 数字转字符
                    }
                    System.out.print(o);
                }
                System.out.println();
            }
        }
    }

    private static boolean dfs(int nums[], int[] signs, int v, int required, Stack<Object> stack) {
        boolean allVisited = true;// 四个角均被访问
        for (int sign : signs) {
            if (sign == 0) {
                allVisited = false;
            }
        }

        if (allVisited) {
            return v == required; // 在所有节点均被访问的前提下，判断最后的结果是否为所需要的结果。
        }

        // 访问所有的邻接顶点
        for (int i = 0; i < nums.length; i++) {
            if (signs[i] == 0) {
                signs[i] = 1;

                // 加法
                stack.push("+");
                stack.push(nums[i]);
                if (dfs(nums, signs, v + nums[i], required, stack)) {
                    return true;
                }
                stack.pop();
                stack.pop();

                // 减法
                stack.push("-");
                stack.push(nums[i]);
                if (dfs(nums, signs, v - nums[i], required, stack)) {
                    return true;
                }
                stack.pop();
                stack.pop();

                // 乘法
                stack.push("*");
                stack.push(nums[i]);
                if (dfs(nums, signs, v * nums[i], required, stack)) {
                    return true;
                }
                stack.pop();
                stack.pop();

                // 除法
                stack.push("/");
                stack.push(nums[i]);
                if (nums[i] != 0 && v % nums[i] == 0 && dfs(nums, signs, v / nums[i], required, stack)) {
                    return true;
                }
                stack.pop();
                stack.pop();

                signs[i] = 0; // 回溯
            }
        }

        return false;//当所有情况均得不到需要的结果，返回false。
    }

    private static int str2Num(String letter) {
        int num;
        switch (letter) {
            case "joker":
            case "JOKER":
                num = -1;
                break;
            case "A":
                num = 1;
                break;
            case "J":
                num = 11;
                break;
            case "Q":
                num = 12;
                break;
            case "K":
                num = 13;
                break;
            default:
                num = Integer.parseInt(letter);
                break;
        }
        return num;
    }

    private static String num2Str(int num) {
        String str;
        switch (num) {
            case 1:
                str = "A";
                break;
            case 11:
                str = "J";
                break;
            case 12:
                str = "Q";
                break;
            case 13:
                str = "K";
                break;
            default:
                str = Integer.toString(num);
                break;
        }
        return str;
    }

}