Parentheses Expressions Problem – Catalan Numbers


This is a C++ Program that Solves Parentheses Expressions Problem – Catalan numbers using Dynamic Programming technique.

Problem Description

How many different strings are possible containing n pairs of parentheses which are correctly matched?

Problem Solution

This problem can be solved using catalan numbers. Catalan numbers forms a sequence of natural numbers based on a recursive formula(like fibonacci). Catalan numbers are used in various counting problems, this being one of them.

Let C[n]=nth catalan number
Number of different strings with n correctly matched pairs of parentheses = C[n]

Recurrence relation –


Time complexity of this solution is O(n^2).

Expected Input and Output


n=1, result=1           ()


n=2, result=2           ()(), (())


n=3, result=5           ((())),(()()), (())(), ()(()),()()()
Program/Source Code

Here is source code of the C++ Program to Solve Parentheses Expressions Problem – Catalan numbers. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include<iostream>
  2. using namespace std;
  4. int catalan_parenthesis(int n)
  5. {
  6.     //we have n pairs of parentheses
  7.     //we have to find the total number of strings that are possible with n pairs of parentheses that are correctly matched
  8.     int c[n+1];
  10.     //c[i]=total number of strings that are possible with n correctly matched pairs of parentheses    
  12.     //we know that for 0 pairs, only one string possible (empty string)
  13.     //for a single node, there can be only 1 string ie, ()
  14.     //for 2 nodes, there can be just 2 strings ie, ()() and (()) 
  15.     //so, we initialize the array with these values
  16.     c[0]=1;
  17.     c[1]=1;
  18.     c[2]=2;
  20.     int i,j;
  22.     //now, using bottom up DP, we will implement the recursive formula of catalan number to find the required value
  23.     for(i=3;i<=n;i++)
  24.     {
  25.         c[i]=0;
  27.         for(j=0;j<i;j++)
  28.         {
  29.             c[i]+=c[j] * c[(i-1)-j];
  30.         }
  31.     }
  33.     return c[n];
  34. }
  36. int main()
  37. {
  38.     int n;
  40.     cout<<"Enter the number of pairs of parentheses"<<endl;
  41.     cin>>n;
  43.     cout<<"Total number of different strings with "<<n<<" pairs of parentheses correctly matched"<<endl;
  44.     cout<<catalan_parenthesis(n);
  46.     cout<<endl;
  47.     return 0;
  48. }
Program Explanation

In the main function, we ask the user to input the value number of parentheses. We pass this value to the function catalan_parenthesis as parameter. This function will calculate the expected result and return it. The returned value will be displayed.

Runtime Test Cases
$ g++ catalan_parenthesis.cpp
$ ./a.out
Enter the number of pairs of parentheses
Total number of different strings with 6 pairs of parentheses correctly matched

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.


Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.