本系列的中篇暂时忽略了减法和除法，介绍了如何避免交换律、结合律、独立运算顺序不唯一造成的重复。本文将重新引入减法和除法，研究如何避免「去括号」和「反转减号」造成的重复。其中，「反转减号」的处理尤为困难。

　　首先，我们把减法和除法重新加入 actions 函数：

def actions(left, right):
    for op in '+*':
        if op != left.ch and (op != right.ch or left.id < right.left.id):
           yield Node(op, left, right)
    for op in '-/':
        yield Node(op, left, right)
        yield Node(op, right, left)

一、避免「去括号」造成的重复

　　当若干个加、减法运算混合时，减法的去括号可以产生 a - (b + c - d) 与 a - b - c + d 这种等价算式，我们要从中选一个做代表。一个很诱人的想法是选择 a - b - c + d 这个无括号的算式为代表。可惜的是，无括号算式对应的树是向左分叉的，而我们针对交换律的改进已经排除了根结点为加法且向左分叉的树了。好在我们还可以选择形如 (a + d) - (b + c) 的算式做代表，即只允许最上层运算为减法，它的两棵子树必须都若干项相加而成。换句话说，就是在树中，加号和减号的孩子都不能是减号。

　　上面的分析同样适用于乘法和除法。我们选择形如 (a * d) / (b * c) 的算式，作为乘、除法混合运算的代表。体现在树中，就是乘号和除号的孩子都不能是除号。

　　加入了以上限制条件的 actions 函数如下所示。由于条件开始变得复杂了，我们就把加、减、乘、除四种运算分开来写。

def actions(left, right):
    # 加法：两个孩子都不能是减号；左孩子还不能是加号；
    #       若右孩子是加号，则左孩子和右孩子的左孩子要满足单调性
    if left.ch not in '+-' and right.ch != '-' and (right.ch != '+' or left.id < right.left.id):
        yield Node('+', left, right)
    # 减法：两个孩子都不能是减号
    if left.ch != '-' and right.ch != '-':
        yield Node('-', left, right)
        yield Node('-', right, left)
    # 乘法：两个孩子都不能是除号；左孩子还不能是乘号；
    #       若右孩子是乘号，则左孩子和右孩子的左孩子要满足单调性
    if left.ch not in '*/' and right.ch != '/' and (right.ch != '*' or left.id < right.left.id):
        yield Node('*', left, right)
    # 除法：两个孩子都不能是除号
    if left.ch != '/' and right.ch != '/':
        yield Node('/', left, right)
        yield Node('/', right, left)

二、避免「反转减号」造成的重复

　　为了避免「反转减号」造成的重复，我们定义一个概念，叫算式的「极性」。a - b 和 b - a 这两个算式只差一个负号，我们就称它们是有极性的，并从中任选一者称为正极性，另一者称为负极性。而像 a + b、a * b 这种算式，找不到与它们只差一个负号的算式，那么就称为无极性。更一般的极性定义为：

　　如果一个算式可以通过交换若干减号的被减数与减数，或者把加号改成减号、减号改成加号而变成自己的相反数，那么就称一个算式是有极性的；这个算式和它的相反数中，任选一者称为正极性，另一者称为负极性。

　　这个极性有什么用呢？举个例子：我们定义 a - b 为正极性，b - a 为负极性；c - d 为正极性，d - c 为负极性。把 a - b 与 c - d 这两个正极性的算式相乘，可以得到 (a - b) * (c - d)；把 b - a 与 d - c 这两个负极性的算式相乘，可以得到等价算式 (b - a) * (d - c)。极性可以帮助我们识别出这样的等价算式，并在其中选择一者为代表，而舍弃另一者。

　　我们往 Node 类的定义中再添加一个属性 polar，用来表示算式的极性。正、负、无极性分别用 +1、-1、0 表示。

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

　　显然，初始时由单个变量组成的算式，都没有极性。我们下面要解决的问题，就是如何计算两个算式经过一步运算之后结果的极性，以及如何利用极性识别出等价算式。

　　这里，乘、除法是相对简单的。我们分三种情况讨论：

• 如果相乘或相除的两个算式都没有极性，那么结果也没有极性。
• 如果相乘或相除的两个算式中有一者有极性，那么可以定义结果的极性与有极性的一者极性相同。举个例子：假设一个算式 X 有正极性（即通过反转其中某些减号变成 -X），另一个算式 Y 无极性。那么 X * Y、X / Y、Y / X 这三个算式就会有与之成对的 (-X) * Y、(-X) / Y、Y / (-X)，故可以把前三者定义为正极性，后三者定义为负极性。这里面没有等价算式。
• 如果相乘或相除的两个算式都有极性，情况就比较复杂了。考虑两个有极性的算式 X 和 Y。以乘法为例，X、Y 和它们的相反数可以乘出四种结果：X * Y、X * (-Y)、(-X) * Y、(-X) * (-Y)。这四个式子两两等价，而两组等价的式子互为相反数。我们不妨选择 X * Y 和 X * (-Y) 为代表，并定义 X * Y 为正极性，X * (-Y) 为负极性；另外两个算式则作为这两个算式的等价算式而被舍弃。总结一下是这样：若左子树的极性为正，则结果被选为代表，且极性与右子树相同；若左子树的极性为负，则结果被舍弃。这种处理方法同样适用于除法。

　　下面看加、减法，它们必须放到一起来看。同样分三种情况：

• 如果相加的两个算式 X、Y 都没有极性，那么结果 X + Y 也没有极性；如果相减的两个算式 X、Y 都没有极性，那么就在 X - Y 和 Y - X 中任取一者定义为正极性，另一者定义为负极性。
• 如果 X 有极性，Y 无极性，那么 X、-X 与 Y 相加减可以得到如下 6 个算式：
  [1] X + Y, [2] (-X) + Y, [3] X - Y, [4] (-X) - Y, [5] Y - X, [6] Y - (-X)
  其中 [1]、[4] 互为相反数，[2]、[3] 互为相反数；[2]、[5] 等价，[1]、[6] 等价。我们舍弃 [5]、[6]，并定义 [1]、[3] 为正极性，[2]、[4] 为负极性。总结一下是这样：有极性与无极性相加，结果的极性与有极性者相同；有极性减无极性，结果的极性也与有极性者相同；无极性减有极性，结果舍弃。（注意！此处有猫腻，详见文末 11730 更新）
• 如果 X、Y 都有极性，那么 X、-X 与 Y、-Y 相加减可以得到如下 12 个算式：
  [1] X + Y, [2] (-X) + Y, [3] X + (-Y), [4] (-X) + (-Y),
  [5] X - Y, [6] (-X) - Y, [7] X - (-Y), [8] (-X) - (-Y),
  [9] Y - X, [10] Y - (-X), [11] (-Y) - X, [12] (-Y) - (-X)
  其中 [1]、[4] 互为相反数，[2]、[3] 互为相反数；[1]、[7]、[10] 等价，[2]、[8]、[9] 等价，[3]、[5]、[12] 等价，[4]、[6]、[11] 等价。于是，[5] ~ [12] 这八个算式应当全部舍弃，并可以定义 [1]、[2] 为正极性，[3]、[4] 为负极性。总结一下是这样：两个有极性的算式相加，结果的极性与右子树相同；两个有极性的算式相减，结果舍弃。

　　我们在 actions 函数中实现上面的讨论，这包括计算两个算式运算结果的极性，以及识别、舍弃等价算式。很不幸，代码变得十分冗长了。代码的逻辑顺序与上面的讨论不尽相同，请逐条对照。

def actions(left, right):
    # 加法：两个孩子都不能是减号；左孩子还不能是加号；
    #       若右孩子是加号，则左孩子和右孩子的左孩子要满足单调性
    if left.ch not in '+-' and right.ch != '-' and (right.ch != '+' or left.id < right.left.id):
        if left.polar == 0 or right.polar == 0:
            yield Node('+', left, right, left.polar + right.polar)  # 无极性 + 无极性 = 无极性
                                                                    # 有极性 + 无极性 = 有极性者的极性
        else:
            yield Node('+', left, right, right.polar)               # 有极性 + 有极性 = 右子树极性
    # 减法：两个孩子都不能是减号
    if left.ch != '-' and right.ch != '-':
        if left.polar == 0 and right.polar == 0:                    # 无极性 - 无极性：
            yield Node('-', left, right, 1)                         # 正过来减是正极性
            yield Node('-', right, left, -1)                        # 反过来减是负极性
        else:
            if left.polar == 0:
                yield Node('-', right, left, right.polar)           # 有极性 - 无极性 = 有极性者的极性
                                                                    # （无极性 - 有极性 = 舍弃）
                                                                    # （有极性 - 有极性 = 舍弃）
            if right.polar == 0:
                yield Node('-', left, right, left.polar)            # 同上
    # 乘法：两个孩子都不能是除号；左孩子还不能是乘号；
    #       若右孩子是乘号，则左孩子和右孩子的左孩子要满足单调性
    if left.ch not in '*/' and right.ch != '/' and (right.ch != '*' or left.id < right.left.id):
        if left.polar == 0 or right.polar == 0:
            yield Node('*', left, right, left.polar + right.polar)  # 无极性 * 无极性 = 无极性
                                                                    # 有极性 * 无极性 = 有极性者的极性
        elif left.polar > 0:
            yield Node('*', left, right, right.polar)               # 正极性 * 有极性 = 右子树极性
                                                                    # （负极性 * 有极性 = 舍弃）
    # 除法：两个孩子都不能是除号
    if left.ch != '/' and right.ch != '/':
        if left.polar == 0 or right.polar == 0:
            yield Node('/', left, right, left.polar + right.polar)  # 无极性 / 无极性 = 无极性
                                                                    # 有极性 / 无极性 = 有极性者的极性
                                                                    # 无极性 / 有极性 = 有极性者的极性
            yield Node('/', right, left, left.polar + right.polar)  # 同上
        else:
            if left.polar > 0:
                yield Node('/', left, right, right.polar)           # 正极性 / 有极性 = 右子树极性
                                                                    # （负极性 / 有极性 = 舍弃）
            if right.polar > 0:
                yield Node('/', right, left, left.polar)            # 同上

　　到此，我们终于避免了所有五种原因造成的重复。可以验证，最终版程序可以不重不漏地枚举四则运算式！

三、总结

　　本文解决了减法和除法中由「去括号」和「反转减号」造成的重复，修改主要体现在 actions 函数中。为了排除由「反转减号」造成的重复，我们定义了算式的极性。极性在运算中的传递规律非常复杂，造成 actions 函数冗长而不优雅，我也很无奈。

　　用最终版程序可以算出，由 n 个变量经四则运算可以组成的算式个数为：

这个数列也被 The Online Encyclopedia of Integer Sequences 收录：

值得一提的是，这个数列是由一位中国网友杜朝晖（音）贡献的；页面上两个参考文献链接，一个（已失效）指向一个中文数学论坛，一个指向百度贴吧。

　　本系列文章虽然解决了枚举由 n 个变量组成的四则运算式时的去重问题，但仍有许多有趣的扩展问题有待研究。它们包括：

• 已知 n 个具体数值，不重复地枚举它们组成的四则运算式。这里的难点在于，具体数值中可能含有 0 和 1，它们的运算也容易产生 0 和 1。而 0 是加法单位元，1 是乘法单位元；0 与加减法结合、1 与乘除法结合会产生大量的等价算式。此外，还需要考虑「0 不能做除数」的限制。
• 已知若干变量，但其中有些变量出现多次（例如 3 个 a、2 个 b），不重复地枚举它们组成的四则运算式。变量的多次出现本身就会造成许多重复算式；另外同一个变量经减法、除法运算会得到 0 和 1，于是就也面临「加、乘法单位元」和「0 不能做除数」的问题。
• 已知 n 个变量，不枚举它们组成的四则运算式，而只是求不等价算式的个数。换句话说，求 OEIS 中数列 A140606 的通项公式。如果求不出通项公式，也可以求复杂度较低的递推公式，或者求一个渐近的通项公式。这将是一个既有趣又有难度的组合数学问题。

　　本系列文章的完整代码，可以在 GitHub 上获得：

MaigoAkisame/enumerate-expressions​github.com

10901 更新： @终军弱冠 给出了算式计数的递推算法，详见他的专栏文章：

终军弱冠：关于四则运算表达式计数问题的讨论​zhuanlan.zhihu.com

10921 更新： @终军弱冠 利用 Smooth implicit-function schema，进一步给出了算式数目的渐进表达式：

终军弱冠：关于四则运算表达式数量的渐进近似​zhuanlan.zhihu.com

11730 更新：关于「有极性 ± 无极性」运算结果的极性判断，我最初写的是规定 [1] X + Y 与 [2] (-X) + Y 两个相加的算式为正极性，[3] X - Y 与 [4] (-X) - Y 两个相减的算式为负极性。在这种规则下，我验证了 6 个变量以内，算式枚举不重不漏。

　　但是， @hqztrue 在 GitHub 上指出，当有 7 个变量时，我的程序会漏解：

漏掉的算式均为以下形式之一：

• ((a - b) * c + d - e) / (f - g)
• ((a - b) / c + d - e) / (f - g)
• (c / (a - b) + d - e) / (f - g)

漏解的原因在于，(a - b) * c + d - e 及其相反数算式 (b - a) * c + e - d，都是由「有极性 - 无极性」运算得来的，它们都被标记为负极性，这违反了「互为相反数的算式极性一正一负」的初衷。当它们与有极性算式 f - g 相除时，就都落入了「负极性 / 有极性 = 舍弃」的陷阱，造成了漏解。这种情况至少需要 7 个变量才会暴露出来。

　　在本次更新中，对于「有极性 ± 无极性」运算结果的极性，我改为规定 [1]、[3] 为正极性，[2]、[4] 为负极性，即让结果继承有极性算式的极性。文中与 GitHub 上的代码均做了相应的更新，GitHub 上还添加了一个专用于计数的 C++ 版本。经 C++ 版本验证，到 9 个变量为止，算式总数均与 A140606 一致，且正、负极性的算式数目相同。不过，我仍无法证明修改后的规则对于任意多的变量都是正确的。