스택 괄호 검사

괄호 검사

프로그램에서는 여러 가지 타입의 괄호들이 쌍으로 존재하여야 하며, 괄호가 일치하지 않으면 잘못된 프로그램이기 때문에 컴파일러는 이를 검사하여야 한다. 이때 스택 자료구조를 사용할 수 있다.

괄호의 검사 조건은 아래 소스코드에 주석으로 명시해 두었다.

소스코드

from stack import Stack

def switch(i):
    return {'(': '1', '{': '1', '[': '1', ')': '2', '}': '2', ']': '2'}.get(i, '-1')

def match_bracket(i):
    return {')': '(', '}': '{', ']': '['}.get(i, '-1')

def check_matching(expr):
    s = Stack()

    # 문자열을 하나씩 비교하여 괄호일 경우 스택에 추가.
    for i in expr:
        ch = switch(i)
        if ch == '1':
            # 여는 괄호를 만나면 스택에 push.
            s.push(i)
        elif ch == '2':
            # 닫는 괄호를 만나면 스택에서 괄호를 하나 pop 하여 비교.
            op = s.pop()
            if op == -1:
                # 조건 1 or 2 위반.
                return False
            elif op == match_bracket(i):
                # 괄호 일치.
                pass
            else:
                # 조건 3 위반.
                return False
        else:
            # 괄호가 아닌 문자.
            pass

    # 스택에 괄호가 남아있는지를 확인.
    if s.is_empty():
        return True
    else:
        # 조건 1 위반.
        return False

    # 괄호 쌍이 일치하지 않거나(조건 1), 
    # 오른쪽 괄호가 먼저 나오거나(조건 2),
    # 괄호의 타입이 서로 다를 경우(조건 3) 오류를 출력한다.

if __name__ == "__main__":
    # 괄호가 포함된 문장이 주어짐.
    if check_matching("{ A[(i+1)]=0; }"):
        print("괄호 검사 성공")
    else:
        print("괄호 검사 실패")

출력

괄호 검사 성공