生成所有可能的"唯一"RPN(反向波兰表示法)表达式

Question

我想在Python中生成所有可能的RPN(反向波兰表示法)表达式,它们使用输入列表中的字母(例如['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. 第一个是如果字母列表中有重复的字母,它将不会返回所有可能的结果.

   例如,如果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+'等等.但我确实想在这种情况下返回所有可能的组合.

2. 第二个问题是输出中有许多"等效"字符串.因为我们有可交换的和关联 的前缀形式,如表达式属性ab+c+/ abc++/ ca+b+ 应被视为等效的:我只希望在函数REC的输出每组的一个().

我们怎样才能改变上述功能来克服这些困难？什么是最优雅的问题解决方案？

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))

使用a 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 op 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/'}
> 

我没有声称一个完美的解决方案,只是说明了一些可用于解决问题的工具.

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内部节点的完整二叉树。

我使用由这个问题的回答者写的生成器：生成所有具有n个叶子的结构上不同的完整二叉树。

下面的代码用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, ...

尽管有许多等效表达式，但它们仍然是所有表达式的一小部分，您应该考虑操作数数量的实际限制。

这就引出了下一个问题，即寻找等效表达式。这似乎在第一个简单因为人们可能认为这只是大约的交换性能+和*但也有病例-和/改变是很难赶上的只是一个简单的正则表达式以复杂的方式表达的其余部分，IMO。例如abc--，ab-c+由于括号中元素的负一元效应以及带除法反演效果的更复杂版本的一元效应，abcde+-*/其等效于abcd-e-//。将重复的元素添加到操作数列表中会创建更多等效的表达式，并使捕获它们变得更加困难。

我发现查找所有等价表达式非常复杂，我认为最好的办法是实现一个扩展，简化和排序所有术语的函数，以便为每组等价表达式提供一个简化版本以进行比较。