[HackerRank] Stacks and Queues : Balanced Brackets (Python)

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

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

Sample Output

YES
NO
YES

Explanation

1. The string {[()]} meets both criteria for being a balanced string, so we print YES on a new line.
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, so we print YES on a new line.

첫번째 코드

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the isBalanced function below.
def isBalanced(s):
    front = 0
    end = len(s) -1
    answer = "YES"

    for i in range(len(s) // 2):
        if s[front + i] == '{':
            if s[end-i] != '}':
                answer = "NO"
                break
        elif s[front + i] == '(':
            if s[end-i] != ')':
                answer = "NO"
                break
        elif s[front + i] == '[':
            if s[end-i] != ']':
                answer = "NO"
                break
    return answer

예제만 보면 양쪽을 비교하면서 원하는 모양의 괄호가 나오지 않으면 "NO"

원하는 모양의 괄호가 나오면 "YES"로 해야겠다 생각을 하게됩니다.

하지만 이렇게 코드를 짜서 제출하면 { ( ( [ ] ) [ ] ) [ ] } 와 같은 괄호는 찾을 수 없습니다.

 

그래서 우리는 이 괄호 문제를 풀때 스택을 사용하게됩니다.

 

두번째 코드

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the isBalanced function below.
def isBalanced(s):
    stack = []
    answer = "YES"

    for i in range(len(s)):
        if s[i] == '{':
            stack.append('{')
        elif s[i] == '(':
            stack.append("(")
        elif s[i] == '[':
            stack.append("[")
        elif s[i] == ']':
            if len(stack) and stack[-1] == '[':
                stack.pop()
            else:
                answer = "NO"
        elif s[i] == ')':
            if len(stack) and stack[-1] == '(':
                stack.pop()
            else:
                answer = "NO"
        elif s[i] == '}':
            if len(stack) and stack[-1] == '{':
                stack.pop()
            else:
                answer = "NO"
    return answer

 

세번째 코드

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the isBalanced function below.
def isBalanced(s):
    stack = []
    answer = "YES"
    open_bracket = ['{', '[', '(']
    close_bracket = ['}', ']', ')']

    for i in range(len(s)):
        if s[i] in open_bracket:
            stack.append(s[i])
        elif s[i] in close_bracket:
            index = close_bracket.index(s[i])

            if len(stack) > 0 and stack[-1] == open_bracket[index]:
                stack.pop()
            else:
                answer = "NO"
                break
    if len(stack) != 0:
        answer = "NO"
    return answer

코드를 조금 줄이기위해서 괄호목록을 List로 만들어 비교했고 나머지 3개의 케이스를 통과시키기 위해서 

stack이 비어있지 않을경우 "NO"를 return 하도록 했습니다.

 

오늘은 여기까지!