题解 | #24点游戏算法#

def fun(nums, op):
    if op == "+":
        return sum(nums)
    elif op == "-":
        return nums[0] - nums[1]
    elif op == "*":
        return nums[0] * nums[1]
    else:
        return nums[0] / nums[1]


def calculate(RP_expression):
    num_stack = []
    for item in RP_expression:
        if isinstance(item, str):
            a, b = num_stack.pop(), num_stack.pop()
            try:
                num_stack.append(fun([a, b], item))
            except:  # 除数为0的时候会报错
                return -1
        else:
            num_stack.append(item)
    return num_stack[0]


def dfs(an, n, RP_expression, ret, visited, nums_stack, op_nums):
    if 2 * op_nums == len(RP_expression) - 1:
        # print(RP_expression)
        ret.append(RP_expression[:])  # 注意拷贝
    if len(RP_expression) == 7:
        return
    if nums_stack <= 1:  # 当逆波兰表达式内数字个数<2时，只可以添加数字
        for i in range(n):
            if visited[i]:
                continue
            visited[i] = True
            RP_expression.append(an[i])
            nums_stack += 1
            dfs(an, n, RP_expression, ret, visited, nums_stack, op_nums)
            nums_stack -= 1
            RP_expression.pop()
            visited[i] = False
    else:  # 当逆波兰表达式内数字个数>=2时，可以添加数字或符号
        # 加入数字
        for i in range(n):
            if visited[i]:
                continue
            visited[i] = True
            RP_expression.append(an[i])
            dfs(an, n, RP_expression, ret, visited, nums_stack + 1, op_nums)
            RP_expression.pop()#回溯
            visited[i] = False#回溯
        # 或加入符号
        for op in ["+","-","*","/"]:
            RP_expression.append(op)
            dfs(an, n, RP_expression, ret, visited, nums_stack - 1, op_nums + 1)
            RP_expression.pop()#回溯


if __name__ == "__main__":
    an = list(map(int, input().split()))
    n = len(an)
    # 状态变量
    RP_expression = []  # 逆波兰表达式
    ret = []
    visited = [False] * n
    nums_stack = 0  # RP中数字栈中的数字个数，每添加一个op则减一
    # n_nums = 0#RP中数字个数
    op_nums = 0  # RP中运算符个数，当op_nums=n_nums-1时代表可以计算
    dfs(an, n, RP_expression, ret, visited, nums_stack, op_nums)
    for expresssion in ret:
        if calculate(expresssion) == 24:
            # print(expresssion)
            print("true")
            exit()
    print("false")

dfs + 逆波兰表达式