题解 | #24点游戏算法#

numberlist = input().split() # 读入数据，简写为列表n[4]

# 由于涉及到括号，把运算写为后缀表达式形式，即4个数3个运算符的表达式（用长度为7的字符串列表formula表示）
# 为什么是3个运算符，因为题目只让运算符出现在两个数字之间
# 例如输入为5 6 7 8，['1','0','2','3','*','+','-']表示n[3]*n[2]+n[0]-n[1]，即8*7+5-6
# 为什么不是[6,5,7,8,'*','+','-']，因为需要避免输入数据中有重复数字的情况，所以只储存数据的下标
# 为什么不是[1,0,2,3,'*','+','-']，因为python列表中元素类型必须相同，所以统一为字符串
# 24点问题转化为从['0','1','2','3','+','-','*','/']这8个元素中选7个依次填入formula后缀表达式列表
# 填充先后顺序：先看能否填充数字，不行的话再填充运算符
# 用DFS即可解题

def Calculate(formula0:list[str])->float:
	# 计算后缀表达式formula0，返回一个浮点数结果
	# 用列表模拟一个运算栈stack0，top0表示栈首的下标（列表尾部）
    stack0 = [0.0]*len(formula0)
    top0 = -1
    for m0 in formula0:
        try:
			# 若读到数据，直接入栈
            a0 = int(m0)
            top0 += 1
            stack0[top0] = float(numberlist[int(m0)]) # 注意formula储存是数据下标的字符形式
        except:
            if m0 == '+':
                stack0[top0-1] += stack0[top0]
            elif m0 == '-':
                stack0[top0-1] -= stack0[top0]
            elif m0 == '*':
                stack0[top0-1] *= stack0[top0]
            else:
				# 注意被除数为0的情况，本来应该返回error，但考虑到题目只要求判断是否等于24，故直接返回0
                if stack0[top0] == 0: 
                    return 0.0
                stack0[top0-1] /= stack0[top0]
            top0 -= 1
	# 输出栈首即为运算结果
    return stack0[top0]

floor = 0 # DFS当前层数（取值0~6，共7层）
formula = ['']*7 # 当前后缀表达式
pickele = ['0','1','2','3','+','-','*','/'] # formula中所有可能的值
yes = 0 # 用于判断结果是否为24，是的话为1
use = [0, 0, 0, 0] # use[i]表示formula[:floor]是否出现过'i'，为0表示当前层以前n[i]未被使用
dN = 0 # 表示当前层以前数字个数与运算符个数的差值，只有dN＞=2当前层才能继续插入运算符
while True:
    if floor < 0: # 如果找不到可能的情况了，直接退出
        break
    if floor < 7: # 如果formula没填充完，那就继续填充
        t = -1
		# 看当前层原有的值是空（t=-1）、数字（0<=t<=3）还是运算符(4<=t<=7)
        for i in range(8):
            if formula[floor] == pickele[i]:
                t = i
                break
		# 如果当前层有值，那么在更新这一层的时候原有数据是要被抹掉的，所以需更新use和dN
		# 分两种情况：1.当前层为数字，把该数字标记为未使用，dN-=1；2.为符号，dN+=1
        if (t>=0) and (t<=3):
			# 当前层为数字，把该数字标记为未使用，dN-=1
            use[t] -= 1
            dN -= 1
        if t <= 3:
            r = -1
			# 看当前层还有没有可使用的数字
            for i in range(t + 1, 4):
                if use[i] < 1:
                    r = i
                    break
            if r >= 0: # 如果有可使用的数字pickele[r]，直接填充，更新use和dN
                formula[floor] = pickele[r]
                dN += 1
                use[r] += 1
                floor += 1
            else: # 如果没有可使用的数字就判断有无可用的运算符
                if dN >= 2: # 后缀表达式的要求，dN >= 2表示该层可以填充运算符
					# 因为该层还没有填充过运算符，故直接填充第一个运算符'+'，并更新use和dN
                    dN -= 1
                    formula[floor] = pickele[4]
                    floor += 1
                else:
					# 该层没有可以填充的值了，回到上一层，注意把这层的值初始化为空
                    formula[floor] = ''
                    floor -= 1
        # 如果该层原本就是运算符，dN+=1，看还有没有运算符可以用
		elif t != 7:
			# 若还有运算符可以用，就直接填充并进入下一层（注意填充的时候dN要-1，和前面的+1抵消了所以没写）
            formula[floor] = pickele[t+1]
            floor += 1
        else:
			# 若没有运算符可用，回到上一层
            dN += 1
            formula[floor] = ''
            floor -= 1
    else: # floor>6表示formula填充完毕，看是否能凑成24点，不能凑直接回到上一层尝试其他填充方式
        if Calculate(formula) == 24.0:
            yes = 1
            break
        else:
            floor -= 1

if yes == 1:
    print('true')
else:
    print('false')