题解 | 24点游戏算法

def calculate24(nums):
    # 定义所有可能的运算符号(+, -, *, /)
    operators = ['+', '-', '*', '/']
    
    # 生成所有可能的数字排列组合的函数
    def permutations(arr):
        # 如果数组为空,返回空列表
        if len(arr) == 0:
            return []
        # 如果数组只有一个元素,返回该元素构成的列表
        if len(arr) == 1:
            return [arr]
        l = []
        # 遍历数组中的每个元素
        for i in range(len(arr)):
            # 取出当前元素
            m = arr[i]
            # 获取剩余的元素
            rem_arr = arr[:i] + arr[i+1:]
            # 递归获取剩余元素的全排列,并将当前元素加到每个排列的前面
            for p in permutations(rem_arr):
                l.append([m] + p)
        return l
    
    # 计算给定数字和运算符组合是否能得到24的函数
    def eval_expr(nums, ops):
        # 尝试不同的表达式组合
        try:
            # 1. 无括号的情况
            expr = f"{nums[0]}{ops[0]}{nums[1]}{ops[1]}{nums[2]}{ops[2]}{nums[3]}"
            if abs(eval(expr) - 24) < 0.0001:  # 考虑浮点数计算误差
                return True
                
            # 2. 一对括号的情况
            # 2.1 括号在最左边
            expr = f"({nums[0]}{ops[0]}{nums[1]}){ops[1]}{nums[2]}{ops[2]}{nums[3]}"
            if abs(eval(expr) - 24) < 0.0001:
                return True
            
            # 2.2 括号在中间    
            expr = f"{nums[0]}{ops[0]}({nums[1]}{ops[1]}{nums[2]}){ops[2]}{nums[3]}"
            if abs(eval(expr) - 24) < 0.0001:
                return True
            
            # 2.3 括号在最右边    
            expr = f"{nums[0]}{ops[0]}{nums[1]}{ops[1]}({nums[2]}{ops[2]}{nums[3]})"
            if abs(eval(expr) - 24) < 0.0001:
                return True
                
            # 3. 两对括号的情况
            # 3.1 两个并列的括号
            expr = f"({nums[0]}{ops[0]}{nums[1]}){ops[1]}({nums[2]}{ops[2]}{nums[3]})"
            if abs(eval(expr) - 24) < 0.0001:
                return True
                
            # 3.2 嵌套括号,从左到右
            expr = f"(({nums[0]}{ops[0]}{nums[1]}){ops[1]}{nums[2]}){ops[2]}{nums[3]}"
            if abs(eval(expr) - 24) < 0.0001:
                return True
                
            # 3.3 嵌套括号,从右到左
            expr = f"{nums[0]}{ops[0]}(({nums[1]}{ops[1]}{nums[2]}){ops[2]}{nums[3]})"
            if abs(eval(expr) - 24) < 0.0001:
                return True
                
            # 3.4 嵌套括号,最右侧
            expr = f"{nums[0]}{ops[0]}({nums[1]}{ops[1]}({nums[2]}{ops[2]}{nums[3]}))"
            if abs(eval(expr) - 24) < 0.0001:
                return True
                
            # 3.5 嵌套括号,左侧优先
            expr = f"({nums[0]}{ops[0]}({nums[1]}{ops[1]}{nums[2]})){ops[2]}{nums[3]}"
            if abs(eval(expr) - 24) < 0.0001:
                return True
        except:
            # 处理可能的计算错误(如除以零)
            return False
        return False

    # 主逻辑:遍历所有可能的数字排列和运算符组合
    num_perms = permutations(nums)  # 获取所有可能的数字排列
    for nums in num_perms:  # 遍历每一种数字排列
        for op1 in operators:  # 遍历第一个运算符
            for op2 in operators:  # 遍历第二个运算符
                for op3 in operators:  # 遍历第三个运算符
                    if eval_expr(nums, [op1, op2, op3]):  # 检查当前组合是否能得到24
                        return True
    return False  # 所有组合都试过了还没找到解,返回False

# 程序入口:获取输入并处理
numbers = list(map(int, input().split()))  # 读取输入并转换为整数列表

# 输出结果
if calculate24(numbers) == True:
    print("true")
elif calculate24(numbers) == False:
    print("false")
#print(calculate24(numbers))