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).
n=1, result=1 ()
n=2, result=2 ()(), (())
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.
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
//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
//now, using bottom up DP, we will implement the recursive formula of catalan number to find the required value
c[i]+=c[j] * c[(i-1)-j];
cout<<"Enter the number of pairs of parentheses"<<endl;
cout<<"Total number of different strings with "<<n<<" pairs of parentheses correctly matched"<<endl;
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.