algorithm - 计算给 bool 表达式加括号的方法

Question

计算将 bool 表达式括起来的方式的数量。比如一个 bool 表达式，我的意思是这样的，1^0|0|1，对于运算符，它可以是^，&或者|。

做了一些引用和计算，似乎方法的数量总是(2n)!/((n+1)!n!)，其中n是运算符的数量。如果有人知道为什么方法数总是 (2n)!/((n+1)!n!)，感谢分享见解。

下面是一个例子，说明我如何理解不同的括号方式，例如，两种不同的括号方式都会导致 False。

1^((0|0)|1) 1^(0|(0|1))

提前致谢，林

Answer 1

Catalan numbers 给出了完全括起表达式的方法数.到目前为止，理解为什么会出现这种情况的最简单方法是对加泰罗尼亚数字使用以下公式:

当有 0 个运算符时，只有一种方法可以完全括起表达式:(x)。

当我们有一个包含 n 个运算符的表达式时，我们可以将第一个运算符放在 n 个地方:

x|x       One operator, one possible location.
 ^

x|x|x     Two operators, two possible locations.
 ^ ^

当我们“放置”一个运算符时，我们只需将左侧括号的可能方法数乘以右侧括号的方法数。我们对每个可能的位置都这样做，并对这些可能性求和。