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

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

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]

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

Case-1:

n=1, result=1 ()

Case-2:

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

Case-3:

n=3, result=5 ((())),(()()), (())(), ()(()),()()()

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.

`#include<iostream>`

using namespace std;

int catalan_parenthesis(int n)

`{`

`//we have n pairs of parentheses`

`//we have to find the total number of strings that are possible with n pairs of parentheses that are correctly matched`

int c[n+1];

`//c[i]=total number of strings that are possible with n correctly matched pairs of parentheses`

`//we know that for 0 pairs, only one string possible (empty string)`

`//for a single node, there can be only 1 string ie, ()`

`//for 2 nodes, there can be just 2 strings ie, ()() and (())`

`//so, we initialize the array with these values`

c[0]=1;

c[1]=1;

c[2]=2;

int i,j;

`//now, using bottom up DP, we will implement the recursive formula of catalan number to find the required value`

for(i=3;i<=n;i++)

`{`

c[i]=0;

for(j=0;j<i;j++)

`{`

c[i]+=c[j] * c[(i-1)-j];

`}`

`}`

return c[n];

`}`

int main()

`{`

int n;

cout<<"Enter the number of pairs of parentheses"<<endl;

cin>>n;

cout<<"Total number of different strings with "<<n<<" pairs of parentheses correctly matched"<<endl;

cout<<catalan_parenthesis(n);

cout<<endl;

return 0;

`}`

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.

Case-1: $ g++ catalan_parenthesis.cpp $ ./a.out Enter the number of pairs of parentheses 6 Total number of different strings with 6 pairs of parentheses correctly matched 132

**Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.**

To practice all Dynamic Programming Problems, __here is complete set of 100+ Problems and Solutions__.