# 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]

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

Expected Input and Output

Case-1:

```
n=1, result=1           ()```

Case-2:

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

Case-3:

```
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;`
3. ` `
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];`
9. ` `
10. `    //c[i]=total number of strings that are possible with n correctly matched pairs of parentheses    `
11. ` `
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=1;`
17. `    c=1;`
18. `    c=2;`
19. ` `
20. `    int i,j;`
21. ` `
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;`
26. ` `
27. `        for(j=0;j<i;j++)`
28. `        {`
29. `            c[i]+=c[j] * c[(i-1)-j];`
30. `        }`
31. `    }`
32. ` `
33. `    return c[n];`
34. `}`
35. ` `
36. `int main()`
37. `{`
38. `    int n;`
39. ` `
40. `    cout<<"Enter the number of pairs of parentheses"<<endl;`
41. `    cin>>n;`
42. ` `
43. `    cout<<"Total number of different strings with "<<n<<" pairs of parentheses correctly matched"<<endl;`
44. `    cout<<catalan_parenthesis(n);`
45. ` `
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
```
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. 