Balanced expressions such that given positions have opening brackets | Python 3 code to find number of ways of arranging bracket with proper expressions ; function to calculate the number of proper bracket sequence ; hash array to mark the positions of opening brackets ; dp 2d array ; mark positions in hash array ; first position marked as 1 ; iterate and formulate the recurrences ; if position has a opening bracket ; return answer ; Driver Code ; positions where opening braces will be placed
N = 1000 NEW_LINE def arrangeBraces ( n , pos , k ) : NEW_LINE INDENT h = [ False for i in range ( N ) ] NEW_LINE dp = [ [ 0 for i in range ( N ) ] for i in range ( N ) ] NEW_LINE for i in range ( k ) : NEW_LINE INDENT h [ pos [ i ] ] = 1 NEW_LINE DEDENT dp [ 0 ] [ 0 ] = 1 NEW_LINE for i in range ( 1 , 2 * n + 1 ) : NEW_LINE INDENT for j in range ( 2 * n + 1 ) : NEW_LINE INDENT if ( h [ i ] ) : NEW_LINE INDENT if ( j != 0 ) : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = 0 NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if ( j != 0 ) : NEW_LINE INDENT dp [ i ] [ j ] = ( dp [ i - 1 ] [ j - 1 ] + dp [ i - 1 ] [ j + 1 ] ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j + 1 ] NEW_LINE DEDENT DEDENT DEDENT DEDENT return dp [ 2 * n ] [ 0 ] NEW_LINE DEDENT n = 3 NEW_LINE pos = [ 2 , ] ; NEW_LINE k = len ( pos ) NEW_LINE print ( arrangeBraces ( n , pos , k ) ) NEW_LINE