Balanced Brackets

Balanced Brackets

A Bracket is considered to be anyone of the following charachters (, ), {, }, [ or ]. Two Brackets are considered as balanced if each opening Parentheses (i.e., (, { or [) is followed by closing Parentheses of exact same type. So, A sequence of Parentheses is considered to be balanced if

• It doesn't contains any unmatched brackets.
• The subset of brackets enclosed within the confines of a matched pair of brackets is also a matched pair of brackets.

Write a program to check whether each sequence of brackets is balanced. If it is balanced then print YES otherwise, print NO.

Input

A single string denoting sequence of brackets
input : {[()]}
           {[}]

Output

Display YESIf the brackets are balanced otherwise, print NO.
output : YES
             NO

To check whether the brackets are balanced or not, follow the below give algorithm

1. Declare a stack of java.util.Stack class
2. Now traverse the expression string exp.
   1. If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.
   2. If the current character is a closing bracket (‘)’ or ‘}’ or ‘]’) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
3. After complete traversal, if there is some starting bracket left in stack then “not balanced”

import java.util.Scanner;
import java.util.Stack;


public class Solution {


    public static boolean isBalanced(String expression) {

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < expression.length(); i++) {
            Character ch = expression.charAt(i);
            switch (ch) {
                case '(':
                case '[':
                case '{':
                    stack.push(ch);
                    break;
                case ')':
                    if (stack.isEmpty() || stack.pop() != '(') { // makes sure not to call .pop() on an empty stack
                        return false;
                    }
                    break;
                case ']':
                    if (stack.isEmpty() || stack.pop() != '[') {
                        return false;
                    }
                    break;
                case '}':
                    if (stack.isEmpty() || stack.pop() != '{') {
                        return false;
                    }
                    break;
                default:
                    break;
            }
        }
        return stack.isEmpty();
    }
 

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int a0 = 0; a0 < t; a0++) {
            String expression = in.next();
            System.out.println( (isBalanced(expression)) ? "YES" : "NO" );
        }
    }
}

   

Please write comments if you find any bug in above codes/algorithms, or find other ways to solve the same problem