Minimum number of bracket reversals needed to make an expression balanced | Set | Returns count of minimum reversals for making expr balanced . Returns - 1 if expr cannot be balanced . ; length of expression must be even to make it balanced by using reversals . ; To store number of reversals required . ; To store number of unbalanced opening brackets . ; To store number of unbalanced closing brackets . ; If current bracket is open then increment open count . ; If current bracket is close , check if it balances opening bracket . If yes then decrement count of unbalanced opening bracket else increment count of closing bracket . ; For the case : " " or when one closing and one opening bracket remains for pairing , then both need to be reversed . ; Driver Code
def countMinReversals ( expr ) : NEW_LINE INDENT length = len ( expr ) NEW_LINE if length % 2 : NEW_LINE INDENT return - 1 NEW_LINE DEDENT ans = 0 NEW_LINE open = 0 NEW_LINE close = 0 NEW_LINE for i in range ( 0 , length ) : NEW_LINE INDENT if expr [ i ] == " " : NEW_LINE INDENT open += 1 NEW_LINE DEDENT else : NEW_LINE INDENT if not open : NEW_LINE INDENT close += 1 NEW_LINE DEDENT else : NEW_LINE INDENT open -= 1 NEW_LINE DEDENT DEDENT DEDENT ans = ( close // 2 ) + ( open // 2 ) NEW_LINE close %= 2 NEW_LINE open %= 2 NEW_LINE if close > 0 : NEW_LINE INDENT ans += 2 NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT expr = " } } { { " NEW_LINE print ( countMinReversals ( expr ) ) NEW_LINE DEDENT