Open In App

Find the number of valid parentheses expressions of given length

Last Updated : 15 Mar, 2023
Summarize
Comments
Improve
Suggest changes
Like Article
Like
Save
Share
Report
News Follow

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
#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
 
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
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
 
// 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
 
// 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)

 



Previous Article
Next Article

Similar Reads

Count pairs of parentheses sequences such that parentheses are balanced
Given N bracket sequences, the task is to find the number of pairs of bracket sequences by joining which can be obtained a balanced bracket sequence as a whole. A bracket parentheses sequence can only be a part of a single pair. Examples: Input: { ")())", ")", "((", "((", "(", ")", ")"} Output: 2 Bracket sequence {1, 3} and {5, 6} Input: {"()", "((
9 min read
Find a valid parenthesis sequence of length K from a given valid parenthesis sequence
Given a string S of valid parentheses sequence of length N and an even integer K, the task is to find the valid parentheses sequence of length K which is also a subsequence of the given string. Note: There can be more than one valid sequence, print any of them. Examples: Input: S = "()()()", K = 4Output: ()()Explanation:The string "()()" is a subse
7 min read
Minimum number of Parentheses to be added to make it valid
Given a string S of parentheses '(' or ')' where, [Tex]0\leq len(S)\leq 1000 [/Tex]. The task is to find a minimum number of parentheses '(' or ')' (at any positions) we must add to make the resulting parentheses string is valid. Examples: Input: str = "())" Output: 1 One '(' is required at beginning. Input: str = "(((" Output: 3 Three ')' is requi
9 min read
Longest Valid Parentheses Substring
Given a string str consisting of opening and closing parenthesis '(' and ')'. Find the length of the longest valid parenthesis substring. Examples: Input: ((()Output : 2Explanation : Longest Valid Parentheses Substring is (). Input: )()())Output : 4Explanation: Longest Valid Parentheses Substring is ()() . Table of Content [Expected Approach - 1] U
15+ min read
Valid Parentheses in an Expression
Given an expression string s, write a program to examine whether the pairs and the orders of "{", "}", "(", ")", "[", "]" are correct in the given expression. Example: Input: s = "[()]{}{[()()]()}" Output: trueExplanation: All the brackets are well-formed Input: s = "[(])" Output: falseExplanation: 1 and 4 brackets are not balanced because there is
9 min read
Check if the given Binary Expressions are valid
Given n expressions of the type x = y and x != y where 1 ? x, y ? n, the task is to check whether the integers from 1 to n can be assigned to x and y such that all the equations are satisfied. Examples: Input: x[] = {1, 2, 3}, op[] = {"=", "=", "!="}, y[] = {2, 3, 1} Output: Invalid If 1 = 2 and 2 = 3 then 3 must be equal to 1. Input: x[] = {1, 2},
10 min read
Length of longest balanced parentheses prefix
Given a string of open bracket '(' and closed bracket ')'. The task is to find the length of longest balanced prefix. Examples: Input : S = "((()())())((" Output : 10From index 0 to index 9, they are forming a balanced parentheses prefix.Input : S = "()(())((()"Output : 6 The idea is take value of open bracket '(' as 1 and value of close bracket ')
9 min read
Balance the parentheses for the given number N
Given a number N, the task is to insert the minimum number of opening and closing parenthesis into the number N such that the resultant string is balanced and every digit D is exactly in D pairs of matching parenthesis. Examples: Input: N = 312 Output: (((3))1(2)) Explanation: Every digit in the number is within exactly in D parenthesis. There are
3 min read
Find the length of the longest valid number chain in an Array
Given an array A[] of N numbers, the task is to find the length of the longest valid number that can be formed by connecting one or more numbers from the array such that, while connecting two numbers the last digit of the previous number is the same as the first digit of the next number. Examples: Input: A = [100, 234, 416, 654, 412, 298, 820, 177]
10 min read
Check if the Depth of Parentheses is correct in the given String
Given a string S consisting of opening parentheses, closing parentheses and integers, the task is to print Yes if, in this string, the integers correctly indicates its depth. Depth refers to the number of nested sets of parentheses surrounding that integer. Print No otherwise.Examples: Input: S = "((2)((3)))" Output: Yes Explanation: No of Opening
7 min read
Calculate score of parentheses from a given string
Given string str of length N, consisting of pairs of balanced parentheses, the task is to calculate the score of the given string based on the given rules: “()” has a score of 1.“a b” has a score of a + b, where a and b are individual pairs of balanced parentheses.“(a)” has a score twice of a i.e., the score is 2 * score of a. Examples: Input: str
6 min read
Arrange given numbers in a mathematical expression using operators [+, -, *, /] and parentheses to get value 24
Given an array arr[] consisting of 4 integers each between [1-9], the task is to check whether it is possible to get the number 24 by placing the operators +, -, /, and * between the numbers or grouping them using parenthesis. If it is possible then print "Possible", Otherwise print "Not Possible". Examples: Input: arr[] = {3, 6, 8, 2}Output: Possi
11 min read
Number of balanced parentheses substrings
Given a balanced parentheses string which consists of '(' and ')'. The task is to find the number of balanced parentheses substrings in the given string Examples : Input : str = "()()()" Output : 6 (), (), (), ()(), ()(), ()()()Input : str = "(())()" Output : 4 (), (()), (), (())() Approach : Let us assume that whenever we encounter with opening br
6 min read
Number of ways to insert two pairs of parentheses into a string of N characters
Given a string str of length N, the task is to find the number of ways to insert only 2 pairs of parentheses into the given string such that the resultant string is still valid.Examples: Input: str = "ab" Output: 6 ((a))b, ((a)b), ((ab)), (a)(b), (a(b)), a((b)) which are a total of 6 ways.Input: str = "aab" Output: 20 Approach: it can be observed t
3 min read
Number of levels having balanced parentheses in a Binary Tree
Given a Binary Tree consisting only '(' and ')' a level is considered to be balanced if the nodes of the level having parenthesis are balanced from left to right. The task is to count the total number of balanced levels in a binary tree. Examples: Input: ( / \ ( ) / \ \ ( ) ( / \ \ \ ( ( ) ) Output: 2Explanation:In Level 2 and 4, the parenthesis ar
10 min read
Minimize length by removing subsequences forming valid parenthesis from a given string
Given a string S consisting of '(', ')', '[' and ']', the task is to find the minimum count of remaining characters in the string by removing subsequences of the valid parenthesis. Examples: Input: S = "[]])([" Output: 4 Explanation: Removing the subsequence { str[0], str[1] } modifies S to "])([". Therefore, the required output is 4. Input: S = "(
9 min read
Minimize length of a given string by removing subsequences forming valid parenthesis
Given a string S consisting of characters '(', ')', '[', ']', '{', '}', the task is to remove all balanced bracket subsequences from the string and print the remaining characters. Examples: Input: S = "((){()({})"Output: "({"Explanation: S[1] and S[2] forms a regular bracket sequence. Therefore, remove them from the string. S = "({()({})"S[2] and S
11 min read
Pairs involved in Balanced Parentheses
Given a string of brackets, the task is to find the number of pairs of brackets involved in a balanced sequence in a given range. Examples : Input : ((())(() Range : 1 5 Range : 3 8 Output : 2 2 Explanation : In range 1 to 5 ((()), there are the two pairs. In range 3 to 8 ()) ((), there are the two pairs. Input : )()())) Range : 1 2 Range : 4 7 Out
14 min read
Cost to Balance the parentheses
Parentheses are said to be balanced when every opening brace has a closing brace like "()()" or "(())" or "(()())" etc. Incorrect balancing includes ")(" or "))((" etc. The task here is to correct the sequence of parentheses in such a way that it is done in minimum cost. And shifting of parentheses by over one parentheses costs 1. If the parenthese
7 min read
Check for balanced parentheses in an expression | O(1) space
Given a string of length n having parentheses in it, your task is to find whether given string has balanced parentheses or not. Please note there is constraint on space i.e. we are allowed to use only O(1) extra space. Also See : Check for balanced parentheses Examples: Input : (())[] Output : Yes Input : ))(({}{ Output : No If k = 1, then we will
15+ min read
Insert minimum parentheses to make string balanced
Given a string of digits S. The task is to insert a minimum number of opening and closing parentheses into the string S such that the resulting string is balanced and each digit d must be inside d pairs of matching parentheses. Examples: Input: S = 221 Output: ((22)1) Explanation: The string ((2))((2))(1) is not valid solutions because it is not of
6 min read
Reduce string by removing outermost parentheses from each primitive substring
Given a string S of valid parentheses "(" and ")", the task is to print the string obtained by removing the outermost parentheses of every primitive substring from S. A valid parentheses substring S is primitive if it is non-empty, and cannot be split into two or more non-empty substrings which are also a valid parentheses. Examples: Input: S = "((
9 min read
Print the string obtained after removal of outermost parentheses
Given a valid parenthesis string str consisting of lowercase alphabets, opening, and closing brackets, the task is to find the string by removing the outermost enclosing brackets such that the string remains a valid parenthesis string. Examples: Input: S = "(((a)(bcd)(e)))"Output: (a)(bcd)(e)Explanation: The outermost enclosing brackets are: { S[0]
8 min read
Calculate score of a string consisting of balanced parentheses
Given a string str consisting of pairs of balanced parentheses, the task is to calculate the score of the given string based on the following rules: "()" has a score of 1."x y" has a score of x + y where x and y are individual pairs of balanced parentheses."(x)" has a score twice of x (i.e), 2 * score of x. Examples: Input: str = "()()"Output: 2Exp
7 min read
Modify a numeric string to a balanced parentheses by replacements
Given a numeric string S made up of characters '1', '2' and '3' only, the task is to replace characters with either an open bracket ( '(' ) or a closed bracket ( ')' ) such that the newly formed string becomes a balanced bracket sequence. Note: All occurrences of a character must be replaced by the same parentheses. Examples: Input: S = "1123"Outpu
10 min read
Remove Invalid Parentheses
An expression will be given which can contain open and close parentheses and optionally some characters, No other operator will be there in string. We need to remove minimum number of parentheses to make the input string valid. If more than one valid output are possible removing same number of parentheses then print all such output. Examples: Input
9 min read
Print all combinations of balanced parentheses
Given a number n, the task is to generate all possible n pairs of balanced parentheses. Examples: Input: n=1Output: {}Explanation: This the only sequence of balanced parenthesis formed using 1 pair of balanced parenthesis. Input : n=2Output: {}{} {{}}Explanation: This the only two sequences of balanced parenthesis formed using 2 pair of balanced pa
12 min read
Print all the possible arithmetic expressions for a given number
Given an integer N, the task is to print all the possible arithmetic expressions using all numbers from 1 to N and with binary operator +, –, * and /.Examples: Input: n = 2 Output: 1+2, 1-2, 1/2, 1*2Input: n = 3 Output: 1+2+3, 1+2-3, 1+2/3, 1+2*3, 1-2+3, 1-2-3, 1-2/3, 1-2*3 1/2+3, 1/2-3, 1/2/3, 1/2*3, 1*2+3, 1*2-3, 1*2/3, 1*2*3 Approach: We will cr
5 min read
Extracting PAN Number from GST Number Using Regular Expressions
Given a string str in the form of a GST Number, the task is to extract the PAN Number from the given string. General Format of a GST Number: "22AAAAA0000A1Z5" 22: State CodeAAAAA0000A: Permanent Account Number (PAN)1: Entity Number of the same PANZ: Alphabet Z by default5: Checksum digit Examples: Input: str="23BOSPC9911R2Z5Output: BOSPC9911R Input
4 min read
Reduce a string to a valid email address of minimum length by replacing specified substrings
Given string S representing an email address of length N, the task is to find the minimum possible length of the string by replacing "dot" with '.' and "at" with '@' such that the string represents a valid email address. An email address can have only one '@' and can have possibly zero or multiple dots ('.') such that it can not have '@' or '.' at
7 min read
Practice Tags :
three90RightbarBannerImg