什么Python代码为二元运算符生成所有可能的分组（树）

正如几个 SO 问题中所解释的，更抽象的是数学世界 http://mathworld.wolfram.com/BinaryBracketing.html，加泰罗尼亚数字的序列恰好对应于可以为任何给定数量的运算符生成的括号分组的数量。但我还没有找到一种算法来生成所有这些分组。

该二元包围算法对应于酱油格子 http://en.wikipedia.org/wiki/Tamari_lattice并且可以用多种不同的方式来描述。该算法最明显的实际用途是通过二元运算符及其所操作的数字的每个可能的括号来生成所有可能的表达式。这可用于详尽地测试二叉树上的各种类型的操作。

网络搜索确实揭示了C# 中的一种实现 http://blogs.msdn.com/b/ericlippert/archive/2010/04/19/every-binary-tree-there-is.aspx但我认为我需要一段时间才能理解，因为我不知道 C# 语法。

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

所有二叉树(2)

1. (x(xx))
2. ((xx)x)

所有二叉树(3)

1. (((xx)x)x)
2. ((x(xx))x)
3. ((xx)(xx))
4. (x((xx)x))
5. (x(x(xx)))

所有二叉树(4)

1. (x(x(x(xx))))
2. (x(x((xx)x)))
3. (x((xx)(xx)))
4. (x((x(xx))x))
5. (x(((xx)x)x))
6. ((xx)(x(xx)))
7. ((xx)((xx)x))
8. ((x(xx))(xx))
9. (((xx)x)(xx))
10. ((x(x(xx)))x)
11. ((x((xx)x))x)
12. (((xx)(xx))x)
13. (((x(xx))x)x)
14. ((((xx)x)x)x)

更好的是执行如下操作的代码：

所有二叉树("2+3/4")

output:

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

怎么样

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)

Output:

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