Algorithm

Problem Name: Data Structures - Balanced Brackets

Problem Link: https://www.hackerrank.com/challenges/balanced-brackets/problem?isFullScreen=true

In this HackerRank in Data Structures - Balanced Brackets solutions

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 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

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

Function Description

Complete the function isBalanced in the editor below.

isBalanced has the following parameter(s):

  • string s: a string of brackets

Returns

  • string: either YES or NO

Input Format

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

Constraints

  • 1 <= n <= 10**3
  • 1 <= |s| <= 10**3 ,where |s| is the length of the sequence.
  • All chracters in the sequences ∈ {{},(,),[,]}

Output Format

For each string, return YES or NO.

Sample Input

STDIN           Function
-----           --------
3               n = 3
{[()]}          first s = '{[()]}'
{[(])}          second s = '{[(])}'
{{[[(())]]}}    third s ='{{[[(())]]}}'

Sample Output

YES
NO
YES

Explanation

  1. The string {[()]} meets both criteria for being a balanced string.
  2. The string {[(])} is not balanced because the brackets enclosed by the matched pair { and } are not balanced: [(]).
  3. The string {{[[(())]]}} meets both criteria for being a balanced string.

 

 

 

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include 
#include 
#include 
#include 
#include 
#include 
#include 


int main(){
    int t,top=-1,i,flag,a0;
    char stack[100],temp;
    scanf("%d",&t);
    for(int a0 = 0; a0 < t; a0++){
        char* s = (char *)malloc(10240 * sizeof(char));
        scanf("%s",s);
        flag=1;
        for(i=0;s[i]!='\0';i++)
        {
            if(s[i] == '('||s[i]=='{'||s[i]=='[')
                stack[++top]=s[i];                
            if(s[i] == ')'||s[i]=='}'||s[i]==']')
            {
                  if(top == -1)
     {
      flag=0;     
      break;
     }
                   
                  else
                      {
                        temp=stack[top--];
                                             
                      if((s[i] == ')' &&temp != '(') ||(s[i] == '}' && temp!='{')||(s[i] == ']' && temp!='['))
                          flag=0;
                    }
            }
        }
        if(top>=0)
        {
         while(top >= 0)
            temp=stack[top--];
         flag=0;
        }
         
        if(flag == 0)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


#include 

using namespace std;

string isBalanced(string s) {
    std::vector stack;
    bool flag = false;
    for(int i = 0; (i < s.length()) && !flag; i++){
        
        switch(s[i]){
            case '{':
                stack.push_back(s[i]);
                break;
            case '[':
                stack.push_back(s[i]);
                break;
            case '(':
                stack.push_back(s[i]);
                break;
                
            case '}':
                if(stack.size() == 0){
                    flag=true;
                }
                else if('{' != stack.back()){
                    flag=true;
                }
                else{
                    stack.pop_back();
                }
                break;
                
             case ']':
                if(stack.size() == 0){
                    flag=true;
                }
                else if('[' != stack.back()){
                    flag=true;
                }
                else{
                    stack.pop_back();
                }
                break;
                
              case ')':
                if(stack.size() == 0){
                    flag=true;
                }
                else if('(' != stack.back()){
                    flag=true;
                }
                else{
                    stack.pop_back();
                }
                break; 
        }
    }
    return (flag || (stack.size() != 0)) ? "NO" : "YES";
}

int main() {
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        string s;
        cin >> s;
        string result = isBalanced(s);
        cout << result << endl;
    }
    return 0;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - Java Programming


import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'isBalanced' function below.
     *
     * The function is expected to return a STRING.
     * The function accepts STRING s as parameter.
     */

   public static String isBalanced(String s) {
        Stack apertura = new Stack<>();
          Stack cierre = new Stack<>();
          Map pairs = new HashMap<>();
          pairs.put('{', '}'); 
          pairs.put('(', ')');
          pairs.put('[', ']');     
          for(int i = 0;i {
            try {
                String s = bufferedReader.readLine();

                String result = Result.isBalanced(s);

                bufferedWriter.write(result);
                bufferedWriter.newLine();
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        bufferedReader.close();
        bufferedWriter.close();
    }
}
Copy The Code & Try With Live Editor

#4 Code Example with Javascript Programming

Code - Javascript Programming


'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the 'isBalanced' function below.
 *
 * The function is expected to return a STRING.
 * The function accepts STRING s as parameter.
 */

function isBalanced(s) {
    let stack = [];
    for(let i = 0; i < s.length; i++){       
        if(stack.length === 0){
            stack.push(s[i]);
            continue;
        }
        
        if(s[i] === "}" && stack[stack.length - 1] === "{")
            stack.pop();
        else if (s[i] === "]" && stack[stack.length - 1] === "[")
            stack.pop();
        else if (s[i] === ")" && stack[stack.length - 1] === "(")
            stack.pop();
        else
            stack.push(s[i]);
    }
    
    if(stack.length === 0) return "YES";
    return "NO";

}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const t = parseInt(readLine().trim(), 10);

    for (let tItr = 0; tItr < t; tItr++) {
        const s = readLine();

        const result = isBalanced(s);

        ws.write(result + '\n');
    }

    ws.end();
}
Copy The Code & Try With Live Editor

#5 Code Example with Python Programming

Code - Python Programming


#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'isBalanced' function below.
#
# The function is expected to return a STRING.
# The function accepts STRING s as parameter.
#

def isBalanced(s):
    stack=[]
    if len(s)%2!=0:
        return 'NO'
    for i in s:
        if i in ['(','[','{']:
            stack.append(i)
        else :
            if not stack:
                return 'NO'
            if (i==')' and stack[-1]=='(') or (i==']' and stack[-1]=='[') or (i=='}' and stack[-1]=='{'):
                stack.pop()
            
        
    if stack:
        return 'NO'
    else:
        return 'YES'

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input().strip())

    for t_itr in range(t):
        s = input()

        result = isBalanced(s)

        fptr.write(result + '\n')

    fptr.close()
Copy The Code & Try With Live Editor

Demonstration

Previous
[Solved] Components in a graph solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Castle on the Grid solution in Hackerrank - Hacerrank solution C, C++, java,js, Python