Find the number of valid parentheses expressions of given length

Last Updated : 15 Mar, 2023

Given a number n find the number of valid parentheses expressions of that length.
Examples :

Input: 2
Output: 1 
There is only possible valid expression of length 2, "()"

Input: 4
Output: 2 
Possible valid expression of length 4 are "(())" and "()()" 

Input: 6
Output: 5
Possible valid expressions are ((())), ()(()), ()()(), (())() and (()())

This is mainly an application of Catalan Numbers. Total possible valid expressions for input n is n/2’th Catalan Number if n is even and 0 if n is odd.

Algorithm:

1. Define a function named “binomialCoeff” that takes two unsigned integers n and k as input and returns an unsigned long integer.
2. Inside the “binomialCoeff” function:
a. Define an unsigned long integer named res and initialize it to 1.
b. If k is greater than n-k, set k to n-k.
c. For i from 0 to k-1, do the following:
i. Multiply res by (n-i).
ii. Divide res by (i+1).
d. Return res.
3. Define a function named “catalan” that takes an unsigned integer n as input and returns an unsigned long integer.
4. Inside the “catalan” function:
a. Calculate the value of 2nCn by calling the “binomialCoeff” function with arguments 2*n and n.
b. Return the value of 2nCn/(n+1).
5. Define a function named “findWays” that takes an unsigned integer n as input and returns an unsigned long integer.
6. Inside the “findWays” function:
a. If n is odd, return 0.
b. Otherwise, return the nth Catalan number by calling the “catalan” function with argument n/2.
7. Define the main function.
8. Define an integer named n with the value 6.
9. Call the “findWays” function with argument 6 and print the result.

Below given is the implementation :

C++

// C++ program to find valid paranthesisations of length n
// The majority of code is taken from method 3 of
// https://www.geeksforgeeks.org/program-nth-catalan-number/
#include <bits/stdc++.h>
using namespace std;
 
// Returns value of Binomial Coefficient C(n, k)
unsigned long int binomialCoeff(unsigned int n,
                                unsigned int k)
{
    unsigned long int res = 1;
 
    // Since C(n, k) = C(n, n-k)
    if (k > n - k)
        k = n - k;
 
    // Calculate value of [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]
    for (int i = 0; i < k; ++i) {
        res *= (n - i);
        res /= (i + 1);
    }
 
    return res;
}
 
// A Binomial coefficient based function to 
// find nth catalan number in O(n) time
unsigned long int catalan(unsigned int n)
{
    // Calculate value of 2nCn
    unsigned long int c = binomialCoeff(2 * n, n);
 
    // return 2nCn/(n+1)
    return c / (n + 1);
}
 
// Function to find possible ways to put balanced
// parenthesis in an expression of length n
unsigned long int findWays(unsigned n)
{
    // If n is odd, not possible to 
    // create any valid parentheses
    if (n & 1)
        return 0;
 
    // Otherwise return n/2'th Catalan Number
    return catalan(n / 2);
}
 
// Driver program to test above functions
int main()
{
    int n = 6;
    cout << "Total possible expressions of length "
         << n << " is " << findWays(6);
    return 0;
}

Java

// Java program to find valid paranthesisations of length n
// The majority of code is taken from method 3 of
// https://www.geeksforgeeks.org/program-nth-catalan-number/
 
class GFG {
     
    // Returns value of Binomial Coefficient C(n, k)
    static long binomialCoeff(int n, int k)
    {
        long res = 1;
 
        // Since C(n, k) = C(n, n-k)
        if (k > n - k)
            k = n - k;
 
        // Calculate value of [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]
        for (int i = 0; i < k; ++i) {
            res *= (n - i);
            res /= (i + 1);
        }
 
        return res;
    }
 
    // A Binomial coefficient based function to 
    // find nth catalan number in O(n) time
    static long catalan(int n)
    {
        // Calculate value of 2nCn
        long c = binomialCoeff(2 * n, n);
 
        // return 2nCn/(n+1)
        return c / (n + 1);
    }
 
    // Function to find possible ways to put balanced
    // parenthesis in an expression of length n
    static long findWays(int n)
    {
        // If n is odd, not possible to
        // create any valid parentheses
        if ((n & 1) != 0)
            return 0;
 
        // Otherwise return n/2'th Catalan Number
        return catalan(n / 2);
    }
 
    // Driver program to test above functions
    public static void main(String[] args)
    {
        int n = 6;
        System.out.println("Total possible expressions of length " + 
                                          n + " is " + findWays(6));
    }
}
 
// This code is contributed by Smitha Dinesh Semwal

Python3

# Python3 program to find valid
# paranthesisations of length n
# The majority of code is taken
# from method 3 of
# https:#www.geeksforgeeks.org/program-nth-catalan-number/
 
# Returns value of Binomial 
# Coefficient C(n, k)
def binomialCoeff(n, k):
    res = 1;
 
    # Since C(n, k) = C(n, n-k)
    if (k > n - k):
        k = n - k;
 
    # Calculate value of [n*(n-1)*---
    # *(n-k+1)] / [k*(k-1)*---*1]
    for i in range(k): 
        res *= (n - i);
        res /= (i + 1);
 
    return int(res);
 
# A Binomial coefficient based 
# function to find nth catalan  
# number in O(n) time
def catalan(n):
     
    # Calculate value of 2nCn
    c = binomialCoeff(2 * n, n);
 
    # return 2nCn/(n+1)
    return int(c / (n + 1));
 
# Function to find possible
# ways to put balanced parenthesis
# in an expression of length n
def findWays(n):
     
    # If n is odd, not possible to 
    # create any valid parentheses
    if(n & 1):
        return 0;
 
    # Otherwise return n/2'th
    # Catalan Number
    return catalan(int(n / 2));
 
# Driver Code
n = 6;
print("Total possible expressions of length", 
                       n, "is", findWays(6));
     
# This code is contributed by mits

C#

// C# program to find valid paranthesisations
// of length n The majority of code is taken
// from method 3 of 
// https://www.geeksforgeeks.org/program-nth-catalan-number/
using System;
 
class GFG {
     
    // Returns value of Binomial
    // Coefficient C(n, k)
    static long binomialCoeff(int n, int k)
    {
        long res = 1;
 
        // Since C(n, k) = C(n, n-k)
        if (k > n - k)
            k = n - k;
 
        // Calculate value of [n*(n-1)*---*
        // (n-k+1)] / [k*(k-1)*---*1]
        for (int i = 0; i < k; ++i)
        {
            res *= (n - i);
            res /= (i + 1);
        }
 
        return res;
    }
 
    // A Binomial coefficient based function to 
    // find nth catalan number in O(n) time
    static long catalan(int n)
    {
         
        // Calculate value of 2nCn
        long c = binomialCoeff(2 * n, n);
 
        // return 2nCn/(n+1)
        return c / (n + 1);
    }
 
    // Function to find possible ways to put 
    // balanced parenthesis in an expression
    // of length n
    static long findWays(int n)
    {
        // If n is odd, not possible to
        // create any valid parentheses
        if ((n & 1) != 0)
            return 0;
 
        // Otherwise return n/2'th
        // Catalan Number
        return catalan(n / 2);
    }
 
    // Driver program to test 
    // above functions
    public static void Main()
    {
        int n = 6;
        Console.Write("Total possible expressions"
                       + "of length " + n + " is "
                                   + findWays(6));
    }
}
 
// This code is contributed by nitin mittal.

PHP

<?php
// PHP program to find valid
// paranthesisations of length n
// The majority of code is taken
// from method 3 of
// https://www.geeksforgeeks.org/program-nth-catalan-number/
 
// Returns value of Binomial 
// Coefficient C(n, k)
function binomialCoeff($n, $k)
{
    $res = 1;
 
    // Since C(n, k) = C(n, n-k)
    if ($k > $n - $k)
        $k = $n - $k;
 
    // Calculate value of [n*(n-1)*---
    // *(n-k+1)] / [k*(k-1)*---*1]
    for ($i = 0; $i < $k; ++$i) 
    {
        $res *= ($n - $i);
        $res /= ($i + 1);
    }
 
    return $res;
}
 
// A Binomial coefficient 
// based function to find 
// nth catalan number in 
// O(n) time
function catalan($n)
{
     
    // Calculate value of 2nCn
    $c = binomialCoeff(2 * $n, $n);
 
    // return 2nCn/(n+1)
    return $c / ($n + 1);
}
 
// Function to find possible
// ways to put balanced
// parenthesis in an expression 
// of length n
function findWays($n)
{
     
    // If n is odd, not possible to 
    // create any valid parentheses
    if ($n & 1)
        return 0;
 
    // Otherwise return n/2'th
    // Catalan Number
    return catalan($n / 2);
}
 
    // Driver Code
    $n = 6;
    echo "Total possible expressions of length "
                    , $n , " is " , findWays(6);
     
// This code is contributed by nitin mittal
?>

Javascript

<script>
// Javascript program to find valid
// paranthesisations of length n
// The majority of code is taken
// from method 3 of
// https://www.geeksforgeeks.org/program-nth-catalan-number/
 
// Returns value of Binomial 
// Coefficient C(n, k)
function binomialCoeff(n, k)
{
    let res = 1;
 
    // Since C(n, k) = C(n, n-k)
    if (k > n - k)
        k = n - k;
 
    // Calculate value of [n*(n-1)*---
    // *(n-k+1)] / [k*(k-1)*---*1]
    for (let i = 0; i < k; ++i) 
    {
        res *= (n - i);
        res /= (i + 1);
    }
 
    return res;
}
 
// A Binomial coefficient 
// based function to find 
// nth catalan number in 
// O(n) time
function catalan(n)
{
     
    // Calculate value of 2nCn
    let c = binomialCoeff(2 * n, n);
 
    // return 2nCn/(n+1)
    return c / (n + 1);
}
 
// Function to find possible
// ways to put balanced
// parenthesis in an expression 
// of length n
function findWays(n)
{
     
    // If n is odd, not possible to 
    // create any valid parentheses
    if (n & 1)
        return 0;
 
    // Otherwise return n/2'th
    // Catalan Number
    return catalan(n / 2);
}
 
    // Driver Code
    let n = 6;
    document.write("Total possible expressions of length " + 
                   n + " is " + findWays(6));
     
// This code is contributed by _saurabh_jaiswal
</script>

Output:

Total possible expressions of length 6 is 5

Time Complexity: O(n)

Auxiliary Space: O(1)

Sachin

Improve

Minimum number of bracket reversals needed to make an expression balanced

Construct Binary Tree from String with bracket representation

Find the number of valid parentheses expressions of given length

C++

Java

Python3

C#

PHP

Javascript

Similar Reads

Please Login to comment...

What kind of Experience do you want to share?