# Hackerrank - Balanced Brackets Solution

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. It must return a string: `YES`

if the sequence is balanced or `NO`

if it is not.

isBalanced has the following parameter(s):

*s*: a string of brackets

**Input Format**

The first line contains a single integer , the number of strings.

Each of the next lines contains a single string , a sequence of brackets.

**Constraints**

- , where is the length of the sequence.
- All chracters in the sequences ∈ {
,**{**,**}**,**(**,**)**,**[**}.**]**

**Output Format**

For each string, return `YES`

or `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 pair`{`

and`}`

are not balanced:`[(])`

. - The string
`{{[[(())]]}}`

meets both criteria for being a balanced string, so we print`YES`

on a new line.

### Solution in Python using stack

```
def isBalanced(S):
stack = []
pairs = {"{": "}", "[": "]", "(" : ")"}
for i in S:
if not stack:
stack.append(i)
elif i == pairs.get(stack[-1]):
stack.pop()
else:
stack.append(i)
return "YES" if not stack else "NO"
for i in range(int(input())):
S = input()
print(isBalanced(S))
```

### Solution in Python using regex

Not recommended

```
import re
def isBalanced(s):
p= "\[\]|\(\)|\{\}"
while re.search(p,s):
s = re.sub(p,"",s)
return "NO" if s else "YES"
for i in range(int(input())):
print(isBalanced(input()))
```

**Explanation**

Basically we are continually using regex to search for (), {} or [] and replace it with an empty string and break the loop once no more such match is found.

If we successfully replace all matches and the resultant value of s is empty string then our function will return "YES".

Example

```
Loop 1 >>> s = "{[()]}"
Loop 2 >>> s = "{[]}"
Loop 3 >>> s = "{}"
Loop 4 >>> s = ""
```

If we have a unbalanced parenthesis such as {] then our program will not be able to replace all values of the given string and our function will return "NO".

```
Loop 1 >>> s = "[[()]{(]}]"
Loop 2 >>> s = "[[]{(]}]"
Loop 3 >>> s = "[{(]}]"
```