如何打印所有可能的平衡括号中的前pression？ [英] How to print all possible balanced parentheses for an expression?

问题描述

例如，包含元素 A，B，C，D ，有5个可能的方式把相邻的元素，减少成一个单一的元素，其中正好有两个元素必须在同一时间内组合（以括号psented再$ P $下同）：

For example, with elements a,b,c,d, there are 5 possible ways to take neighboring elements and reduce them into a single element, where exactly two elements must be combined at a time (below represented by parentheses):

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

第一个例子乘 A * B ，然后乘以该产品由 C ，然后乘以该产品由 D 。第二个例子是第一个乘 B * C ，然后乘以该产品 A ，然后乘以该产品由 D 。

The first example multiplies a*b, then multiplies that product by c, then multiplies that product by d. The second example first multiplies b*c, then multiplies that product by a, then multiplies that product by d.

2n个元素的任何有效的括号内的EX pression必然有n个（和n ）的属性，从左到右阅读，总有至少尽可能多的（为）。

Any valid parenthesized expression of 2n elements will necessarily have n ( and n ) with the property that, reading from left to right, there are always at least as many ( as ).

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

I know that for n numbers, the number of ways is the (n-1)th Catalan number. But how does one accurately generate all the resulting groupings?

感谢

（顺便说一句：有超过160相当于这个问题的配方，全部基于由加泰罗尼亚数字列举不同的组合对象有关这些最先进的最新列表，请参阅的施瑞德的加泰罗尼亚附录。）

(As an aside: There are over 160 equivalent formulations of this problem, all based on different combinatorial objects enumerated by the Catalan Numbers. For the most up to date list of these, see Richard Stanley's Catalan Addendum.)

推荐答案

使用递归

   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

的顺序，你会得到如下：

The order you will get is the following:

n=0: 

n=1: ()

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

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

在这里，我每一次改变括号（[{突出算法如何工作的。

Here I'm changing the parens each time (,[,{ to highlight how the algorithm works.

这篇关于如何打印所有可能的平衡括号中的前pression？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！