문제

leetcode 20. Valid Parentheses
Given a string s containing just the characters
'(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:

• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.

괄호로 된 입력값이 올바른지 판별하는 문제입니다.
열린 괄호는 동일한 유형의 괄호로 닫아야하고, 올바른 순서로 닫아야합니다.

풀이

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        table ={
            ')': '(',
            '}': '{',
            ']': '['
        }
        
        for char in s :
            if char not in table:
                stack.append(char)
            elif not stack or table[char] != stack.pop():
                return False
        return len(stack) == 0

입력받은 문자열을 반복문으로 돌며 여는 괄호를 만날 때는 스택에 푸시push한다. 닫는 괄호를 만날 때 스택에서 팝pop하여 괄호 쌍이 맞는지 확인하면, 괄호의 순서와 열린 괄호와 닫힌 괄호의 유형이 같은지 확인할 수 있다.
예를 들어

input: s = "{[]}"

입력 s가 다음과 같을 때, '{' -> '[' -> ']' -> '}'순서로 반복문을 돕니다.

첫번째, 두번째 반복에서 {와 [는 if char not in table:의 조건에 걸려 stack에 append됩니다. 
stakc = ['{', '[']

세번째 반복에서 char = ']'이고, table[']'] = '['이다. stack.pop()을 하면 stack의 가장 마지막 요소인 '['가 반환되면 삭제된다.(stack = ['{']) 따라서 table[char] = stack.pop().

네번째 반복에서 char = '}'이고, table['}'] = '{' == stack.pop() = '{'이므로 elif에 걸리지 않고 stack은 pop되어 stack =[]이 된다.

마지막 return 에서 len(stack) == 0이 True를 반환하게 된다.