什么python代码为二元运算符生成所有可能的分组(树)

Question

正如在几个SO问题中所解释的那样,并且在mathworld中更抽象地解释,加泰罗尼亚数字的序列恰好对应于可以为任何给定数量的运算符生成的括号分组的数量.但我还没有找到生成所有这些分组的算法.

该二进制包围算法对应于Tamari Lattice,并且可以以多种不同方式描述.该算法最明显的实际用途是通过围绕二元运算符和它们运算的数字的每个可能的包围来生成所有可能的表达式.这可以用于穷举测试二叉树上的各种类型的操作.

网络搜索确实揭示了C#中的一个实现,但我认为我需要一段时间来理解,因为我不知道C#语法.

那么,什么python代码生成围绕运算符的所有可能的括号分组(因此可以与实际表达式一起使用以生成所有可能性)？对于2,3和4,输出如下所示:

AllBinaryTrees(2)

1. (X(XX))
2. ((XX)x)的

AllBinaryTrees(3)

1. (((XX)x)的x)的
2. ((X(XX))×)
3. ((XX)(XX))
4. (×((XX)X))
5. (X(X(XX)))

AllBinaryTrees(4)

1. (X(X(X(XX))))
2. (X(X((XX)X)))
3. (×((XX)(XX)))
4. (×((X(XX))×))
5. (×(((XX)x)的X))
6. ((XX)(X(XX)))
7. ((XX)((XX)X))
8. ((X(XX))(XX))
9. (((XX)x)的(XX))
10. ((X(X(XX)))×)
11. ((X((XX)X))x)的
12. (((XX)(XX))×)
13. (((X(XX))×)x)的
14. ((((XX)x)的x)的x)的

更好的是代码可以执行以下操作:

AllBinaryTrees( "2 + 3/4")

输出:

1. 2+(3/4)
2. (2 + 3)/ 4

Answer 1

怎么样

def allbinarytrees(s):
    if len(s) == 1:
        yield s
    else:
        for i in range(1, len(s), 2):
            for l in allbinarytrees(s[:i]):
                for r in allbinarytrees(s[i+1:]):
                    yield '({}{}{})'.format(l, s[i], r)

样品用法:

for t in allbinarytrees('1+2-3*4/5'):
    print(t)

输出:

(1+(2-(3*(4/5))))
(1+(2-((3*4)/5)))
(1+((2-3)*(4/5)))
(1+((2-(3*4))/5))
(1+(((2-3)*4)/5))
((1+2)-(3*(4/5)))
((1+2)-((3*4)/5))
((1+(2-3))*(4/5))
(((1+2)-3)*(4/5))
((1+(2-(3*4)))/5)
((1+((2-3)*4))/5)
(((1+2)-(3*4))/5)
(((1+(2-3))*4)/5)
((((1+2)-3)*4)/5)