Balanced Brackets Hackerrank problem solution

                                      Balanced Brackets Hackerrank

Balanced Brackets Hackerrank

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

Two brackets are considered to be a matched pair if the an 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 encloses 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 considered to be 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, print YES on a new line; otherwise, print NO on a new line.

Input Format

The first line contains a single integer, n, denoting the number of strings.
Each line i of the n subsequent lines consists of a single string, s, denoting a sequence of brackets.

Constraints

1<=n<=103
1<=lens<=103 , where lens is the length of the sequence.
Each character in the sequence will be a bracket (i.e., {, }, (, ), [, and ]).
Output Format

For each string, print whether or not the string of brackets is balanced on a new line. If the brackets are balanced, print YES; otherwise, print NO.

Sample Input

3
{[()]}
{[(])}
{{[[(())]]}}

Sample Output

YES
NO
YES
Explanation

The string {[()]} meets both criteria for being a balanced string, so we print YES on a new line.
The string {[(])} is not balanced because the brackets enclosed by the matched pairs [(] and (]) are not balanced.
The string {{[[(())]]}} meets both criteria for being a balanced string, so we print YES on a new line.

Solution

Define {, (, and [ as opening brackets and }, ), and ] as closing brackets.
Whenever an opening bracket appears, we push it onto the stack. Whenever a closing bracket appears, we check if it matches the opening bracket at the top of the stack. If it does, we continue analyzing the string; we can infer that the string is not balanced, and we print NO. After processing the string completely and the stack is empty, the string is balanced, and we print YES. Else, we print NO.

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <stack>
using namespace std;
string isBalanced(string s){
    stack <char> st;
    for(auto c:s){
        switch (c){
            case '(':
            case '{':
            case '[':
                  st.push(c);
                   break;
            case '}':
                if(st.empty() || st.top()!='{' )
                    return "NO";
                st.pop();
                break;
            case ']':
                if(st.empty() || st.top()!='[')
                    return "NO";
                st.pop();
                break;
            case ')':
                if(st.empty() || st.top()!='(')
                    return "NO";
                st.pop();
                break;
            default: break;
        }
    }
    return st.empty() ? "YES":"NO";
}

int main(){
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        string s;
        cin >> s;
        cout << isBalanced(s) << endl;
    }
    return 0;
}
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

	public static void main(String args[]) throws IOException {
		 String s; int tcCount; int iCount=0;
		 Scanner in = new Scanner(System.in);
		 tcCount = Integer.parseInt(in.nextLine());
		 while( iCount < tcCount ) {
	            s = in.nextLine();
	            int flag = 1, i = 0, l = s.length();
	            Stack<Character> st = new Stack<Character>();
	            for( i = 0; i < l; i++ ){
	                char ch = s.charAt(i);
	                if( ch == '(' || ch == '[' || ch == '{' )
	                    st.push( ch );
	                else {
	                    if( st.empty() ){
	                        flag = 0; break;
	                    } else {
	                        char c = (char) st.pop();
	                        if( (c == '(' && ch != ')') || (c == '[' && ch != ']') || (c == '{' && ch != '}') ){
	                            flag = 0; break;
	                        }
	                    }
	                }
	            }
             if( flag == 1 && st.empty() ) { System.out.println("YES"); } 
             else  { System.out.println("NO"); }
             iCount++;
	        }
		 in.close();
	}
}
# Enter your code here. Read input from STDIN. Print output to STDOUT
def is_matched(expr):
  lefty = "({["  # opening delimiters
  righty = ")}]" # respective closing delims
  S = []
  for c in expr:
    if c in lefty:
      S.append(c) # push left delimiter on stack
    elif c in righty:
      if not S:
        return False # nothing to match with
      if righty.index(c) != lefty.index(S.pop( )):
        return False # mismatched
  if not S:
    return True
  else:
    return False

num_cases = int(input())
while num_cases:
  input_text = raw_input()
  if (is_matched(input_text) == True):
    print "YES"
  else:
    print "NO"
  num_cases = num_cases -1
#include <iostream>
#include <vector>
#include <cstring>
#include <stack>

using namespace std;

bool isOpen(char c)
{
    if(c == '(' || c == '{' || c == '[')
        return true;
    return false;
}

bool isBalanced(char popped, char now)
{
    if(popped == '(' && now ==')')
        return true;
    if(popped == '[' && now ==']')
        return true;
    if(popped == '{' && now =='}')
        return true;
    return false;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        stack<char> s;
        string str;
        cin>>str;
        int no = 0;
        for(int i = 0; i < str.length(); i++)
        {
            char now = str[i];
            if(isOpen(now))
                s.push(now);
            else
            {
                char popped;
                if(s.size() > 0)
                {
                    popped = s.top();
                    s.pop();
                }
                else
                {
                    no = 1;
                    break;
                }
                if(isBalanced(popped, now))
                    continue;
                else
                {
                    no = 1;
                    break;
                }
            }
        }
        if(s.size() != 0)
            no = 1;
        if(no)
            cout<<"NO\n";
        else
        {
            cout<<"YES\n";
        }
    }
    return 0;
}

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

One comment: On Balanced Brackets Hackerrank problem solution

Leave a reply:

Your email address will not be published.