Minimum number of Reversal Needed to make an expression balanced

“Minimum number of Reversal Needed to make an expression balanced” is again an important application of stack data structure. Here, we have given an expression consisting of parenthesis of type ‘{‘ and ‘}’. Our task is to find the minimum number of bracket reversal needed to make an expression balanced. The reversal is to convert the parenthesis of type ‘{‘ into ‘}’ and vice-versa. 

If the expression cannot be converted into balanced expression, simply return “-1”.

Example:
1. {{}}   => 0 number of reversal needed as the expression is already balanced.
2. }}{{    =>  2 reversals needed to make an expression balanced in the form {}{}.
3. }}}}  => Again, 2 reversals needed to make an expression balanced in the form {}{}.
4. {{{{}} => Only 1 reversal is needed to make an expression balanced in the form {}{{}}.

The steps required to find the minimum number of reversals needed to make an expression balanced are as follows:

  1. The expression can only be balanced if the number of characters in the expression is even. So, firstly, check whether the length of expression is even or not, if it is odd, simply return -1 because the expression cannot be balanced.
  2. Now, create an empty character stack.
  3. Scan the expression from left to right and remove all the balanced part of the expression using stack.
  4. Now, after scanning, count the number of open parenthesis ‘{‘ and closing parenthesis ‘}’.
  5.  Now, return ceil of half count of open parenthesis and ceil of half count of closing parenthesis, which is desired result.

FORMULA : ceil(a/2) + ceil(b/2).

Where, a and b is count of open and closing parenthesis respectively.


 C++ Program to  Find Minimum Number of Bracket Reversal needed to make an expression balanced


#include<bits/stdc++.h>
using namespace std;
int countReversals(string str)
{
    if(str.length() % 2 != 0)
    return -1;
    
    stack<char>st;
    
    /*Remove all the balanced part of the expression
     and pushing remaing into stack*/
    for(int i = 0 ; i < str.length() ; i++)
    {
        if(str[i] == '}' && !st.empty() && st.top()=='{')
        st.pop();
        else 
        st.push(str[i]);
    }
    int rem_len = st.size(); 
  
    // count opening brackets at the end of 
    // stack 
    int n = 0; 
    while (!st.empty() && st.top() == '{') 
    { 
        st.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 (rem_len/2 + n%2); 
}
int main()
{
    string str;
    cout<<"Enter the expression of parenthesis : ";
    cin>>str;
    int res = countReversals(str);
    if(res == -1)
    cout<<"\nThe expression is of odd length, hence cannot be balanced";
    else
    cout<<"\nThe number of reversals needed to make an expression balanced is "<<res;
}

OUTPUT:
Enter the expression of parenthesis: }}{{
The number of reversals needed to make an expression balanced is 2.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *