스택(Stacks) - 수식의 괄호 유효성 검사

문제 설명

소괄호: ( )
중괄호: { }
대괄호: [ ]
를 포함할 수 있는 수식을 표현한 문자열 expr 이 인자로 주어질 때, 이 수식의 괄호가 올바르게 여닫혀 있는지를 판단하는 함수 solution() 을 완성하세요. 이 함수는 수식의 괄호가 유효하면 True 를, 그렇지 않으면 False 를 리턴합니다.

 

올바른 수식

• (A +B)
• {(A + B) * C}
• [(A +B) * (C + D)]

올바르지 않은 수식

• (A +B
• A +B)
• {A * (B * C})
• [(A + B) * (C + D)}

 

 

알고리즘 설계 - 수식을 왼쪽부터 한 글자씩 읽어서

1. 여는괄호를 만나면 "( 또는 { 또는 [" 스택에 푸시

2. 닫는괄호를 만나면 ") 또는 } 또는 ] 

2-1. 스택이 비어있으면 올바르지 않은 수식

2-2. 스택에서 pop, 쌍을 이루는 여는 괄호인지 검사

2-2-1.맞지 않으면 올바르지 않는 수식

3. 끝까지 검사한 후 스택이 비어있어야 올바른 수식

 

 

 

 

풀이

class ArrayStack:

    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def push(self, item):
        self.data.append(item)

    def pop(self):
        return self.data.pop()

    def peek(self):
        return self.data[-1]


def solution(expr):
    
    match = {
        ')' : '(',
        '}' : '{',
        ']' : '['
    }
    
    S = ArrayStack()

    for c in expr:
        if c in '({[' :
            S.push(c)
        elif c in match:
            if S.isEmpty():
                return False
            else:
                t = S.pop()
                if t != match[c]:
                    return False
    return S.isEmpty()