## Algorithm

Problem Name: Data Structures - Balanced Brackets

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 <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

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 &

### #2 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>

using namespace std;

string isBalanced(string s) {
std::vector < char> 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 &

### #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 < Character> apertura = new Stack<>();
Stack cierre = new Stack<>();
Map < Character,Character> pairs = new HashMap<>();
pairs.put('{', '}');
pairs.put('(', ')');
pairs.put('[', ']');
for(int i = 0;i < s.length();i++){
if(pairs.keySet().contains(s.charAt(i))){
apertura.push(s.charAt(i));
} else{
if(apertura.size()<=0)
return "NO";
Character aux = apertura.pop();
if(s.charAt(i) == pairs.get(aux))
continue;
else
return "NO";
}
}
return (apertura.size() == 0 && cierre.size() == 0) ? "YES" : "NO";

}

}

public class Solution {
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

IntStream.range(0, t>.forEach(tItr -> {
try {

String result = Result.isBalanced(s);

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

bufferedWriter.close();
}
}

Copy The Code &

### #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();
});

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

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

const result = isBalanced(s);

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

ws.end(>;
}

Copy The Code &

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