Answer to Question #249662 in Java | JSP | JSF for Tarurendra Kushwah

Question

Misha was playing with Balanced Brackets alone. Mykhailo also wanted to play the game with her, so he comes up and asks her a question.

Misha is allowed to chose a sub-sequence (i.e. not necessarily contiguous substring) of brackets. AFTER chosing a the sub-sequence, she is allowed to re-arrange it (if needed) such that this chosen sub-sequence (after rearrangement) is balanced. Find the maximum length of this sub-sequence. (Please note that the resulting sub-sequence , after rearrangement MUST be balanced.)

Input:

• First line will contain T
• T, number of testcases. Then the testcases follow.
• First line of each test case has an integer N
• N, denoting length of string.
• Second line of each test case has a string S
• S which is the string. String will only consist of '(' and ')'.

Output:

For each testcase, the maximum possible length of balanced string.

Constraints

• 1≤T≤10
• 1≤T≤10
• 1≤|S|≤10
• 5
• 1≤|S|≤105
• String will only consist of '(' and ')'.

Answer 1

import java.util.*;
import java.util.Scanner;
public class Main {
    static boolean Balanced(String expr)
    {
        Deque<Character> stack
            = new ArrayDeque<Character>();


        for (int i = 0; i < expr.length(); i++)
        {
            char x = expr.charAt(i);
 
            if (x == '(' || x == '[' || x == '{')
           {
                stack.push(x);
                continue;
            }


            if (stack.isEmpty())
                return false;
            char check;
            switch (x) {
            case ')':
                check = stack.pop();
                if (check == '{' || check == '[')
                    return false;
                break;
 
            case '}':
                check = stack.pop();
                if (check == '(' || check == '[')
                    return false;
                break;
 
            case ']':
                check = stack.pop();
                if (check == '(' || check == '{')
                    return false;
                break;
            }
        }
 
        return (stack.isEmpty());
    }
    public static void main(String[] args)
    {
        Scanner input=new Scanner(System.in);
        System.out.print("Enter the number of test cases: ");
        int T=input.nextInt();
        for(int i=0;i<T;i++){
        System.out.println("Enter the string of brackets: ");
        String S = input.next();
        int N=S.length();
        System.out.println("The length of the string is: "+N);
        if (Balanced(S))
            System.out.println("Balanced ");
        else
            System.out.println("You chose unBalanced string ");}
    }
}