7

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

这种二进制包围算法对应于Tamari 格，可以用多种不同的方式来描述。该算法最明显的实际用途是通过围绕二元运算符及其运算的数字的每个可能的括号来生成所有可能的表达式。这可以用来详尽地测试二叉树上的各种类型的操作。

网络搜索确实揭示了 C# 中的一个实现，但我认为我需要一段时间才能理解，因为我不知道 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)

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

AllBinaryTrees("2+3/4")

输出：

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

2 回答 2

7

怎么样

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)
于 2013-06-21T18:57:02.057 回答
3

接受的答案仅适用于单个数字，我将其保留为接受的答案，因为它以易于阅读的方式说明了这个概念。这个修改后的、看起来更混乱的版本适用于所有数字，而不仅仅是一位数字：

def allbinarytrees(s):
    if s.isdigit():
        yield s
    else:
        i = 0
        while i < len(s)-1:
            while i < len(s) and s[i].isdigit():
                i += 1
            if i < len(s) - 1:
                for left in allbinarytrees(s[:i]):
                    for right in allbinarytrees(s[i+1:]):
                        yield '({}{}{})'.format(left, s[i], right)
            i += 1

示例用法：

j=0
for t in allbinarytrees('11+22*3/4456'):
    j += 1
    print j, (t[1:-1])

输出：

1 11+(22*(3/4456))
2 11+((22*3)/4456)
3 (11+22)*(3/4456)
4 (11+(22*3))/4456
5 ((11+22)*3)/4456
于 2013-06-21T21:03:32.300 回答