题目描述 24点游戏的玩法是这样的:任取一幅牌中的 4张牌(不含大小王),每张牌上有数字(其中A 代表1,J 代表11,Q 代表 12,K代表13),你可以利用数学中的加、减、乘、除以及括号想办法得到24,每张牌只能用一次。例如有四张6,那么6+6+6+6=24,也可以6*6-6-6=24。但是有些牌是无法得到24的,比如两张 A 和两张2。 读入表达式树的先序遍历字符串, 这里的表达式树是来自24点游戏的真实场景,也就是对应四个数字(值在1到13之间)组成的表达式,问该表达式树能不能得到24? 输入 输入由多组测试数据组成。 每组数据包含一行字符串,即24点游戏的表达式树的先序遍历序列。 输出 对于每组数据,输出一行。如果不能得到24,输出“NO”。如果能得到24,按样例输出。 样例输入 Copy + + + 6 # # 6 # # 6 # # 6 # # - - * 6 # # 6 # # 6 # # 6 # # * * 1 # # 2 # # * 1 # # 2 # # 样例输出 Copy (((6+6)+6)+6)=24 (((6*6)-6)-6)=24 NO
时间: 2024-03-18 19:38:48 浏览: 73
根据题目描述,我们需要读入表达式树的先序遍历字符串,然后判断该表达式树能否得到24。由于我们需要进行多组测试,因此我们可以采用循环输入的方式。下面是一个可能的实现代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(s):
if not s:
return None
if s[0] == '#':
return None
root = TreeNode(s[0])
root.left = build_tree(s[1:])
root.right = build_tree(s[1:])
return root
def evaluate(root):
if root.val == '+':
return evaluate(root.left) + evaluate(root.right)
elif root.val == '-':
return evaluate(root.left) - evaluate(root.right)
elif root.val == '*':
return evaluate(root.left) * evaluate(root.right)
elif root.val == '/':
right = evaluate(root.right)
if right == 0:
return float('inf')
return evaluate(root.left) / right
else:
return int(root.val)
def is_possible_24(root):
if not root:
return False
result = evaluate(root)
if result == 24:
return True
return is_possible_24(root.left) or is_possible_24(root.right)
while True:
try:
s = input().strip().split()
root = build_tree(s)
if is_possible_24(root):
print("(" + s[0] + ")=24")
else:
print("NO")
except:
break
```
需要注意的是,除法可能存在除数为0的情况,因此在实现中需要特判一下。同时,由于Python中整数除法默认向下取整,因此在除法运算中需要使用浮点数进行计算。另外,输出时需要按照题目要求加上括号。
阅读全文