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

Question

计算给布尔表达式加括号的方法的数量。例如，一个布尔表达式我的意思是这样的，1^0|0|1，对于运算符，它可以是 ^、& 或 |。

做了一些参考和计算，似乎方式的数量总是（2n）！/（（n + 1）！n！），其中n是运算符的数量。如果有人知道为什么方法的数量总是（2n）！/（（n + 1）！n！），感谢分享这些见解。

这是一个示例，说明我如何表示不同的括号方式，例如，两种不同的括号方式都会导致 False。

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

提前谢谢， 林

Answer 1

加泰罗尼亚数字给出了将表达式完全括起来的方法的数量。到目前为止，理解为什么会这样的最简单方法是使用以下加泰罗尼亚数字公式：

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

当我们有一个带有n运算符的表达式时，我们可以将第一个运算符放在n以下位置：

x|x       One operator, one possible location.
 ^

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

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