如何为表达式打印所有可能的平衡括号？

一尘不染

如何为表达式打印所有可能的平衡括号？

algorithm

例如，使用elements a,b,c,d，有5种可能的方法将相邻元素取为单个元素，并将它们一次简化为两个元素（在下面用括号表示）：

(((ab)c)d), ((a(bc))d), ((ab)(cd)), (a((bc)d)) and (a(b(cd)))

第一个示例乘以a*b，然后乘以该乘积c，然后乘以该乘积d。第二个示例首先乘以b*c，然后乘以该乘积a，然后乘以该乘积d。

2n个元素的任何有效的括号表达式也会一定ñ (和n )与，从左至右，总有至少尽可能多的财产(为)。

我知道对于n个数字，路数是第（n-1）个加泰罗尼亚语数字。但是，如何准确地生成所有结果分组呢？

谢谢

（顺便说一句：此问题有160多种等效的表述，全部基于加泰罗尼亚语数字枚举的不同组合对象。有关这些问题的最新列表，请参阅Richard
Stanley的《加泰罗尼亚语附录》。）

阅读 231

2020-07-28

共1个答案

一尘不染

使用递归

   for each balanced expression of n-1 parentheses 
     for each pos i from 0 to m of an expression
       add '('
       for each pos  j from i + 1 to m
          add ')' if expression is balanced

您将获得的订单如下：

n=0:

n=1: ()

n=2: []() , [()]

n=3: {}[]() , {[]}() , {[]()} , {}[()] , {[()]}

在这里，我每次都会更改参数(,[,{以突出显示算法的工作原理。

2020-07-28