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.

Related Posts:

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

You may also like...

Leave a Reply

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