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

December 29, 2021

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 function
int 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