{"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 &#8211; number of valid parentheses expressions of given length"},"content":{"rendered":"<p>Given a number n find the number of valid parentheses expressions of that length.<span id=\"more-142556\"><\/span><\/p>\n<pre>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<p>This is mainly an application of <a href=\"http:\/\/www.geeksforgeeks.org\/program-nth-catalan-number\/\" target=\"_blank\" rel=\"noopener noreferrer\">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<p>Following is C++ implementation of the above idea.<\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">C++ Program<\/span> <\/div> <pre class=\"language-cpp code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-cpp code-embed-code\">\/\/ C++ program to find valid paranthesisations of length n<br\/>\/\/ The majority of code is taken from method 3 of <br\/>\/\/ http:\/\/www.geeksforgeeks.org\/program-nth-catalan-number\/<br\/>#include&lt;iostream&gt;<br\/>using namespace std;<br\/> <br\/>\/\/ Returns value of Binomial Coefficient C(n, k)<br\/>unsigned long int binomialCoeff(unsigned int n, unsigned int k)<br\/>{<br\/>    unsigned long int res = 1;<br\/> <br\/>    \/\/ Since C(n, k) = C(n, n-k)<br\/>    if (k &gt; n - k)<br\/>        k = n - k;<br\/> <br\/>    \/\/ Calculate value of [n*(n-1)*---*(n-k+1)] \/ [k*(k-1)*---*1]<br\/>    for (int i = 0; i &lt; k; ++i)<br\/>    {<br\/>        res *= (n - i);<br\/>        res \/= (i + 1);<br\/>    }<br\/> <br\/>    return res;<br\/>}<br\/> <br\/>\/\/ A Binomial coefficient based function to find nth catalan<br\/>\/\/ number in O(n) time<br\/>unsigned long int catalan(unsigned int n)<br\/>{<br\/>    \/\/ Calculate value of 2nCn<br\/>    unsigned long int c = binomialCoeff(2*n, n);<br\/> <br\/>    \/\/ return 2nCn\/(n+1)<br\/>    return c\/(n+1);<br\/>}<br\/> <br\/>\/\/ Function to find possible ways to put balanced parenthesis<br\/>\/\/ in an expression of length n<br\/>unsigned long int findWays(unsigned n)<br\/>{<br\/>    \/\/ If n is odd, not possible to create any valid parentheses<br\/>    if (n &amp; 1) return 0;<br\/> <br\/>   \/\/ Otherwise return n\/2&#039;th Catalan Numer<br\/>   return catalan(n\/2);<br\/>}<br\/> <br\/>\/\/ Driver program to test above functions<br\/>int main()<br\/>{<br\/>    int n = 6;<br\/>    cout &lt;&lt; &quot;Total possible expressions of length &quot;<br\/>         &lt;&lt; n &lt;&lt; &quot; is &quot; &lt;&lt; findWays(6);<br\/>    return 0;<br\/>}<\/code><\/pre> <\/div>\n<p>Output:<\/p>\n<pre>Total possible expressions of length 6 is 5<\/pre>\n<p>Time Complexity: O(n)<\/p>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>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}]}}