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

Case-1:

 
n=1, result=1           ()

Case-2:

Subscribe Now: Dynamic Programming Newsletter | Important Subjects Newsletters

 
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.

```
#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;
```
```
}
```

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.

If you find any mistake above, kindly email to [email protected]

« Prev - Binary Trees with N Keys Problem – Dynamic Programming Solutions

» Next - Newspaper Headline Problem using Dynamic Programming

Related Posts:

Recommended Articles: