「24 点」是一个历史悠久的游戏：任取 4 张扑克牌，如何用「加、减、乘、除」运算算出 24？除了作为消遣，它还是一道经典的编程入门题，其基本思路是：枚举所有可能的算式，逐个检验结果是否等于 24。

　　在这一系列专栏中，我们忽略「24」，而把目光聚焦在「枚举算式」上。换句话说，我们来枚举由 4 个变量 a, b, c, d（也可以推广至 n 个变量）经过四则运算可以组成的所有算式，而不代入具体数值。我们的程序要输出的，就是 a + b - c * d、a / (b * (c + d)) 这样所有的算式。

　　枚举算式的思路有很多，比如：

• 不分层枚举：分别枚举 n 个变量的顺序、n-1 个运算符是什么，以及加括号的方式。「加括号的方式」不太直接，但可以用「n-1 个运算符的计算顺序」来代替。这种思路适合用来计算算式的总数： ，但如果真要枚举算式，程序写起来并不方便。
• 自顶向下枚举：枚举最顶层的运算符，并把所有变量分成两组放在运算符的两边，然后递归地枚举两边的算式。这种做法需要枚举「所有变量的集合」的所有子集，写程序也不方便。
• 自底向上枚举：把每个变量都看作算式，每次任取两个算式和一个运算符，组成新算式后放回算式集合，并递归下去，直到集合中只剩一个算式为止。这种思路，在递归的每一层上要做的事情是最简单的，所以本文将采用这种思路。

一、算式的表示方式

　　在枚举算式之前，我们首先要设计算式的表示方式。最简单的办法是使用字符串。但在下文中可以看到，为了判断在哪里需要加括号，以及避免重复，我们需要从算式中提取一些信息，而从字符串中提取这些信息就很不方便了。于是我们选用树形结构来表示算式。一个算式表示为一棵树，树的内部结点为运算符，叶子结点为变量。例如，a / (b * (c + d)) 这个算式就用如下的树来表示：

　　树的结点可以用一个类来实现，目前它只需要三个属性：一个字符（运算符或者表示变量的字母），一个左孩子指针，一个右孩子指针。用 Python 语言实现如下：

class Node:
    def __init__(self, ch = None, left = None, right = None):
        self.ch = ch
        self.left = left
        self.right = right

　　既然开始设计算式的表示方式了，我们就顺便考虑一下怎么输出一个算式，即怎么把一棵树转换成一个字符串。这也是一个递归的过程：

• 如果根结点的字符是个字母，那么这棵树仅代表一个变量，只需输出相应的字母；
• 否则，这棵树代表一个算式，可以将两棵子树分别转换成字符串后，用根结点的运算符连接起来。

　　这里有一个比较麻烦的问题，就是两棵子树转换成的字符串，可能需要加括号。我们当然可以不分青红皂白地一律加括号，但这样输出的算式读起来就比较困难。最省括号的方法如下：

• 如果子树只代表一个变量，那么不加括号；
• 左子树需要加括号的情况为：根的运算符的优先级高于左子树，即根的运算符为乘除，左子树的运算符为加减；
• 右子树需要加括号的情况有三种：
• 根的运算符的优先级高于右子树，即根的运算符为乘除，右子树的运算符为加减；
• 根的运算符为减，右子树的运算符为加减；
• 根的运算符为除，右子树的运算符为乘除。
• 右子树需要加括号的三种情况，可以合并为：根的运算符为除，或者根的运算符为乘减，且右子树的运算符为加减。

由此可以实现 Node 类的 __str__ 方法，这样就可以通过 str(root) 把一棵树表示的算式输出出来了。

    def __str__(self):
        if self.ch not in '+-*/':
            return self.ch                              # 单变量不加括号
        left = str(self.left)                           # 左子树转字符串
        right = str(self.right)                         # 右子树转字符串
        if self.ch in '*/' and self.left.ch in '+-':
            left = '(' + left + ')'                     # 左子树加括号
        if self.ch == '/' and self.right.ch in '+-*/' or \
           self.ch in '*-' and self.right.ch in '+-':
            right = '(' + right + ')'                   # 右子树加括号
        return left + ' ' + self.ch + ' ' + right       # 用根结点的运算符相连

二、朴素的枚举算法

　　下面我们实现开头所说的「自底向上」的枚举算法，即每次取两个算式和一个运算符，并把运算结果放回集合。

def DFS(trees):                                         # trees 为当前算式列表
    if len(trees) == 1:
        yield str(trees[0])                             # 只剩一个算式，输出
        return
    for i in range(len(trees)):                         # 枚举一棵子树
        for j in range(i + 1, len(trees)):              # 枚举另一棵子树
            for node in actions(trees[i], trees[j]):    # 枚举运算符
                new_trees = [trees[k] for k in range(len(trees)) if k != i and k != j] + [node]
                                                        # 从集合中去掉两棵子树，并加入运算结果
                for expression in DFS(new_trees):       # 递归下去
                    yield expression

　　我在输出结果时使用了 yield 而不是 print 语句，这样 DFS 函数将成为一个 generator，方便主程序捕捉到所有算式，并进行「统计个数」等后续工作。actions 函数接收两棵子树，枚举根结点的运算符，并返回它们组成的整棵树。由于在 DFS 函数中我们限定了 i < j，所以 actions 函数也要枚举输入的两棵子树谁在左，谁在右。

def actions(left, right):
    for op in '+-*/':
        yield Node(op, left, right)
        yield Node(op, right, left)

我之所以把 actions 单独写成一个函数，是因为后续文章中，大部分的改进都体现在这个函数上。

　　有了上面这些函数后，就可以通过如下的主程序来输出所有由 4 个变量组成的算式了：

n = 4                                               # 变量个数
trees = [Node(chr(97 + i)) for i in range(n)]       # 初始时有 n 个由单变量组成的算式
expressions = list(DFS(trees))
for ex in expressions:
    print ex

用 len(expressions) 可以获得算式的总数，结果是 9216。不难验证， 在 n = 4 时确实等于 9216。

三、算式重复的统计

　　用上文的方法枚举出的 9216 个算式中，会有很多重复，例如算式 a + b + c + d 就会出现 6 次。除了严格的重复以外，还会有很多等价的算式，比如 b + d + c + a 就跟 a + b + c + d 是等价的。我们来统计一下这些算式中，不重复、不等价的算式各有多少个。

　　「不重复」很好统计。主程序执行完毕后，expressions 列表保存了所有的算式，那么len(set(expressions))就可以给出不重复的算式的个数了。

　　「不等价」则困难一些，但我们可以投机取巧。给所有的变量都取一个比较大的随机数代进去，这样不等价的算式就几乎一定算出不等价的结果。为了保持精度，我们用 Python 提供的分数类（fractions）表示中间结果。统计不等价的算式个数的代码如下：

from fractions import Fraction
a = Fraction(31415); b = Fraction(92653); c = Fraction(58979); d = Fraction(32384)
print len(set(eval(ex) for ex in expressions))

　　由此可以统计出，在 9216 个算式中，不重复的算式有 5856 个，不等价的算式仅有 1170 个。

四、算式重复的原因

　　在「24 点」这个应用中，对重复或等价的算式逐个检查是否等于 24，是纯粹浪费时间。所以在枚举算式时，我们希望在重复或等价的算式中，仅枚举一个代表。为此，我们需要弄清重复和等价算式产生的原因。在下文中，我们提到重复时，也包括等价。

　　产生重复算式的最明显的原因，就是加法和乘法具有交换律和结合律。a + b 等价于 b + a，而下面两棵树都会输出 a + b + c。

　　当加减法混合，或者乘除法混合的时候，有时也会有结合律，例如 (a + b) - c 等价于 a + (b - c)。除此之外，减法和除法还可以通过「去括号」形成等价的算式，例如 a - (b + c) 等价于 a - b - c，a / (b / c) 等价于 a / b * c。

　　减法还有一个特别烦人的性质，即交换被减数与减数（下简称反转减号）时，结果只差一个负号。若在一个算式中反转某一个减号，而算式中另外一个地方有一个加或减号可以配合它变成减或加号，那么就可以得到等价算式。例如，a + (b / (c - d)) 等价于 a - (b / (d - c))，这里最上层的加号变成了减号，以配合 c、d 的交换。另外，若一个单项式中含有多个减号，就也可以同时反转两个减号，得到等价算式，例如 (a - b) * (c - d) 等价于 (b - a) * (d - c)。之所以说这个性质特别烦人，是因为它的作用不是局部的，而是可以影响到树中相距甚远的两个部分。

　　上面列举的原因，全都与四则运算的性质有关。但是，算式的重复，还有一个与四则运算性质无关，而仅与运算顺序有关的原因。我们看算式 (a + b) * (c - d)：这里面的加法和减法互不依赖，或者可以称为「独立」的。在递归过程中，有可能第一层计算加法、第二层计算减法，也有可能第一层计算减法、第二层计算加法，但这两条路径到了第三层时都会面临同样的算式集合 [a+b, c-d]，之后不管进行什么运算，都会得到重复的算式。这种产生重复的原因，可以概括为「独立运算的顺序不唯一」。

　　本系列专栏的后面两篇文章，就来研究如何避免这五种重复。本篇为上篇；中篇暂时忽略减法与除法，介绍如何避免由交换律、结合律、独立运算顺序不唯一造成的重复；下篇重新引入减法与除法，介绍如何进一步避免由去括号、反转减号造成的重复。