[Python] Stack 예제

여는 괄호와 닫는 괄호가 쌍을 이루는지를 확인하는 코드를 짜기 위해 스택 자료구조를 사용해 봅니다.

---

'(', ')', '{', '}', '[' 및 ']' 만 포함된 문자열이 주어졌을 때 입력 문자열이 유효한지 확인하는 프로그램을 작성하세요.

 

assert test_problem_stack("()")
assert test_problem_stack("()[]{}")
assert test_problem_stack("({[][]})")
assert test_problem_stack("({[]})")
assert not test_problem_stack("(]")
assert not test_problem_stack("(()]")
assert not test_problem_stack("(((])")
assert not test_problem_stack("((())")

 

def is_valid_parenthesis(s):
    pair = {
        '}': '{',
        ')': '(',
        ']': '[',
    }
    opener = "({["
    stack = []

    for char in s:
        if char in opener:  # 현재 글자가 여는 괄호인 경우
            stack.append(char)  # 스택에 추가합니다.
        else:  # 현재 글자가 닫는 괄호인 경우
            if not stack:  # 스택이 비어있는 경우 (즉, 여는 괄호가 없는 경우)
                return False  # 유효하지 않은 괄호 문자열이므로 False를 반환합니다.
            top = stack.pop()  # 스택의 가장 위에 있는 요소를 꺼내옵니다.
            if pair[char] != top:  # 꺼내온 요소와 현재 글자가 쌍을 이루지 않는 경우
                return False  # 유효하지 않은 괄호 문자열이므로 False를 반환합니다.

    return not stack  # 문자열 순회가 끝났을 때, 스택이 비어있으면 유효한 괄호 문자열이므로 True를 반환합니다.