Google Answers Logo
View Question
Q: nested parentheses algorithm ( Answered 4 out of 5 stars,   1 Comment )
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:

Here are the 5 possible sequences of properly nested parentheses for 3 pairs:

((()))   (())()  ()(())  (()())  ()()()
Subject: Re: nested parentheses algorithm
Answered By: tox-ga on 03 Feb 2005 15:03 PST
Rated:4 out of 5 stars

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



Clarification of Answer by tox-ga on 03 Feb 2005 15:05 PST

Please feel free to request a clarification if this is not exactly
what you are looking for.


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

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.

chuvak2k-ga rated this answer:4 out of 5 stars
i will have to modify the answer abit, but this is what was needed.

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.

Here is the Sloan link to the sequence

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 with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

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