Minimum Bracket Reversals

In minimum bracket reversals problem, we have given a string s containing an expression of characters ‘{‘ and ‘}’ only. Find the minimum number of bracket reversals needed to make an expression balanced.

Example

Input : s = “}{”

Output: 2

Input : s = “{{{”

Output: The given expression can not be balanced.

Algorithm for Minimum Bracket Reversals

1. Initialize a string s containing an expression of characters ‘{‘ and ‘}’ only.
2. Check if the size of the string mod 2 is not equal to 0, return -1.
3. Else create a stack data structure.
4. Traverse through the given string and check if the character at the current index of the string is not equal to ‘}’ or the size of the stack is 0, push the character at the current index of the string in the stack else check if the element at the top of the stack is ‘{‘, pop the top of the stack else push the character at the current index of the string in the stack.
5. Create an integer variable and store the size of the stack in it. Also, create a counter variable to count the brackets and initialize it as 0.
6. Traverse while the stack is not empty and the element at the top of the stack is equal to ‘{‘, pop the element at the top of the stack and increment the counter by 1.
7. Divide integer variable in which the size of the stack was stored earlier by 2 and add it to counter variable mod 2. Return the result after addition.
8. Check if the returned value is equal to -1, print “The given expression can not be balanced” else print the returned value.

C++ Program for Minimum Bracket Reversals

#include<bits/stdc++.h> 
using namespace std; 

int MinReversals(string s){ 
    int len = s.length(); 
    
    if(len%2){ 
        return -1;
    }
    
    stack<char> st; 
    
    for(int i=0; i<len; i++){ 
        if(s[i]=='}' && !st.empty()){
        
            if(st.top()=='{'){ 
                st.pop(); 
            }
            
            else{
                st.push(s[i]); 
            }
        } 
        else{
            st.push(s[i]); 
        }
    } 
    
    int red_len = st.size(); 
    int n = 0; 
    
    while(!st.empty() && st.top() == '{'){ 
        st.pop(); 
        n++; 
    } 
    
    return (red_len/2 + n%2); 
} 

int main(){ 
    string s = "}}{{"; 
    
    if(MinReversals(s) == -1){
        cout << "The given expression can not be balanced."; 
    }
    else{
        cout << MinReversals(s);
    }
    
    return 0; 
}

2

Java Program for Minimum Bracket Reversals

import java.util.Stack; 
  
class countMinReversals{ 
  
    static int MinReversals(String s){ 
        int len = s.length(); 
      
        if(len%2 != 0){ 
            return -1; 
        }
      
        Stack<Character> st = new Stack<>(); 
          
        for(int i=0; i<len; i++){ 
            char c = s.charAt(i); 
            
            if(c =='}' && !st.empty()){ 
                if(st.peek()=='{'){ 
                    st.pop(); 
                }
                else{
                    st.push(c); 
                }
            } 
            else{
                st.push(c);
            }
        } 
      
        int red_len = st.size(); 
        int n = 0; 
        
        while(!st.empty() && st.peek() == '{'){ 
            st.pop(); 
            n++; 
        } 
      
        return(red_len/2 + n%2); 
    } 
      
    public static void main(String[] args){ 
        String s = "}}{{"; 
          
        if(MinReversals(s) == -1){
            System.out.println("The given expression can not be balanced."); 
        }
        else{
            System.out.println(MinReversals(s));
        }  
    } 
  
}

2

Complexity Analysis for Minimum Bracket Reversals

Time Complexity: O(n) where n is the number of the characters in the given expression.

Space Complexity: O(n) because we used space for n characters.

References