生成所有可能的 "unique" RPN（逆波兰表示法）表达式
Generating all possible "unique" RPN (Reverse Polish notation) expressions
我想在 Python 中生成所有可能的 RPN (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
该函数有两个困难：
第一个是如果列表中有重复字母
字母，它不会 return 所有可能的结果。
例如如果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/']"
所以输出缺少'ab+a+'等等。但我确实想要 return 全部
在那种情况下也是可能的组合。
第二个问题是"equivalent"字符串
输出。因为我们有 commutative and associative
前缀形式的属性，表达式如 ab+c+/abc++/ca+b+
应该被认为是等价的：我只想要每个组中的一个
函数 rec().
我们如何改变上述功能来克服这些困难？问题最优雅的解决方案是什么？
The first one is that if there are repeated letters in list of
letters, it won't return all possible results.
我们可以通过使用不同的方法生成排列来解决这个问题：
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() 将消除由重复变量引起的任何重复。
The second problem is that there are many "equivalent" strings in the
output. Since we have the commutative and associative properties
为了处理可交换问题，我们将使用模式匹配来简化方程：
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/'}
>
我并不是在宣称一个完美的解决方案，只是说明了一些可用于解决您的问题的工具。
为了创建所有可能的表达式，我们可以将每个表达式都视为一个 binary expression tree，然后符号将只是以不同方式遍历树的问题。例如：
tree: *
/ \
+ - c
/ \ / \
a b a b
infix: a + b (a - b) * c
postfix a b + a b - c *
由于所有必需的运算符都是二元的，因此生成的表达式树是完整的二叉树，这意味着所有非叶节点都恰好有两个子节点。二叉表达式树的另一种属性是所有操作数都是树的叶子，所有内部节点都是运算符，内部节点（运算符）的个数比叶子（操作数）的个数少1。
现在要创建所有可能的表达式，首先我们需要具有 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 个 Catalan number with n being the number of internal nodes of the tree. You can read more about it at the answer to Counting binary trees。
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，IMO 来捕捉。例如 abc-- 等价于 ab-c+ 因为减号对括号元素的一元效应和更复杂的版本具有除法的反转效果，abcde+-*/ 等价于 abcd-e-//.将重复元素添加到操作数列表中会创建更多等价表达式，并使捕获所有元素变得更加困难。
我发现找到所有等价表达式非常复杂，在我看来你最好的选择是实现一个函数来扩展、简化和排序所有术语，这样你就有了每组等价表达式的简化版本用于比较。
我想在 Python 中生成所有可能的 RPN (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
该函数有两个困难：
第一个是如果列表中有重复字母 字母，它不会 return 所有可能的结果。
例如如果
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/']"所以输出缺少
'ab+a+'等等。但我确实想要 return 全部 在那种情况下也是可能的组合。第二个问题是"equivalent"字符串 输出。因为我们有 commutative and associative 前缀形式的属性，表达式如
ab+c+/abc++/ca+b+应该被认为是等价的：我只想要每个组中的一个 函数 rec(). 的输出
我们如何改变上述功能来克服这些困难？问题最优雅的解决方案是什么？
The first one is that if there are repeated letters in list of letters, it won't return all possible results.
我们可以通过使用不同的方法生成排列来解决这个问题：
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() 将消除由重复变量引起的任何重复。
The second problem is that there are many "equivalent" strings in the output. Since we have the commutative and associative properties
为了处理可交换问题，我们将使用模式匹配来简化方程：
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/'}
>
我并不是在宣称一个完美的解决方案，只是说明了一些可用于解决您的问题的工具。
为了创建所有可能的表达式，我们可以将每个表达式都视为一个 binary expression tree，然后符号将只是以不同方式遍历树的问题。例如：
tree: *
/ \
+ - c
/ \ / \
a b a b
infix: a + b (a - b) * c
postfix a b + a b - c *
由于所有必需的运算符都是二元的，因此生成的表达式树是完整的二叉树，这意味着所有非叶节点都恰好有两个子节点。二叉表达式树的另一种属性是所有操作数都是树的叶子，所有内部节点都是运算符，内部节点（运算符）的个数比叶子（操作数）的个数少1。
现在要创建所有可能的表达式，首先我们需要具有 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 个 Catalan number with n being the number of internal nodes of the tree. You can read more about it at the answer to Counting binary trees。
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，IMO 来捕捉。例如 abc-- 等价于 ab-c+ 因为减号对括号元素的一元效应和更复杂的版本具有除法的反转效果，abcde+-*/ 等价于 abcd-e-//.将重复元素添加到操作数列表中会创建更多等价表达式，并使捕获所有元素变得更加困难。
我发现找到所有等价表达式非常复杂，在我看来你最好的选择是实现一个函数来扩展、简化和排序所有术语，这样你就有了每组等价表达式的简化版本用于比较。