[数据结构与算法]【一起来刷Python题】——08.破解24点游戏

自己不是大佬，却渴望成为大佬...🌈做算法题第8天，断更了这么久，过一段时间有惊喜分享，哈哈哈...

题目描述：给定4个整数，数字范围为1~13，任意使用+、-、*、/、()，构造出 一个表达式，使得最终结果为24。这就是常见的算24的游戏。例如：(9-8)×8×3=24。

代码：

from __future__ import division
from itertools import  combinations
import re
class Solver:
    # 需要达成的目标结果值
    target = 24
    # 四则运算符号定义， 其中，a--b=b-a，a//b=b/a；
    ops = ['+','-','*','/','--','//']
    # precise_mode为精准模式，若开启，则减号及除号后开启括号
    def __init__(self, precise_mode=False):
        self.precise_mode = precise_mode
    def solution(self, nums):
        result = []
        groups = self.dimensionality_reduction(self.format(nums))
        for group in groups:
            for op in self.ops:
                exp = self.assemble(group[0], group[1], op)['exp']
                if self.check(exp, self.target) and exp not in result:
                    result.append(exp)
        return [exp + '=' + str(self.target) for exp in result]
    # 对需要处理的数字或表达式组合进行降维， 降低到二维
    def dimensionality_reduction(self, nums):
        result = []
        # 如果维数大于2， 则选出两个表达式组合成一个， 从而降低一个维度， 通过递归降低到二维
        if len(nums) > 2:
            for group in self.group(nums, 2):
                for op in self.ops:
                    new_group = [self.assemble(group[0][0], group[0][1], op)] + group[1]
                    result += self.dimensionality_reduction(new_group)
        else:
            result = [nums]
        return result
    # 将两个表达式组合成一个新表达式
    def assemble(self, exp1, exp2, op):
        # 如果运算符为‘--’或者‘//’，则交换数字顺序重新计算
        if op == '--' or op == '//':
            return self.assemble(exp2, exp1, op[0])
        # 如果是乘法，则根据两个表达式的情况加括号
        if op in r'*/':
            exp1 = self.add_parenthesis(exp1)
            exp2 = self.add_parenthesis(exp2)
        if self.precise_mode:
            if op == '-':
                exp2 = self.add_parenthesis(exp2)
            elif op == '/':
                exp2 = self.add_parenthesis(exp2, True)
        exp = self.convert(exp1['exp']+ op + exp2['exp'], op)
        return {'op': op, 'exp': exp}
    # 根据需要为表达式添加相应的括号
    @staticmethod
    def add_parenthesis(exp, is_necessary=False):
        # 如果上一计算步骤的运算符号为加号或减号，则需要加括号
        if (is_necessary and not exp['exp'].isdigit()) or exp['op'] in r'+-':
            result = {
                'exp': '(' + exp['exp'] +')',
                'op': exp['op']
            }
        else:
            result = exp
        return result
    # 检查表达式是否与结果相等，考虑到中间步骤的除法，因此不采用相等判断，而是采用计算值和目标值的绝对值是否符合某个精度
    @staticmethod
    def check(exp, target, precision=0.0001):
        try:
            return abs(eval(exp) - target) < precision
        except ZeroDivisionError: # 出现被除数是 0 的情况，返回False
            return False
    # 将表达式各项重新排序为等价标准表达式
    @staticmethod
    def convert(exp ,op):
        if op in r'+-':
            pattern = r'([\+\-]((\(.+\)|\d+)[\*\/](\(.+\)|\d+)|\d+))'
            exp = '+' + exp
        else:
            pattern = r'([\*\/](\(.+?\)|\d+))'
            exp = '*' + exp
        result = ''.join(sorted([i[0] for i in re.findall(pattern, exp)]))
        if len(result) != len(exp):
            result = exp
        return result[1:]
    # 将输入的数字格式为字典，数字的运算符号为空格，注意不是空字符
    @staticmethod
    def format(nums):
        return [{'op': ' ', 'exp': str(num)} for num in nums]
    # 对标达式列表进行分组，返回列表，[[[n1, n2],[n3, n4],[[n1,n3],[n2,n4]],...]
    @staticmethod
    def group(exp_list, counter):
        # 生成以下标号为元素的列表
        index_list = [i for i in range(len(exp_list))]
        # 以下标号列表取出不重复的组合
        combination = list(combinations(index_list, counter))
        # 使用下标得到原表达式并组成最终的结果数组
        for group1 in combination:
            group2 = list(set(index_list) - set(group1))
            yield [
                [exp_list[g1] for g1 in group1],
                [exp_list[g2] for g2 in group2]
            ]
auto_input = False
if auto_input:
    from numpy import random
    customer_input = random.randint(1, 20, size=4)
else:
    customer_input = list()
    customer_input.append(input('请输入第一个数字： '))
    customer_input.append(input('请输入第二个数字： '))
    customer_input.append(input('请输入第三个数字： '))
    customer_input.append(input('请输入第四个数字： '))
task = Solver()
answer = task.solution(customer_input)
if len(answer) == 0:
    print('No solutions')
else:
    for a in answer:
        print(a)

代码思路：

我们的目标：给定任意N个正整数（N>1）,找到能够将这N个数通过四则运算得出24的全部表达式，并且只在必要的时候加上括号以及去除等价的重复表达式。

1.去除括号：首先明确两个问题。1）合适的括号是在不影响计算结果的前提下，能不加括号就不加括号。比如：（15+8）+7-6=24应写作 15+8+7-6=24。2）等价的重复表达式是完全相同的表达式，或者在加法交换律和乘法交换律的作用下，完全相等的表达式。比如下面三种解法：① 10+12+7-5=24等价于10-5+7+12=24；② 15*8/（1+4）=24等价于15/（4+1）*8=24；③（3+1）*（2+4）=24等价于（1+3）*（4+2）=24。

2.求全部解算法：我们采用的算法是降低维度的算法，即把4个数字运算的四维问题降低到二维来解决。比如，给定4个数字[1,2,3,4]，这是一个四维问题，我们首先要将其转换为二维问题。具体的办法是，先将4个数字其中的两个数字取出，然后将这两个数字转化为所能组成的全部表达式。我们首先取出[1,2]，考虑到加法交换律和乘法交换律的前提下，共有6种可能的不等价表达式，即1+2，1-2，1*2，1/2，2-1，2/1，则四维问题就可以转化为多组三维问题，即['1+2'，3，4]，['1-2'，3，4]，['1*2'，3，4]，['1/2'，3，4]，['1--2'，3，4]，['2/1'，3，4]。然后我们枚举每一种取出两个数的组合，使用排列组合公式即C(4,2)，所以将四维问题，所以将四维问题转化为三维问题共有C(4,2)*6=36种组合。下一步是重复这一过程，将三维问题继续转化为二维问题，同理，每一个三维问题都可转化为等价的二维问题，共有C(3,2)*6=18种组合。所以，四维问题可转化为36*18=648种二维问题，每个二维问题又有6种组合方式，所以，全部的表达式个数为648*6=3888个。

3.加括号算法：每当将二维组合成新表达式的时候，根据原有的两个表达式的各自的运算符号和两个表达式之间的运算符的关系来判断是否需要添加括号。举个例子，假设a、b两个表达式要组合成新的表达式，总共会有如下4种情形。① 如果式a+b，则完全不需要加括号。② 如果是a*b或者a/b，若a、b自身的运算符号是加号或者减号，则应加括号。如a=a1+a2，b为数字，则a*b=(a1+a2)*b。③如果是a-b，则b为加号或减号，则b应加括号。如b=b1-b2，a=a1+a2，则a-b=a1+a2-(b1-b2)，但值得注意的是，a1+a2-(b1-b2)其实等价于a1+a2-b1+b2，这种情况在其他的组合中其实已经存在。因此，无须再考虑这种情况下的加括号问题。④如果是a/b，若b的符号是乘号或者除号，原本也要加括号，但其实这种情况与上一种情况类似，我们出于计算简便考虑，可以不再考虑括号问题。

4.去除等价表达式：对于一个运算表达式来说，a+b-c+d与如下三种运算表达式的计算结果均是等价的：①a+d+b-c；②b+a+d-c③b-c+a+d 我们可以在任何一个表达式前再加一个加号，然后使用正则表达式对表达式进行切割成如下状态：['+a'，'+b'，'-c'，'+d'] 最后对其进行排序后再组合成字符串得到： a+b+d-c 。问哦们将这样的表达式称为标准表达式，凡是通过这样的处理方法得到的标准表达式是相同的，我们均认为式等价表达式，只保留一个标准表达式即可。同理，乘法交换律也是同样的转换方法。