Minimum operation required to make a balanced sequence | Python3 implementation of the approach ; Function to return the minimum operations required ; Condition where we got only one closing bracket instead of 2 , here we have to add one more closing bracket to make the sequence balanced ; Add closing bracket that costs us one operation ; Remove the top opening bracket because we got the 1 opening and 2 continuous closing brackets ; Inserting the opening bracket to stack ; After making the sequence balanced closing is now set to 0 ; Case when there is no opening bracket the sequence starts with a closing bracket and one opening bracket is required Now we have one opening and one closing bracket ; Add opening bracket that costs us one operation ; Assigning 1 to cntClosing because we have one closing bracket ; Case where we got two continuous closing brackets need to pop one opening bracket from stack top ; Condition where stack is not empty This is the case where we have only opening brackets ( st . size ( ) * 2 ) will give us the total closing bracket needed cntClosing is the count of closing bracket that we already have ; Driver code
from queue import LifoQueue NEW_LINE def minOperations ( s , len ) : NEW_LINE INDENT operationCnt = 0 ; NEW_LINE st = LifoQueue ( ) ; NEW_LINE cntClosing = 0 ; NEW_LINE for i in range ( 0 , len ) : NEW_LINE INDENT if ( s [ i ] == ' { ' ) : NEW_LINE INDENT if ( cntClosing > 0 ) : NEW_LINE INDENT operationCnt += 1 ; NEW_LINE st . pop ( ) ; NEW_LINE DEDENT st . put ( s [ i ] ) ; NEW_LINE cntClosing = 0 ; NEW_LINE DEDENT elif ( st . empty ( ) ) : NEW_LINE INDENT st . put ( ' { ' ) ; NEW_LINE operationCnt += 1 ; NEW_LINE cntClosing = 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT cntClosing = ( cntClosing + 1 ) % 2 ; NEW_LINE if ( cntClosing == 0 ) : NEW_LINE INDENT st . pop ( ) ; NEW_LINE DEDENT DEDENT DEDENT operationCnt += st . qsize ( ) * 2 - cntClosing + 1 ; NEW_LINE return operationCnt ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT str = " { " ; NEW_LINE print ( minOperations ( str , 1 ) ) ; NEW_LINE DEDENT