Check if a given string can be converted to a Balanced Bracket Sequence | Function to check if the can be balanced by replacing the ' $ ' with opening or closing brackets ; If string can never be balanced ; Declare 2 stacks to check if all ) can be balanced with ( or $ and vice - versa ; Store the count the occurence of ( , ) and $ ; Traverse the string ; Increment closed bracket count by 1 ; If there are no opening bracket to match it then return False ; Otherwise , pop the character from the stack ; If current character is an opening bracket or $ , push it to the stack ; Increment symbol count by 1 ; Increment open bracket count by 1 ; Traverse the string from end and repeat the same process ; If there are no closing brackets to match it ; Otherwise , pop character from stack ; Store the extra ( or ) which are not balanced yet ; Check if $ is available to balance the extra brackets ; Count ramaining $ after balancing extra ( and ) ; Check if each pair of $ is convertable in ( ) ; Driver Code ; Function Call
def canBeBalanced ( sequence ) : NEW_LINE INDENT if ( len ( sequence ) % 2 ) : NEW_LINE INDENT return False NEW_LINE DEDENT stack_ , stack2_ = [ ] , [ ] NEW_LINE countOpen , countClosed = 0 , 0 NEW_LINE countSymbol = 0 NEW_LINE for i in range ( len ( sequence ) ) : NEW_LINE INDENT if ( sequence [ i ] == ' ) ' ) : NEW_LINE INDENT countClosed += 1 NEW_LINE if ( len ( stack_ ) == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT else : NEW_LINE INDENT del stack_ [ - 1 ] NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if ( sequence [ i ] == ' $ ' ) : NEW_LINE INDENT countSymbol += 1 NEW_LINE DEDENT else : NEW_LINE INDENT countOpen += 1 NEW_LINE DEDENT stack_ . append ( sequence [ i ] ) NEW_LINE DEDENT DEDENT for i in range ( len ( sequence ) - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( sequence [ i ] == ' ( ' ) : NEW_LINE INDENT if ( len ( stack2_ ) == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT else : NEW_LINE INDENT del stack2_ [ - 1 ] NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT stack2_ . append ( sequence [ i ] ) NEW_LINE DEDENT DEDENT extra = abs ( countClosed - countOpen ) NEW_LINE if ( countSymbol < extra ) : NEW_LINE INDENT return False NEW_LINE DEDENT else : NEW_LINE INDENT countSymbol -= extra NEW_LINE if ( countSymbol % 2 == 0 ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S = " ( ) ( $ " NEW_LINE if ( canBeBalanced ( S ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT