[백준/Python] 9012: 괄호

[백준/Python] 9012: 괄호

설명이 복잡하게 적혀 있긴 하지만 단순히 괄호가 올바른지를 검사하는 balacned parentheses 문제이다.

열린 괄호가 있으면 그에 맞는 닫힌 괄호 쌍이 존재해야 한다. 이는 스택 구조를 이용해 풀 수 있다.

우선 여는 괄호가 나오는 스택에 push한다. 그리고 닫는 괄호가 나오면 그 닫는 괄호에 맞는 여는 괄호 쌍이 존재하는지 확인하고 pop한다. 만약 스택이 비어있다면 괄호 쌍이 맞지 않는 것이므로 NO를 리턴한다. 예를 들어 ())인 경우 3번째 )에서 NO를 리턴하게 될 것이다. (push 1번, pop 2번)

"("가 나오면 push, ")"가 나오면 pop한 후, 만약 주어진 괄호가 전부 쌍에 맞게 존재한다면 for문을 다 돌고 난 뒤에는 스택이 비어 있을 것이다. 스택이 비어 있다면 YES를 리턴하고, 비어 있지 않다면 쌍이 맞지 않는 것이므로 NO를 리턴한다. 만약 괄호가 ((()와 같이 주어진다면 for문을 다 돌고 나서도 스택이 비어있지 않는다. (push 3번, pop 1번) 따라서 NO를 리턴한다.

소스코드

---

import sys

def paren_checker(expr):
    stack = []
    for i in expr:
        if i == "(":
            stack.append(i)
        elif i == ")":
            if len(stack) != 0: 
                stack.pop()
            else:
                return "NO" # 스택이 empty라면 여는 괄호 쌍이 더 존재하지 않는 것
    if len(stack) == 0:
        return "YES"
    else:
        return "NO"

t = int(sys.stdin.readline())

for i in range(t):
    expr = sys.stdin.readline()
    print(paren_checker(expr))