

Subject:
nested parentheses algorithm
Category: Computers > Algorithms Asked by: chuvak2kga List Price: $45.00 
Posted:
03 Feb 2005 05:00 PST
Expires: 05 Mar 2005 05:00 PST Question ID: 468032 
Consider sequences of properly nested parentheses. By properly nested I mean that every left parenthesis has a matching right parenthesis and that at every stage the number of left parantheses seen so far is greater than or equal to the number of right parentheses. Write an algorithm (pseudocode) to determine the number of different possible sequences of properly nested parentheses with N pairs of parentheses. Another way of thinking of this is as follows. Consider an n+2 sides convex polygon. In how many ways can it be cut into N triangles by drawing nonintersecting diagonals? The first few of these numbers are: 1,2,5,14,42,132 Here are the 5 possible sequences of properly nested parentheses for 3 pairs: ((())) (())() ()(()) (()()) ()()() 

Subject:
Re: nested parentheses algorithm
Answered By: toxga on 03 Feb 2005 15:03 PST Rated: 
chuvak2kga, The algorithm for determining this value is as follows: function NPPermutations (int numP) { int permutations = 1 for (int i=numP+2;i<=2*numP;i++) { permutations = permutations * i } for (int i=2;i<=numP;i++) { permutations = permutations / i } return permutations } (Source: http://planetmath.org/encyclopedia/CatalanNumbers.html) Cheers, toxga  
 
 

chuvak2kga
rated this answer:
i will have to modify the answer abit, but this is what was needed. 

Subject:
Re: nested parentheses algorithm
From: jsimonga on 03 Feb 2005 06:51 PST 
I think what you are looking for are the Catalan numbers. C_n = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!) Eric W. Weisstein et al. "Catalan Number." From MathWorldA Wolfram Web Resource. http://mathworld.wolfram.com/CatalanNumber.html Here is the Sloan link to the sequence http://www.research.att.com/projects/OEIS?Anum=A000108 Is this helps? 
If you feel that you have found inappropriate content, please let us know by emailing us at answerssupport@google.com with the question ID listed above. Thank you. 
Search Google Answers for 
Google Home  Answers FAQ  Terms of Service  Privacy Policy 