Minimum number of Bracket Reversals Needed to make an expression balanced

“Minimum number of Bracket Reversals 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 Minimum number of Bracket 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 Reversals Needed to make an expression balanced is as follows:

/* Program to Find Minimum number of Bracket Reversals 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.

Related Posts:

1. Check whether given Parentheses String are Balanced Parentheses or Not.
2. Next Greater Element
3. Infix to Postfix Conversion
4. Infix to Prefix Conversion
5. Prefix to Infix Conversion
6. Prefix to Postfix Conversion
7. Postfix to Infix Conversion
8. Postfix to Prefix Conversion
9. Find Minimum number of bracket reversals required to make an expression balanced.
10. Implement Queue Using Two Stacks.
11. Merge Overlapping Intervals using Stacks
12. Implement Stack Using Linked List
13. Largest Rectangular Area in Histogram
14. Program to print matrix in zig-zag order.
15. Program to print matrix in spiral order.
16. Length of Longest Valid Substring
17. Reverse a String using Stack
18. Implement two stacks in a single array
19. Print Bracket Number
20. Next Greater Frequency Element
21. Sort a Stack using Temporary Stack