Stacks: Balanced Brackets

Stacks: Balanced Brackets

---

bracket은 (), {}, [] 이 세가지를 모두 포함한다.
이것을 매칭하는 문제이다.

구현코드

def is_matched(expression):
    stack = []
    for bracket in expression:
        if bracket in ['[', '{', "("]:
            stack.append(bracket)
        else:
            if stack:
                if bracket == ']':
                    leftBracket = stack.pop()
                    if leftBracket != '[':
                        return False
                elif bracket == '}':
                    leftBracket = stack.pop()
                    if leftBracket != '{':
                        return False
                elif bracket == ')':
                    leftBracket = stack.pop()
                    if leftBracket != '(':
                        return False
            else:
                return False
    return True

t = int(input().strip())
for a0 in range(t):
    expression = list(input().strip())
    if is_matched(expression) == True:
        print("YES")
    else:
        print("NO")

실행결과

# Input
3
{[()]}
{[(])}
{{[[(())]]}}

# Output
YES
NO
YES

• 하지만 이 방법은 runtime issue를 발생 시킨다.

새로운 솔루션

def is_matched(expression):
    stack = []
    for bracket in expression:
        if bracket == '{':
            stack.append('}')
        elif bracket == '[':
            stack.append(']')
        elif bracket == '(':
            stack.append(')')
        else:
            if len(stack) == 0 or bracket != stack[-1]:
                return False
            stack.pop()
    return len(stack) == 0

t = int(input().strip())
for a0 in range(t):
    expression = input().strip()
    if is_matched(expression) == True:
        print("YES")
    else:
        print("NO")

Dictionary를 이용한 방법

Advantage

• 다른 bracket을 필요로 하다면 쉽게 확장이 가능하다.
• if-else 또는 switch case를 다중으로 작성할 필요가 없다.
• O(1) call time을 가진다 (hash table이니 당연한 말이긴 하다).

def is_matched(expression):
    stack = []
    dicty = {'(':')', '[':']', '{':'}'}
    for x in expression:
        if x in dicty:
            stack.append(dicty[x])
        elif stack and x == stack[-1]:
            stack.pop()
        else:
            return False
            
    return not stack

t = int(input().strip())
for a0 in range(t):
    expression = input().strip()
    if is_matched(expression) == True:
        print("YES")
    else:
        print("NO")