生成所有可能的“唯一”的RPN（逆波兰表示法）表达式。

Question

我希望在Python中生成所有可能的逆波兰表达式（Reverse Polish notation），使用输入列表中的字母（例如['a', 'b', 'c']）并包含运算符['+', '-', '*', '/']。

我的想法是，我们可以向当前表达式添加元素，直到发生以下情况之一：要么我们已经使用了所有字母，要么表达式已完成（即我们不能再添加更多运算符）。

因此，我编写了以下函数：

1）

'''
The function returns True if we can add operator to current expression:
we scan the list and add +1 to counter when we meet a letter
and we add -1 when we meet an operator (it reduces
last two letters into 1 (say ab+ <--> a + b)
''' 
def can_add_operator(string_):
    n = 0
    for letter in string_:
        if letter not in ['+', '-', '*', '/']:
            n += 1
        else:
            n -= 1
    result = n > 1
    return result


    can_add_operator('ab*c+')) #False
    can_add_operator('ab*c')  #True

2)

'''
The function returns a list, that contains operators and
letters, one of which we can add to the current expression.
'''

def possible_elements(items, string_):
    #list of all letters that we have not used yet
    result =  [x for x in items if x not in string_]
    if can_add_operator(string_):
        result = ["+", "-", "*", "/"] + result
    return result

letters = ['a', 'b', 'c', 'd']
possible_elements(letters, 'ab*c') #['+', '-', '*', '/', 'd']
possible_elements(letters, '') #['a', 'b', 'c', 'd']
possible_elements(letters, 'ab*c+d+') #[]

3) 接下来我将其包装成递归：

#exp -- current expression, base of recursion is exp = ''
def rec(exp, Final_sol = []):
    elements_to_try = possible_elements(letters, exp)
    for i in elements_to_try:
        if len(possible_elements(letters, exp + i)) == 0:
            Final_sol.append(exp + i)
        else:
            rec(exp+i, Final_sol)
    return Final_sol

#we start with an empty string
Final_sol = rec('')
print(len(Final_sol)) #7680

那个函数有两个难点：

1. The first one is that if there are repeated letters in list of letters, it won't return all possible results.

   For example if letters = ['a', 'b', 'a']:

   Final_sol = rec('')
   print(len(Final_sol)) #32
   str(Final_sol)
   >> "['ab+', 'ab-', 'ab*', 'ab/', 'ba+', 'ba-', 'ba*', 'ba/', 'ba+', 'ba-', 
   'ba*', 'ba/', 'ab+', 'ab-', 'ab*', 'ab/', 'ab+', 'ab-', 'ab*', 'ab/', 'ba+', 
   'ba-', 'ba*', 'ba/', 'ba+', 'ba-', 'ba*', 'ba/', 'ab+', 'ab-', 'ab*', 
    'ab/']"
   

   So the output missing 'ab+a+' and so on. But I do want to return all possible combinations in that case too.

2. The second problem is that there are many "equivalent" strings in the output. Since we have the commutative and associative properties in prefix form, expressions like ab+c+/abc++/ca+b+ should be considered as equivalent: I want only one of each group in the output of the function rec().

我们如何修改上述函数以克服这些困难？什么是解决问题的最优雅的方法？

- Dima

---

你认为哪些表达式是不同的？例如，ab+ 和 ba+ 是不是不同的？abc++ 和 ab+c+ 呢？（根据你对第一个问题的回答，ca+b+ 等等呢？） - rici

@rici 嗯，这是一个很好的问题。一开始我没有考虑到这种情况 :) 如果我能够生成“distinct”（不同）的前缀形式，以便ab+/ba+和abc++/ab+c+等都提供不同的结果，那将是最好的。 - Dima

@Dima：通过对所有输入（包括子表达式！）定义顺序并要求可交换运算符的操作数以递增顺序出现（因此根本不允许ba+），可以排除某些平凡等价的表达式。 - Davis Herring

为什么我们在字母用完之前不能在表达式前添加内容呢？例如：<letter> + 可以安全地添加到任何逆波兰表达式中。 - hidefromkgb

@MatrixTai 我想使用所有元素。 - Dima

Answer 1

第一个问题是，如果字母列表中有重复的字母，它将不会返回所有可能的结果。 我们可以通过使用不同的方法来生成排列来解决这个问题：

from itertools import permutations

variables = ['a', 'a', 'b', 'c']

operators = ['+', '-', '*', '/']

equations = set()

for permutation in permutations(variables):
    a, b, *rest = permutation

    operations = permutations(operators)

    for permutation in operations:

        equation = zip([a + b, *rest], permutation)

        equations.add("".join(variable + operator for variable, operator in equation))

使用 set() 可以消除由重复变量引起的任何重复。

第二个问题是输出中有许多“等效”字符串。由于我们拥有交换律和结合律属性

为了处理可交换问题，我们将使用模式匹配来简化方程：

import sys
import re

DEBUG = True

remove = set()

# Reduce commutative equivalents: ca*a-b/ same as ac*a-b/
if DEBUG:
    print("Reduce commutative equivalents:", file=sys.stderr)

for equation in equations:
    if equation not in remove:
        for match in re.finditer(r"(?=(.+)(\w)[+*])", equation):

            a, _ = match.span(1)
            _, d = match.span(2)

            equivalent = equation[:a] + match[2] + match[1] + equation[d:]

            if equivalent != equation and equivalent in equations:
                remove.add(equivalent)
                if DEBUG:
                    print(f"Removed {equivalent} same as {equation}", file=sys.stderr)

equations -= remove

因为我们已经将所有的方程式都建立为ab op c op d op等形式，我认为我们没有生成关联等效项，但如果我们这样做了，我们可以使用类似的技术来尝试精简它们：

remove = set()

# Reduce associative equivalents aa+b*c- same as ab*ab*+c-
if DEBUG:
    print("Reduce associative equivalents:", file=sys.stderr)

for equation in equations:
    if equation not in remove:
        for match in re.finditer(r"(?=(\w)([+])(\w)([*]))", equation):

            a, _ = match.span(1)
            _, d = match.span(4)

            equivalent = equation[:a] + match[3] + match[4] + match[1] + match[3] + match[4] + match[2] + equation[d:]

            if equivalent != equation and equivalent in equations:
                remove.add(equivalent)
                if DEBUG:
                    print(f"Removed {equivalent} same as {equation}", file=sys.stderr)

equations -= remove

最后，我们将输出我们的简化集合：

if DEBUG:
    print("Final equations:", file=sys.stderr)

print(equations)

输出

> python3 test.py
Reduce commutative equivalents:
Removed ac+a-b/ same as ca+a-b/
Removed ab*a/c- same as ba*a/c-
Removed cb*a/a- same as bc*a/a-
Removed ac+b-a/ same as ca+b-a/
Removed ba+c/a- same as ab+c/a-
Removed ba+a-c/ same as ab+a-c/
Removed ac+a/b- same as ca+a/b-
Removed ac+b/a- same as ca+b/a-
Removed ac*b-a/ same as ca*b-a/
Removed bc*a-a/ same as cb*a-a/
Removed ca*a-b/ same as ac*a-b/
Removed ba*a-c/ same as ab*a-c/
Removed cb+a/a- same as bc+a/a-
Removed ba+c-a/ same as ab+c-a/
Removed ca*a/b- same as ac*a/b-
Removed ca*b/a- same as ac*b/a-
Removed ba+a/c- same as ab+a/c-
Removed ab*c-a/ same as ba*c-a/
Removed ab*c/a- same as ba*c/a-
Removed cb+a-a/ same as bc+a-a/
Reduce associative equivalents:
Final equations:
{'ca+a-b/', 'cb*a+a-', 'aa/b-c*', 'ba/c-a*', 'cb/a-a*', 'ab+a*c/', 'aa/c+b-',
'bc/a-a+', 'aa*b+c-', 'ba*a/c-', 'ab+c/a*', 'ca-a/b+', 'ca-b+a*', 'bc*a/a-',
'bc/a+a*', 'ac+a/b*', 'bc+a*a-', 'ca/a-b+', 'ac-a*b+', 'ba-a*c/', 'ac/b-a*',
'ba-c+a*', 'ba+a-c*', 'aa+b/c-', 'ca-b*a/', 'ca+b-a/', 'ab+c/a-', 'ac*b+a-',
'aa+c-b/', 'aa*c/b-', 'ab/c*a+', 'ac+b/a*', 'aa+b*c/', 'ab-a*c+', 'ac+a-b*',
'cb-a+a*', 'cb*a/a+', 'ab-c/a+', 'ac*b+a/', 'ba*c/a+', 'ba/c+a*', 'aa-b*c+',
'aa/b+c*', 'ab-c*a+', 'ac+a*b/', 'ac/b+a-', 'aa*b-c+', 'ac-a+b/', 'aa-c*b+',
'ab+a-c/', 'aa-c+b/', 'ba+c*a/', 'ca-b*a+', 'ab-a/c*', 'aa-b/c+', 'ac*a+b/',
'ba/a+c-', 'ba-c/a+', 'cb/a+a*', 'ca+b/a*', 'aa/c*b+', 'ac-a+b*', 'ba-a+c*',
'ca+a*b/', 'aa+b/c*', 'aa/c-b+', 'bc*a/a+', 'ca+a/b-', 'ca+b/a-', 'ca*b-a/',
'ac/b*a-', 'aa*b/c+', 'ba/a*c+', 'bc/a*a+', 'ca-b+a/', 'ac/b+a*', 'aa*b/c-',
'bc-a+a/', 'ca/b-a*', 'ba-c*a/', 'cb*a-a/', 'ba-c/a*', 'aa*b+c/', 'ac*a-b/',
'ca*b/a+', 'aa+b-c*', 'ba/a-c*', 'ca-b/a+', 'ab/c-a+', 'cb+a/a*', 'aa-c/b*',
'ba+c*a-', 'cb*a+a/', 'aa*c/b+', 'ab/c+a*', 'ca+b-a*', 'aa+b-c/', 'ac-b*a/',
'ab*a-c/', 'ba-a*c+', 'ba*c+a-', 'bc/a*a-', 'ba*c-a+', 'ba/c*a+', 'ab-c+a/',
'ba*c+a/', 'ca*a-b+', 'bc+a/a-', 'aa+c*b-', 'ab+c*a-', 'ac-a/b+', 'ca+a-b*',
'aa+c-b*', 'ab/c*a-', 'ab+c-a/', 'bc+a/a*', 'ac-a/b*', 'ab/a-c*', 'ac/a-b+',
'bc-a/a+', 'ab+a*c-', 'ac/a-b*', 'ca*a+b-', 'ab/a-c+', 'ab-a*c/', 'cb/a*a-',
'ac/a+b*', 'bc-a/a*', 'ac-b+a*', 'ac*a/b-', 'ba*a+c-', 'ba/a-c+', 'bc/a+a-',
'aa/b-c+', 'cb+a-a*', 'ca-b/a*', 'ca+b*a-', 'ac*b/a-', 'ca-a+b/', 'ca/b*a-',
'ba+a/c*', 'cb-a*a+', 'ac+a*b-', 'aa*b-c/', 'aa*c-b/', 'ac/a*b+', 'aa-c+b*',
'ca*a+b/', 'ca/b+a-', 'ac*a/b+', 'aa+c/b-', 'ab/c+a-', 'ab+a/c-', 'cb-a+a/',
'ab*a-c+', 'ab-a+c*', 'ab+a/c*', 'ac/b-a+', 'ab*c+a/', 'ba/c+a-', 'ba/c*a-',
'cb-a*a/', 'ac+b*a-', 'ba+c-a*', 'ac/b*a+', 'cb/a*a+', 'cb-a/a+', 'bc*a+a/',
'ac*b/a+', 'cb+a*a-', 'ba*c-a/', 'ca-a*b/', 'ca-a*b+', 'ab/a*c-', 'ba-a+c/',
'ba*a/c+', 'bc-a+a*', 'ca+a/b*', 'ca*a/b+', 'aa*c+b-', 'ba*c/a-', 'bc/a-a*',
'ca/a+b*', 'ab-a+c/', 'ca/b*a+', 'ab-a/c+', 'cb*a-a+', 'aa-b/c*', 'ac-b/a+',
'aa*c-b+', 'ab*c+a-', 'cb/a-a+', 'ab/a+c*', 'ba+a*c-', 'ba*a+c/', 'ba-a/c*',
'aa/b+c-', 'ba/c-a+', 'ca/b-a+', 'ab*a/c+', 'bc+a-a*', 'bc*a-a+', 'ab+c*a/',
'ab-c*a/', 'ac*a+b-', 'ca/a+b-', 'ac/a*b-', 'ac+b-a*', 'ba/a+c*', 'ba-a/c+',
'ab*c/a+', 'cb/a+a-', 'ca/a-b*', 'ac-b/a*', 'ab/a*c+', 'ca*b+a/', 'ac-a*b/',
'aa/b*c+', 'aa/c-b*', 'ca/a*b+', 'bc-a*a/', 'ca+b*a/', 'aa*c+b/', 'ab*a+c/',
'bc+a*a/', 'ab-c/a*', 'ca-a+b*', 'aa-c*b/', 'cb-a/a*', 'aa+b*c-', 'ca+a*b-',
'aa-b+c*', 'ac/a+b-', 'ba-c+a/', 'ba-c*a+', 'ca*b-a+', 'ac-b+a/', 'aa-b*c/',
'aa-b+c/', 'ac*a-b+', 'ac+b*a/', 'ca/a*b-', 'bc+a-a/', 'bc-a*a+', 'ba+a*c/',
'ac*b-a+', 'aa/c+b*', 'ab/a+c-', 'ab/c-a*', 'ab-c+a*', 'ba+c/a*', 'ab*c-a+',
'ab+a-c*', 'cb+a*a/', 'ac-b*a+', 'ba/a*c-', 'ab*a+c-', 'ab+c-a*', 'bc*a+a-',
'aa/b*c-', 'ca*b+a-', 'ba*a-c+', 'ca/b+a*', 'aa-c/b+', 'aa+c/b*', 'ca-a/b*',
'aa/c*b-', 'aa+c*b/'}
> 

我并不是在宣称有一个完美的解决方案，只是为您展示一些可用的工具来解决您的问题。

- cdlane

---

（不确定我是否可以回答一个大约两年前的问题，但是我还是来试试吧）你的解决方案没有考虑到其他可能的逆波兰表达式变体。它无法生成cbaa/-*+。你怎么能让它做到呢？ - Kyle Sharp

@KyleSharp 我认为指出解决方案中的缺陷非常重要，尤其是那些长期被认为可接受的解决方案。 - Alessio Sangalli

@KyleSharp 嗯，找到了！我相信只有在使用不可交换的运算符时才会引发问题。 - undefined

Answer 2

为了创建所有可能的表达式，我们可以将每个表达式视为一个二叉表达式树，然后符号表示只是遍历树的不同方式。例如：

tree:                          *
                              / \
             +               -   c
            / \             / \
           a   b           a   b

infix:     a + b          (a - b) * c
postfix    a b +           a b - c *

由于所有必需的运算符都是二元的，所以生成的表达式树都是完全二叉树，这意味着所有非叶节点恰好有两个孩子。二元表达式树的另一个属性是所有操作数都是树的叶子，而所有内部节点都是运算符，并且内部节点（运算符）的数量比叶子（操作数）的数量少一个。

现在要创建所有可能的表达式，首先需要所有结构上不同的具有len(operands)个叶子或len(operands)-1个内部节点的完全二叉树。

我使用了这个问题的回答者编写的生成器：generate all structurally distinct full binary trees with n leaves。

下面的代码生成所有具有n个叶子的结构上不同的完全二叉树。它输出带有一些符号的树结构，你可以在函数中设置。这个设置用于显示用括号括起来的子树、操作数为x和运算符为o。例如，对于2个运算符和3个操作数：

(xo(xox))       ((xox)ox)
    o               o
   / \             / \
  x   o           o   x
     / \         / \
    x   x       x   x

from itertools import product

def expr_trees(n):
    if n == 1:
        yield 'x'

    for i in range(1, n):
        left = expr_trees(i)
        right = expr_trees(n-i)

        for l, r in product(left, right):
            yield '('+l+'o'+r+')'

for t in expr_trees(3):
    print(t)

现在，为了生成所有可能的表达式，我们需要将操作数的所有无重复排列放置在叶子节点上，并将长度为len(operands)-1的带重复运算符的所有排列放置在每个树结构的内部节点上。 在这里，我们修改生成器函数以使用操作符和操作数列表，并输出后缀表达式：

from itertools import permutations, product

def expressions(opds, oprs, idx):
    if len(opds) == 1:
        yield opds[0]

    for i in range(1, len(opds)):
        left = expressions(opds[0:i], oprs, idx+1)

        right = expressions(opds[i:], oprs, idx+1)

        for l, r in product(left, right):
            yield l+r+oprs[idx]

operands = ['a', 'b', 'c']
operators = ['+', '-', '*', '/']

operatorProducts = product(operators, repeat=len(operands)-1)
operandPermutations = permutations(operands)

for opds, oprs in product(operandPermutations, operatorProducts):
    for t in expressions(opds, oprs, 0):
        print(t)

现在来谈一下时间复杂度。以计算所有结构不同的表达式为例，假设操作数为 ['a', 'b', 'c']。

如前所述，三个操作数有两棵完全二叉树。操作数的排列组合数为 3! = 6，运算符的排列组合数为 4^2，因为我们从 4 个运算符中选择 2 个并允许重复。因此我们有：

number of expressions
    = number of trees * number of operand permutations * number of operator permutations
    = 2 * 6 * 16
    = 192

对于一般公式，有趣的部分是结构不同的二叉树数量，这是具有n个内部节点的第n个卡特兰数。您可以在计算二叉树的答案中了解更多信息。

number of trees with n internal nodes = (1 / n+1) x (2n)! / (n! x n!)

因此，具有 n 个运算符或 n+1 个操作数的结构上不同表达式的数量为：

(n+1)! x 4^n x (1/n+1) x (2n)! / (n! x n!) = 4^n x (2n)! / n!

由于此处缺乏支持，数学公式可能不太美观。其中x表示乘法。您可以在上面的链接中找到更好的格式。

请注意，n是运算符数量或操作数数量减1。

如您所见，随着n的增加，可能的表达式数量增长得非常快。

1, 8, 192, 7680, 430080, 30965760, ...

虽然有很多等效表达式，但它们只占所有表达式的一小部分，您应该考虑对操作数数量设定实际限制。

这就带来了下一个问题，即查找等效表达式。起初可能看起来很简单，因为人们可能认为它仅涉及“+”和“*”的交换律，但是存在“-”和“/”改变表达式其余部分的情况，这些情况很难通过简单的RegExp捕获。例如，“abc--”相当于“ab-c+”，因为减号对括号元素具有一元作用，更复杂的版本则具有除法的反转效应，“abcde+-*/”相当于“abcd-e-//”。将重复元素添加到操作数列表中会创建更多等效表达式，并使其更加难以全部捕获。

我发现查找所有等效表达式要复杂得多，在我看来，最好的方法是实现一个函数，扩展、简化和排序所有术语，以便您可以比较每个等效表达式组的简化版本。

- jal

---

非常感谢您抽出时间回答我的问题，尽管它没有得到悬赏。 - Dima

一个优美的答案，它从抽象的角度看待问题本身。通过删除idx参数、对递归调用进行列表切片和直接访问第0个元素，即expressions(opds[:i], oprs[1:])和yield l+r+oprs[0]，可以进一步简化expressions。 - tristanm

感谢您的反馈，@tristanm。 - jal

@jal，发现添加>3个操作数时出现了错误。调用expressions（['a'，'b'，'c'，'d']，['+'，'-'，'*']，0）会产生abcd *- +，abc * d-+，ab-cd-+，abc * -d + ，ab * c-d + 。请注意，第三个表达式包含两个-。原因是左右树都使用相同的运算符idx + 1。您能够提供任何有关这方面的信息吗？ - tristanm