Balanced Brackets

A bracket is considered to be any one of the following characters: (, ), {, }, [, or ].

Two brackets are considered to be a matched pair if the opening bracket (i.e., (, [, or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {}, and ().

A matching pair of brackets is not balanced if the set of brackets it encloses are not matched. For example, {[(])} is not balanced because the contents in between { and } are not balanced. The pair of square brackets enclose a single, unbalanced opening bracket, (, and the pair of parentheses encloses a single, unbalanced closing square bracket, ].

By this logic, we say a sequence of brackets is balanced if the following conditions are met:

• It contains no unmatched brackets.
• The subset of brackets enclosed within the confines of a matched pair of brackets is also a matched pair of brackets.

Given n strings of brackets, determine whether each sequence of brackets is balanced. If a string is balanced, return YES. Otherwise, return NO.

Example:

Input:  n=3, str[]={"{[()]}","{[)])}","{{[[(())]]}}"}
Output: YES
NO
YES

Approach

Java

import java.util.Stack;

public class BalancedBrackets {
    public static void main(String[] args) {
        String str[] = { "{[()]}", "{[(])}", "{{[[(())]]}}" };
        for (int i = 0; i < str.length; i++) {
            System.out.println(isBalanced(str[i]));
            ;
        }
    }

    private static String isBalanced(String s) {

        Stack<Character> st = new Stack<Character>();
        if (s.length() % 2 == 1)
            return "NO";
        else {
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[')
                    st.push(s.charAt(i));
                if (s.charAt(i) == ')' || s.charAt(i) == ']' || s.charAt(i) == '}') {
                    if (st.empty())
                        return "NO";
                    if ((s.charAt(i) == ')' && st.peek() == '(') || 
                            (s.charAt(i) == ']' && st.peek() == '[')
                            || (s.charAt(i) == '}' && st.peek() == '{'))
                        st.pop();
                    else
                        return "NO";
                }
            }
        }
        if (!st.empty())
            return "NO";
        return "YES";
    }
}

C++

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

string isBalanced(string s)
{
    stack<char> st;
    if (s.size() & 1)
        return "NO";
    else
    {
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == '(' || s[i] == '{' || s[i] == '[')
                st.push(s[i]);
            if (s[i] == ')' || s[i] == ']' || s[i] == '}')
            {
                if (st.empty())
                    return "NO";
                if ((s[i] == ')' && st.top() == '(') || (s[i] == ']' && st.top() == '[') || (s[i] == '}' && st.top() == '{'))
                    st.pop();
                else
                    return "NO";
            }
        }
    }
    if (!st.empty())
        return "NO";
    return "YES";
}

int main()
{
    int n = 3;
    string str[3] = {"{[()]}", "{[(])}", "{{[[(())]]}}"};
    for (int i = 0; i < n; i++)
    {
        cout << isBalanced(str[i]) << "\n";
    }
    return 0;
}