text: Minimum number of bracket reversals needed to make an expression balanced | C ++ program to find minimum number of reversals required to balance an expression ; 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 . ; After this loop , stack contains unbalanced part of expression , i . e . , expression of the form " } } . . } { { . . { " ; Length of the reduced expression red_len = ( m + n ) ; count opening brackets at the end of stack ; return ceil ( m / 2 ) + ceil ( n / 2 ) which is actually equal to ( m + n ) / 2 + n % 2 when m + n is even . ; Driver program to test above function
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int countMinReversals ( string expr ) { int len = expr . length ( ) ; if ( len % 2 ) return -1 ; stack < char > s ; for ( int i = 0 ; i < len ; i ++ ) { if ( expr [ i ] == ' } ' && ! s . empty ( ) ) { if ( s . top ( ) == ' { ' ) s . pop ( ) ; else s . push ( expr [ i ] ) ; } else s . push ( expr [ i ] ) ; } int red_len = s . size ( ) ; int n = 0 ; while ( ! s . empty ( ) && s . top ( ) == ' { ' ) { s . pop ( ) ; n ++ ; } return ( red_len / 2 + n % 2 ) ; } int main ( ) { string expr = " } } { { " ; cout << countMinReversals ( expr ) ; return 0 ; }