View Question
Q: nested parentheses algorithm ( Answered ,   1 Comment )
 Question
 Subject: nested parentheses algorithm Category: Computers > Algorithms Asked by: chuvak2k-ga 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 (pseudo-code) 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 non-intersecting 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: ((())) (())() ()(()) (()()) ()()()```
 Answer
 Subject: Re: nested parentheses algorithm Answered By: tox-ga on 03 Feb 2005 15:03 PST Rated:
 ```chuvak2k-ga, 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, tox-ga``` Clarification of Answer by tox-ga on 03 Feb 2005 15:05 PST ```chuvak2k-ga, Please feel free to request a clarification if this is not exactly what you are looking for. Cheers, tox-ga``` Request for Answer Clarification by chuvak2k-ga on 03 Feb 2005 15:41 PST `How can I send you the \$ ? I just rated the answer but it didnt pay you anything?` Clarification of Answer by tox-ga on 03 Feb 2005 16:56 PST ```chuvak2k-ga, Don't worry, it is all taken care of by Google Answers. For future reference, once you have posted a question, the only thing you need to concern yourself with is whether or not you wish to tip the answerer for the response. Cheers, tox-ga```
 chuvak2k-ga rated this answer: `i will have to modify the answer abit, but this is what was needed.`

 Comments
 Subject: Re: nested parentheses algorithm From: jsimon-ga 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 MathWorld--A 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?```
 Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service. If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for

 Google Home - Answers FAQ - Terms of Service - Privacy Policy