我想在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
有与功能两个难点：
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+'等。但我想在这种情况下返回所有可能的组合了。ab+c+ / abc++ / ca+b+表达应被视为等效的：我只希望每个组中的功能REC的输出中的一个（）。我们如何可以改变上面的功能，以克服这些困难？什么是最优雅的解决问题呢？
第一个是，如果有重复字母的字母列表，它不会返回所有可能的结果。
我们可以通过使用不同的方法来生成排列攻击这个问题：
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 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)
OUTPUT
> 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 *
由于所有需要的操作符是二元的，所产生的表达式树是满二叉树，这意味着所有的非叶节点恰好有两个孩子。二进制表达式树的另一个特性是，所有操作数是树的叶子和所有内部节点的运营商，以及内部节点（运营商）的数量比叶（操作数）的数量少一个。
现在，创造一切可能的表现，首先我们需要用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因为我们选择2出4允许重复。因此，我们有：
number of expressions
= number of trees * number of operand permutations * number of operator permutations
= 2 * 6 * 16
= 192
对于通式有趣的部分是作为所述第n Catalan number n为树的内部节点的数目结构上不同的二叉树的数量。您可以在回答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, ...
虽然有许多相当的表述，他们仍然是所有表达式的一小部分，你应该想到的操作数的数量的实际限制。
这给我们带来了哪些是找到等同表述的下一个问题。因为人们可能认为这只是关于+和*的交换律，但也有改变是很难赶上的只是一个简单的正则表达式以复杂的方式表达其余-和/的情况下，IMO它可能看起来很简单，在第一。例如abc--相当于ab-c+的，因为负的对括号的元素和更复杂的版本与分裂的反转作用，abcde+-*/这相当于abcd-e-//的一元效果。添加重复元素的操作数的列表中创建多个等同的表达，使之更加难以赶上他们。
我觉得它更复杂，找到所有的相当的表述，在我看来最好的办法是实现一个可扩展，简化并让你有每个组等效表述的简化版本进行比较排序的所有条款的功能。