什么蟒蛇code生成所有可能的分组（树）的双目操作 [英] What python code generates all possible groupings (trees) for binary operators

问题描述

在几个SO问题在 mathworld ，加泰罗尼亚数字序列解释，更抽象恰好对应于可以为运营商的任何给定的数量来生成分组括号的数量。但是我还没有找到一个算法来生成所有这些分组。

此二进制包围算法对应于塔马利格并可以在许多不同的说明方式。最明显的实际用途，该算法是由围绕二元运算每一种可能的包围和数字他们经营上产生所有可能的前pressions。这可以用于对二叉树穷尽测试各种类型的操作

网络搜索并显示的在C＃的一种实现方式，但我认为它会带我一段时间来理解，因为我不知道C＃语法。

那么，是什么蟒蛇code产生的括号中的运营商所有可能的分组（其因此可以与实际EX pression用于生成做好一切准备）？输出将如下所示的2，3，4：

AllBinaryTrees（2）

1. （X（XX））
2. （（XX）x）

AllBinaryTrees（3）

1. （（（XX）x）x）
2. （（X（XX））×）
3. （（XX）（XX））
4. （X（（XX）X））
5. （X（X（XX）））

AllBinaryTrees（4）

1. （X（X（X（XX））））
2. （X（X（（XX）X）））
3. （X（（XX）（XX）））
4. （X（（X（XX））×））
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）））×）
11. （（X（（XX）x））×）
12. （（（XX）（XX））×）
13. （（（X（XX））x）x）
14. （（（（XX）X）x）x）

更妙的是code这做类似如下：

AllBinaryTrees（2 + 3/4）

输出：

1. 2 +（3/4）
2. （2 + 3）/ 4

解决方案

如何

 高清allbinarytrees（S）：
    如果len（S）== 1：
        产量小号
    其他：
        对于i在范围（1，LEN（S），2）：
            对于L的allbinarytrees（S [：I]）：
                当r在allbinarytrees（S [I + 1：]）：
                    收率'（{} {} {}）。格式（L，S [I]，r）的
 

使用范例：

 为T在allbinarytrees（1 + 2-3 * 8.2 / 10）：
    打印（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）
 

As explained in several SO questions, and more abstractly at mathworld, the sequence of Catalan numbers happens to correspond to the number of parenthetical groupings that can be generated for any given number of operators. But I haven't found an algorithm to generate all these groupings.

This binary bracketing algorithm corresponds to the Tamari Lattice and can be described in a number of different ways. The most obvious practical use for this algorithm is to generate all possible expressions by every possible bracketing around binary operators and the numbers they operate on. This can be used to exhaustively test various types of operations on binary trees.

Web searching did reveal one implementation in C# but I think it would take me a while to understand as I don't know C# syntax.

So, what python code generates all the possible groupings of parenthesis around operators (which can thus be used with an actual expression to generate all the possibilities)? Output would look as follows for 2, 3, and 4:

AllBinaryTrees(2)

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

AllBinaryTrees(3)

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

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

Even better would be code which did something like the following:

AllBinaryTrees("2+3/4")

output:

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

解决方案

How about

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)

Sample usage:

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)

这篇关于什么蟒蛇code生成所有可能的分组（树）的双目操作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！