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:
- 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.
- Now, create an empty character stack.
- Scan the expression from left to right and remove all the balanced part of the expression using stack.
- Now, after scanning, count the number of open parenthesis ‘{‘ and closing parenthesis ‘}’.
- 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:
- Check whether given Parentheses String are Balanced Parentheses or Not.
- Next Greater Element
- Infix to Postfix Conversion
- Infix to Prefix Conversion
- Prefix to Infix Conversion
- Prefix to Postfix Conversion
- Postfix to Infix Conversion
- Postfix to Prefix Conversion
- Find Minimum number of bracket reversals required to make an expression balanced.
- Implement Queue Using Two Stacks.
- Merge Overlapping Intervals using Stacks
- Implement Stack Using Linked List
- Largest Rectangular Area in Histogram
- Program to print matrix in zig-zag order.
- Program to print matrix in spiral order.
- Length of Longest Valid Substring
- Reverse a String using Stack
- Implement two stacks in a single array
- Print Bracket Number
- Next Greater Frequency Element
- Sort a Stack using Temporary Stack