游戏规则：从一副扑克牌中抽取4张牌，对4张牌使用加减乘除中的任何方法使计算结果为24，例如(((4-2)+6)*3) = 24，最快算出24者胜。
实现思路：参照原作者想法，由于设计到了表达式，很自然的想到了用二叉树来实现。简单概括为：先列出所有表达式的可能性，然后运用表达式树，也就是二叉树计算表达式的值，当然还需要使用递归来具体实现各个功能，下面我们具体来实现下吧。
表达式树的所有叶子节点均为操作数(operand), 其它节点为运算符(operator),本次采用二叉树来表示表达式中各个属性的值，这样也方便我们计算。
表达式树1
表达式树2
首先是遍历所有表达式的可能情况，这里得到得是操作数所有可能得情况,假如传入的l是序列[1,2,3,4],count1是4,count2是4，那么得到的结果就是12个随机且不重复的[1,2,3,4]序列
#遍历所有表达式的可能情况
# l - 需要生成随机数组的序列
# count1 - 指定随机序列的个数，这里如果传入为4，我们会执行math下的factorial方法，也就是求4的阶乘，也就是24,24/2 =12
# count2 - 随机序列元素的个数
def list_shuffle_nums(l,count1,count2):
all_result = []
count = math.factorial(count1) / 2
while len(all_result) <= count:
result = []
r = random.sample(l,count2)
for index2 in r:
result.append(index2)
if result not in all_result:
all_result.append(result)
return all_result
同理，产生运算符的不同排列结果
#遍历所有表达式的可能情况
# l - 需要生成随机数组的序列
# count1 - 指定随机序列的个数
# count2 - 随机序列元素的个数
def list_shuffle_operators(l,count1,count2):
all_result = []
#计算count1的阶乘，表示随机序列的个数
count = math.factorial(count1)
while len(all_result) <= count:
result = []
r = random.sample(l,count2)
for index2 in r:
result.append(index2)
if result not in all_result:
all_result.append(result)
return all_result
然后根据传入的表达式的值，构造表达式树，首先我们创建一个表示节点的类
# 树节点
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
然后树的形式无非两种，就是上面大家看到的两种形式，用程序表示出来就是两种函数，参数分别对应了运算符和运算符，还是比较好理解的，知识涉及一些二叉树的知识。
def one_expression_tree(operators,operands):
root_node = Node(operators[0])
operator1 = Node(operators[1])
operator2 = Node(operators[2])
operand0 = Node(operands[0])
operand1 = Node(operands[1])
operand2 = Node(operands[2])
operand3 = Node(operands[3])
root_node.left = operator1
root_node.right = operator2
operator1.left = operand0
operator1.right = operand1
operator2.left = operand2
operator2.right = operand3
return root_node
def two_expression_tree(operators,operands):
root_node = Node(operators[0])
operator1 = Node(operators[1])
operator2 = Node(operators[2])
operand0 = Node(operands[0])
operand1 = Node(operands[1])
operand2 = Node(operands[2])
operand3 = Node(operands[3])
root_node.left = operator1
root_node.right = operand0
operator1.left = operator2
operator1.right = operand1
operator2.left = operand2
operator2.right = operand3
return root_node
然后就是计算表达式树的值,这里也运用了递归。
def cal_tree(node):
if node.left is None:
return node.val
return cal(cal_tree(node.left),cal_tree(node.right),node.val)
#根据两个数和一个符号，计算值
def cal(a,b,operator):
return operator == '+' and float(a) + float(b) or operator == '-' and float(a) - float(b) or operator == '*' and float(a) * float(b) or operator == '÷' and float(a) / float(b)
def calculate(nums):
nums_possible = list_shuffle_nums(nums,3,4)
operators_possible = list_shuffle_operators(['+','-','*','÷'],3,3)
goods_noods = []
for nums in nums_possible:
for op in operators_possible:
node1 = one_expression_tree(op,nums)
result1 = cal_tree(node1)
print('第一种运算过程结果:%d' % result1)
if result1 == 24:
goods_noods.append(node1)
for nums in nums_possible:
for op in operators_possible:
node2 = two_expression_tree(op,nums)
result2 = cal_tree(node2)
print('第二种运算过程结果:%d' % result2)
if result2 == 24:
goods_noods.append(node2)
if len(goods_noods) == 0:
print('计算结果失败')
else:
print('计算结果成功')
for node in goods_noods:
print_expression_tree(node)
输出所有可能的结果,这里注意print_node方法也是使用的递归来打印数据，并且使用end=''去掉了换行符。
def print_expression_tree(root):
print_node(root)
print (' = 24')
def print_node(node):
if node is None:
return
if node.left is None and node.right is None:
print (node.val,end='')
else:
print ('(',end='')
print_node(node.left)
print (node.val,end='')
print_node(node.right)
print (')',end='')
#print (' ( %d %s %d ) ' % (print_node(node.left), node.val, print_node(node.right)))
最后在程序的入口调用calculate方法,并传入数据，也就是你得到的牌。
if __name__ == '__main__':
calculate([2,3,4,6])
成果：
image.png
网友评论