[파이썬 자료구조] 괄호 매칭

<스택의 응용>  괄호 매칭

1.왼쪽 괄호는 스택에 push

2.오른쪽 괄호를 읽으면 pop 수행 

3.pop된 왼쪽 괄호와 바로 읽었던 오른쪽 괄호가 다른 종류이면 에러 처리, 같은 종류이면 다음 괄호를 읽음

4.모든 괄호를 읽은 뒤 에러가 없고 스택이 empty이면, 괄호들이 정상적으로 사용된 것

5.만일 모든 괄호를 처리한 후 스택이 empty가 아니면 짝이 맞지 않는 괄호가 스택에 남은 것이므로 에러 처리

파이썬 코드

def is_matched(expr):
    lefty = '({['
    righty = ')}]'
    S = Stack() #스택구현은 이전 글에 있습니다.
    for c in expr:
        if c in lefty: S.push(c)
        elif c in righty:
            if S.is_empty():
                return False
            if righty.index(c) != lefty.index(S.pop()):
                return False
    return S.is_empty()