Java Implementation of minimum number of bracket reversals needed to make an expression balanced

Problem Statement

Given a String S of size N consisting of only '(' & ')' .The task is to find the minimum number of bracket reversals needed to make the string balanced,or determine if it is impossible.

Example: 

Input: exp = ")(" 

Output: 2 

Explanation: change '(' to ')' and ')' to '(' 

Input: exp = "(((" 

Output: -1

Input: exp = "(((()()"

Output: -1

Input: exp = "(())"  

Output: 0  

Input: exp = ")(())(((" 

Output: 3

Approach:Find the balanced part of the string and remove it from the rest of the string.Then let N=count of  ' ( ' and M=count of  ' ) ' in the new updated string.Minimum reversals required will be

                                                                    [ (M+N)/2  +  N%2 ]

Solution

Below is the java implementation of the above approach:

Code

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public static void main (String[] args) {
        Scanner obj=new Scanner(System.in);
        int t=obj.nextInt();
        while(t-->0)
        {
            String s=obj.next();
            if(s.length()%2==1)
            {
                System.out.println("-1");
            }
            else
            {
                Stack<Character> stack=new Stack<>();
                for(int i=0;i<s.length();i++)
                {
                    if(stack.size()==0)
                    {
                        stack.push(s.charAt(i));
                    }
                    else
                    {
                        if(s.charAt(i)==')' && stack.peek()=='(')
                        {
                            stack.pop();
                        }
                        else if(s.charAt(i)==')' && stack.peek()!='(')
                        {
                            stack.push(s.charAt(i));
                        }
                        else
                        {
                            stack.push(s.charAt(i));
                        }
                    }
                }
                String str="";
                String str2="";
                StringBuilder sb=new StringBuilder();
                while(stack.size()>0)
                {
                    sb.append(stack.pop());
                }
                str=sb.toString();
                for(int i=str.length()-1;i>=0;i--)
                {
                    str2+=str.charAt(i);
                }
                if(str2.length()%2==1)
                {
                    System.out.println("-1");
                }
                else
                {
                    int count1=0,count2=0;
                    for(int i=0;i<str2.length();i++)
                    {
                        if(str2.charAt(i)=='(')
                        {
                            count1++;
                        }
                        else
                        {
                            count2++;
                        }
                    }
                    System.out.println((count1+count2)/2 + count1%2);
                }
            }
        }
    }
}

Time Complexity: O(n) ,n=String length

Feel free to comment if you have any doubt in comments section


For more Data structure and algorithms,computer science,programming,coding related problems search my website

Learn how to prepare for Information Technology Based companies here