Given a number n find the number of valid parentheses expressions of that length.
Input: 2 Output: 1 There is only possible valid expression of length 2, "()" Input: 4 Output: 2 Possible valid expression of length 4 are "(())" and "()()" Input: 6 Output: 5 Possible valid expressions are ((())), ()(()), ()()(), (())() and (()())
This is mainly an application of Catalan Numbers. Total possible valid expressions for input n is n/2’th Catalan Number if n is even and 0 if n is odd.
Following is C++ implementation of the above idea.
[pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20program%20to%20find%20valid%20paranthesisations%20of%20length%20n%0A%2F%2F%20The%20majority%20of%20code%20is%20taken%20from%20method%203%20of%20%0A%2F%2F%20http%3A%2F%2Fwww.geeksforgeeks.org%2Fprogram-nth-catalan-number%2F%0A%23include%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Returns%20value%20of%20Binomial%20Coefficient%20C(n%2C%20k)%0Aunsigned%20long%20int%20binomialCoeff(unsigned%20int%20n%2C%20unsigned%20int%20k)%0A%7B%0A%20%20%20%20unsigned%20long%20int%20res%20%3D%201%3B%0A%20%0A%20%20%20%20%2F%2F%20Since%20C(n%2C%20k)%20%3D%20C(n%2C%20n-k)%0A%20%20%20%20if%20(k%20%3E%20n%20-%20k)%0A%20%20%20%20%20%20%20%20k%20%3D%20n%20-%20k%3B%0A%20%0A%20%20%20%20%2F%2F%20Calculate%20value%20of%20%5Bn*(n-1)*—*(n-k%2B1)%5D%20%2F%20%5Bk*(k-1)*—*1%5D%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20k%3B%20%2B%2Bi)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20res%20*%3D%20(n%20-%20i)%3B%0A%20%20%20%20%20%20%20%20res%20%2F%3D%20(i%20%2B%201)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20res%3B%0A%7D%0A%20%0A%2F%2F%20A%20Binomial%20coefficient%20based%20function%20to%20find%20nth%20catalan%0A%2F%2F%20number%20in%20O(n)%20time%0Aunsigned%20long%20int%20catalan(unsigned%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Calculate%20value%20of%202nCn%0A%20%20%20%20unsigned%20long%20int%20c%20%3D%20binomialCoeff(2*n%2C%20n)%3B%0A%20%0A%20%20%20%20%2F%2F%20return%202nCn%2F(n%2B1)%0A%20%20%20%20return%20c%2F(n%2B1)%3B%0A%7D%0A%20%0A%2F%2F%20Function%20to%20find%20possible%20ways%20to%20put%20balanced%20parenthesis%0A%2F%2F%20in%20an%20expression%20of%20length%20n%0Aunsigned%20long%20int%20findWays(unsigned%20n)%0A%7B%0A%20%20%20%20%2F%2F%20If%20n%20is%20odd%2C%20not%20possible%20to%20create%20any%20valid%20parentheses%0A%20%20%20%20if%20(n%20%26%201)%20return%200%3B%0A%20%0A%20%20%20%2F%2F%20Otherwise%20return%20n%2F2’th%20Catalan%20Numer%0A%20%20%20return%20catalan(n%2F2)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20int%20n%20%3D%206%3B%0A%20%20%20%20cout%20%3C%3C%20%22Total%20possible%20expressions%20of%20length%20%22%0A%20%20%20%20%20%20%20%20%20%3C%3C%20n%20%3C%3C%20%22%20is%20%22%20%3C%3C%20findWays(6)%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C++ Program” highlight=”” provider=”manual”/]Output:
Total possible expressions of length 6 is 5
Time Complexity: O(n)
[ad type=”banner”]