{"id":27043,"date":"2018-01-05T20:50:18","date_gmt":"2018-01-05T15:20:18","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27043"},"modified":"2018-01-05T20:50:18","modified_gmt":"2018-01-05T15:20:18","slug":"c-programming-number-valid-parentheses-expressions-given-length","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-number-valid-parentheses-expressions-given-length\/","title":{"rendered":"C++ Programming – number of valid parentheses expressions of given length"},"content":{"rendered":"

Given a number n find the number of valid parentheses expressions of that length.<\/span><\/p>\n

Input: 2\r\nOutput: 1 \r\nThere is only possible valid expression of length 2, \"()\"\r\n\r\nInput: 4\r\nOutput: 2 \r\nPossible valid expression of length 4 are \"(())\" and \"()()\" \r\n\r\nInput: 6\r\nOutput: 5\r\nPossible valid expressions are ((())), ()(()), ()()(), (())() and (()())<\/pre>\n
This is mainly an application of Catalan Numbers<\/a>. Total possible valid expressions for input n is n\/2\u2019th Catalan Number if n is even and 0 if n is odd.<\/p>\n
Following is C++ implementation of the above idea.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%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)*\u2014*(n-k%2B1)%5D%20%2F%20%5Bk*(k-1)*\u2014*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\u2019th%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\u201d message=\u201dC++ Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output:<\/p>\n
Total possible expressions of length 6 is 5<\/pre>\n
Time Complexity: O(n)<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
This is mainly an application of Catalan Numbers. Total possible valid expressions for input n is n\/2\u2019th Catalan Number if n is even and 0 if n is odd.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,83515],"tags":[70047,80682,77153,80675,80672,80056,80058,80673,80060,80063,80049,80683,76433,80676,80671,80680,80670,75631,80667,80678,80068,78171],"class_list":["post-27043","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming-3","tag-c-programming","tag-check-match","tag-context-free-grammar","tag-cpp-programming","tag-define-context","tag-definition-of-grammar","tag-epsilon-sign","tag-express-inc","tag-grammar-definition","tag-grammar-definitions","tag-grammar-symbols","tag-matching-braces","tag-program-in-c","tag-program-of-c","tag-python-coding-interview-questions","tag-simple-balance","tag-stack-algorithm","tag-stack-program-in-c-using-array","tag-types-of-brackets-in-maths","tag-what-is-parenthesis","tag-what-is-the-grammar","tag-write-a-program-in-c"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27043","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27043"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27043\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27043"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27043"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27043"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}