# Minimum number of bracket reversals needed to make an expression balanced in C++

## Minimum number of swaps for bracket balancing

Today we will be learning How to find the Minimum number of swaps for bracket balancing.

Lets understand this with the help of example :-

• Input:- “}{{}}{{{“
• Output:- 2

For example, if input string is  “}{{}}{{{” then you need to reverse the bracket at 0th position to “{” and thr bracket at 5th position to “}” and bracket at 7th position to “}” that will result in {{{}}}{} now this is balanced.

## Algorithm

• First we will remove all the balanced part of the input string for example }{{}}{ after removing the balanced part we will be left with }{
• Notice it carefully as we can see after removing all the balanced we will always  left with expression of “}}{{“  this type. That is an expression that contains 0 or more closing brackets or 0 or more opening brackets.
• Now we will count the number of closing brackets let m be total number of closing brackets and n be opening brackets
• Store the length of the unbalanced part in red_len that is total value  m+n.
• Now return the value of  return ceil(m/2) + ceil(n/2) which is actually equal to (m+n)/2 + n%2 when m+n is even.

## C++ Code (Method 1) :-

`  #include<bits/stdc++.h>  using namespace std;int countMinReversals(string expr){  int length = expr.length();  // length of the expression must be even to make it balanced by using reversals.   if (length%2)    return -1;  //After this loop, stack will have only the unbalanced part of expression  stack s;  for(int i=0; i<length; i++)  {   if(expr[i]=='}' && !s.empty())   {    if(s.top()=='{')      s.pop();    else      s.push(expr[i]);   }  else    s.push(expr[i]);  }  // Length of the reduced expression red_len = (m+n)  int red_len = s.size();  //count the number of opening brackets at the end of the stack  int n = 0;  while (!s.empty() && s.top() == '{')  {  s.pop();  n++; }  // return ceil(m/2) + ceil(n/2) which is  // actually equal to (m+n)/2 + n%2 when m+n is even.  return(red_len/2 + n%2);}  // Driver program to test above functionint main(){  string expression;  cout<<"Enter the curly brackets : ";  cin>>expression;  cout<<countMinReversals(expression); return 0;}`

## Output:-

`Enter the curly brackets : }{2`
`Enter the curly brackets : }}}}2`

## Method 2:-

• There is another efficient approach the idea is to maintain the count of opening and closing brackets
• If the  length of input string is odd then return -1 that means it can never be balanced
•  Run a loop from i equal 0 to size of the expression and count the left brackets
• Else check if the count of the left bracket is 0 if its 0 then increment count of right brackets else decrement count of left brackets.
• Then store the ceil value of (left_brace / 2.0+ right_brace / 2.0  ) and return the value of ans.
```  #include <bits/stdc++.h>
using namespace std;

int countMinReversals(string expression)
{
int len = expression.length();

//Expressions of odd size can never be balanced
if(len % 2 != 0) {
return -1;
}

int left_bracket = 0, right_bracket = 0;
int ans;

for(int i = 0; i < len; i++) {
//If we find a left bracket then we simply increment the left bracket

if(expression[i] == '{') {
left_bracket++;
}

else {
if (left_bracket == 0) {
right_bracket++;
}
else {
left_bracket--;
}
}
}
ans = ceil(left_bracket / 2.0) + ceil(right_bracket / 2.0);
return ans;
}

// Driver program to test above function
int main()
{
string expr;
cout<<"Enter the Curly brackets : "; cin>>expr;

cout<<"Minimum number of bracket reversals needed to make an expression balanced : ";
cout << countMinReversals(expr);
return 0;
}```

## Output :-

```Enter the Curly brackets : }{{{
Minimum number of bracket reversals needed to make an expression balanced : 3```