# python实例：解决经典扑克牌游戏 — 四张牌凑24点 （一）

Hey! Hope you are having a great day so far!

The 24 Game is an arithmetical card game in which the objective is to find a way to manipulate four integers so that the end result is 24.

It is possible to combine the numbers 1, 5, 6, 7 with arithemtic operations to get 21 as follows: 6/(1-5/7).

Part I:

Write a function that takes in a list of three numbers and a target number, and returns a string that contains an expression that uses all the numbers  in the list once, and results in the target. Assume that the task is possible without using parentheses.

For example, get_target_noparens([3, 1, 2], 7) can return “2*3+1” or “1+2*3” (either output would be fine).

Part II:

Now, write the function get_target which returns a string that contains an expression that uses all the numbers in the list once, and results in the target. The expression can contain parentheses. Assume that the task is possible.

For example, get_target([1, 5, 6, 7], 21) can return “6/(1-5/7)” , this will return all permutation of the list of number.

1. 第一题只需要考虑三个数字，两个符号的排列组合，也就是说在改变运算符号时，我们只需考虑4选1，或者4选2的情况。而第二题却需要完全不同的思路，要在不确定总数字量的情况下，在每两个数字间考虑到所有排列可能。
2. 第二题需要考虑到一个，或者多个括号的算法，在这种情况下，我们不能直接计算结果，因为没有办法确定括号的个数和位置。

\$1+2+3\$

1 def get_all_comb(num_list):
2     '''find all arithmatic combination using the given 3 numbers'''
3
4     for op_1 in ['+','-','*','/']: # 用第一个for loop来考虑所有第一个位置的运算符号的可能性
5         for op_2 in ['+','-','*','/']: # 用第二个for loop来考虑所有第二个位置的运算符号的可能性
6             comb = str(num_list[0])+op_1+str(num_list[1])+op_2+str(num_list[2]) # 组装运算式
7             print(comb) # 打印运算式

1 def get_num_comb(num_list):
2     '''find all combination possibilities of the given 3 numbers'''
3
4     all_comb = [] # 准备收集所有排列组合
5     for i in range(3): # 三个嵌套for循环分别对应在num_list里的序数
6         for j in range(3):
7             for k in range(3):
8                 if i != j and i != k and j != k: # 确定没有重复元素
9                     print([num_list[i], num_list[j], num_list[k]]) #打印最终结果

1 def generate_comb_op(n):
2     '''find all combination of Arithmetic operators with n possible spaces for operators'''
3     # 建立base case
4     if n==0:
5         return [] # 当n为0时不返回任何操作符号
6     elif n ==1:
7         return [['+'],['-'],['*'],['/']] # 当n为1时返回基础的四个符号，注意这里需要用到list of list
8     op_list = generate_comb_op(n-1) # 因为之后要加，所以我们这里用到递归的逻辑，来找到最基本的operator_list
9     all_op_list = [] # 新建一个list来准备更新我们加了运算符号后的sublist
10     # 最后我们还是要用循环的逻辑来给我们原来list里的元素加新的符号
11     for i in op_list:
12         for j in ['+','-','*','/']:
13             all_op_list.append(i+[j]) # 这里用了新的list，来确保每个sublist的长度是相等的
14
15     return all_op_list # 最后返回最终结果

Permutation的逻辑比运算符号的排列稍稍复杂，但是我们可以用类似的递归结构来解决不同的问题，代码如下：

1 def generate_permutated_list(num_list):
2     '''find permuted lists of n given numbers'''
3     # 建立base case
4     if len(num_list) == 0:
5         return [] # 当n为0时不返回任何数字
6     if len(num_list) == 1:
7         return [num_list] # 当n为1时返回所有式子，作为之后首数字的基础
8     list_of_comb = [] # 新建列表来存更新的排列
9     for i in range(len(num_list)):
10         first_num = num_list[i] # 生成首字母
11         for j in generate_permutated_list(num_list[:i] + num_list[i+1:]): # 去除首字母，继续递归
12             list_of_comb.append([first_num] + j) #加入新的list
13
14     return list_of_comb # 最后返回最终结果

1 def modify_op(equation, op):
2     '''this function modify the given equation by only computing the section with the given operators
3     parameters:
4         equation: a list that represents a given mathematical equation which may or may not contain the
5                 given numerical operators. Ex, ['1','+','2'] represents the equation 1+2
6         op: a string that is the given numerical operators'''
7
8     # 这里我们把代表数学计算的字符串和以上定义的操作函数的名字以字典的方式联系并储存起来
9     operators = {'/':division, '*':multiply, '+':add, '-':subtract}
10
11     while op in equation: # 用while循环来确保没有遗漏任何字符
12         i = equation.index(op) # 找到表达式内的第一处需要计算的字符位置
13         if op == '/' and equation[i+1] == '0': # 考虑除法操作的被除数为0的情况
14             return ['']
15         # 把表达式需要计算的部分替换成计算结果
16         equation[i-1:i+2] = [str(operators[op](float(equation[i-1]), float(equation[i+1])))] # 注意这里调用了前面字典里储存的函数名
17     return equation # 返回结果
18
19 def evaluate(equation):
20     '''return the evaluated result in float for the equation'''
21
22     for op in ['/','*','+','-']: # 这里需要注意标点顺序，除在最先，因为需要考虑特殊情况，乘其次，然后才是加减
23         equation = modify_op(equation, op) # 使用helper function
24     return equation[0] # 最后返回最终计算结果

1. 找出所有加减乘除的排列组合
2. 找出所有数字的排列组合
3. 整合所有表达式可能
4. 用估值函数计算表达式
5. 对比表达式答案和目标数
6. 返回符合要求的表达式

1 #  Write a function that takes in a list of three numbers and a target number, and
2 #  returns a string that contains an expression that uses all the numbers
3 #  in the list once, and results in the target. Assume that the task is possible
4 #  without using parentheses.
5 #
6 #  For example, get_target_noparens([3, 1, 2], 7) can return "2*3+1" or "1+2*3"
7 #  (either output would be fine).
8
9 ############################################# 数学表达式生成函数 #############################################
10
11 def generate_comb_op(n):
12     '''find all combination of Arithmetic operators with n possible spaces for operators'''
13     # 建立base case
14     if n==0:
15         return [] # 当n为0时不返回任何操作符号
16     elif n ==1:
17         return [['+'],['-'],['*'],['/']] # 当n为1时返回基础的四个符号，注意这里需要用到list of list
18     op_list = generate_comb_op(n-1) # 因为之后要加，所以我们这里用到递归的逻辑，来找到最基本的operator_list
19     all_op_list = [] # 新建一个list来准备更新我们加了运算符号后的sublist
20     # 最后我们还是要用循环的逻辑来给我们原来list里的元素加新的符号
21     for i in op_list:
22         for j in ['+','-','*','/']:
23             all_op_list.append(i+[j]) # 这里用了新的list，来确保每个sublist的长度是相等的
24
25     return all_op_list # 最后返回最终结果
26
27
28 def generate_permutated_list(num_list):
29     '''find permuted lists of n given numbers'''
30     # 建立base case
31     if len(num_list) == 0:
32         return [] # 当n为0时不返回任何数字
33     if len(num_list) == 1:
34         return [num_list] # 当n为1时返回所有式子，作为之后首数字的基础
35     list_of_comb = [] # 新建列表来存更新的排列
36     for i in range(len(num_list)):
37         first_num = num_list[i] # 生成首字母
38         for j in generate_permutated_list(num_list[:i] + num_list[i+1:]): # 去除首字母，继续递归
39             list_of_comb.append([first_num] + j) #加入新的list
40
41     return list_of_comb # 最后返回最终结果
42
43
44 #################################### 定义所有可能出现的数学操作，包括加减乘除 ####################################
45
46 def division(a,b): # 除法比较特殊，在之后的代码里会考虑到被除数为0的情况
47     return a/b
48 def multiply(a,b):
49     return a*b
51     return a+b
52 def subtract(a,b):
53     return a-b
54
55 ############################################ 数学表达式处理函数 ##############################################
56
57 def modify_op(equation, op):
58     '''this function modify the given equation by only computing the section with the given operators
59     parameters:
60         equation: a list that represents a given mathematical equation which may or may not contain the
61                 given numerical operators. Ex, ['1','+','2'] represents the equation 1+2
62         op: a string that is the given numerical operators'''
63
64     # 这里我们把代表数学计算的字符串和以上定义的操作函数的名字以字典的方式联系并储存起来
65     operators = {'/':division, '*':multiply, '+':add, '-':subtract}
66
67     while op in equation: # 用while循环来确保没有遗漏任何字符
68         i = equation.index(op) # 找到表达式内的第一处需要计算的字符位置
69         if op == '/' and equation[i+1] == '0': # 考虑除法操作的被除数为0的情况
70             return ['']
71         # 把表达式需要计算的部分替换成计算结果
72         equation[i-1:i+2] = [str(operators[op](float(equation[i-1]), float(equation[i+1])))] # 注意这里调用了前面字典里储存的函数名
73     return equation # 返回结果
74
75 def evaluate(equation):
76     '''return the evaluated result in float for the equation'''
77
78     for op in ['/','*','+','-']: # 这里需要注意标点顺序，除在最先，因为需要考虑特殊情况，乘其次，然后才是加减
79         equation = modify_op(equation, op) # 使用helper function
80     return equation[0] # 最后返回最终计算结果
81
82 ############################################# 最终使用函数 ###############################################
83
84 def get_target_noparens(num_list, target):
85     op_list = generate_comb_op(len(num_list)-1) # 找出所有加减乘除的排列组合
86     num_comb = generate_permutated_list(num_list) # 找出所有数字的排列组合
87     # 用for嵌套循环来整合所有表达式可能
88     for each_op_list in op_list:
89         for each_num_list in num_comb:
90             equation = [] # 用list初始化表达式
91             equation_str = '' # 用string表达算式
92             for i in range(len(each_op_list)):
93                 equation.extend([str(each_num_list[i]), each_op_list[i]])
94                 equation_str += str(each_num_list[i]) + each_op_list[i]
95             equation.append(str(each_num_list[-1]))
96             equation_str += str(each_num_list[-1])
97
98             result = evaluate(equation) # 表达式估值，这里要用list的形式
99             if float(result) == float(target):
100                 return equation_str # 用字符串返回算式

• get_target_noparens([1,2,3], 6) 返回  1+2+3
• get_target_noparens([1,2,3], 4.5)返回 1+3/2
• get_target_noparens([23,1,3], 68) 返回  23*3-1

#### 参考资料：

• https://en.wikipedia.org/wiki/24_Game
• 例题选自 University of Toronto, ESC180 2020 Final, Question 4 & Question 5