一、游戏玩法介绍：

24点游戏是儿时玩的主要益智类游戏之一，玩法为：从一副扑克中抽取4张牌，对4张牌使用加减乘除中的任何方法，使计算结果为24。例如，2,3,4,6，通过( ( ( 4 + 6 ) - 2 ) * 3 ) = 24，最快算出24者剩。

二、设计思路：

由于设计到了表达式，很自然的想到了是否可以使用表达式树来设计程序。本程序的确使用了表达式树，也是程序最关键的环节。简要概括为：先列出所有表达式的可能性，然后运用表达式树计算表达式的值。程序中大量的运用了递归，各个递归式不是很复杂，大家耐心看看，应该是能看懂的

表达式树：

表达式树的所有叶子节点均为操作数(operand)，其他节点为运算符(operator)。由于本例中都是二元运算，所以表达式树是二叉树。下图就是一个表达式树

具体步骤：

1、遍历所有表达式的可能情况

遍历分为两部分，一部分遍历出操作数的所有可能，然后是运算符的所有可能。全排列的计算采用了递归的思想

#返回一个列表的全排列的列表集合

deflist_result(l):if len(l) == 1:return[l]

all_result=[]for index,item inenumerate(l):

r= list_result(l[0:index] + l[index+1:])

map(lambdax : x.append(item),r)

all_result.extend(r)return all_result

2、根据传入的表达式的值，构造表达式树

由于表达式树的特点，所有操作数均为叶子节点，操作符为非叶子节点，而一个表达式(例如( ( ( 6 + 4 ) - 2 ) * 3 ) = 24) 只有3个运算符，即一颗表达式树只有3个非叶子节点。所以树的形状只有两种可能，就直接写死了

　

#树节点

classNode:def __init__(self, val):

self.val=val

self.left=None

self.right= None

defone_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=operand3returnroot_nodedeftwo_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=operand3return root_node

3、计算表达式树的值

也运用了递归

#根据两个数和一个符号，计算值

defcal(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)defcal_tree(node):if node.left isNone:returnnode.valreturn cal(cal_tree(node.left), cal_tree(node.right), node.val)

4、输出所有可能的表达式

还是运用了递归

defprint_expression_tree(root):

print_node(root)print '= 24'

defprint_node(node):if node isNone :return

if node.left is None and node.right isNone:printnode.val,else:print '(',

print_node(node.left)printnode.val,

print_node(node.right)print ')',#print ' ( %s %s %s ) ' % (print_node(node.left), node.val, print_node(node.right)),

5、输出结果

三、所有源码

#coding:utf-8

from __future__ importdivisionfrom Node importNodedefcalculate(nums):

nums_possible=list_result(nums)

operators_possible= list_result(['+','-','*','÷'])

goods_noods=[]for nums innums_possible:for op inoperators_possible:

node=one_expression_tree(op, nums)if cal_tree(node) == 24:

goods_noods.append(node)

node=two_expression_tree(op, nums)if cal_tree(node) == 24:

goods_noods.append(node)

map(lambdanode: print_expression_tree(node), goods_noods)defcal_tree(node):if node.left isNone:returnnode.valreturncal(cal_tree(node.left), cal_tree(node.right), node.val)#根据两个数和一个符号，计算值

defcal(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)defone_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=operand3returnroot_nodedeftwo_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=operand3returnroot_node#返回一个列表的全排列的列表集合

deflist_result(l):if len(l) == 1:return[l]

all_result=[]for index,item inenumerate(l):

r= list_result(l[0:index] + l[index+1:])

map(lambdax : x.append(item),r)

all_result.extend(r)returnall_resultdefprint_expression_tree(root):

print_node(root)print '= 24'

defprint_node(node):if node isNone :return

if node.left is None and node.right isNone:printnode.val,else:print '(',

print_node(node.left)printnode.val,

print_node(node.right)print ')',if __name__ == '__main__':

calculate([2,3,4,6])

View Code

英雄年代手游正版官方网站：英雄年代手游：端游经典指尖微操，1:1复刻经典 - 英雄年代手游正版官方网站掌上重温端游经典，英雄年代手游正版官方网站为您呈现原汁原味的1:1复刻玩法。快来感受指尖微操的游戏乐趣！https://m.rxsy99.com/qwa.html