[python] Stack을 활용한 괄호검사 알고리즘

수식 표기나, 프로그래밍 언어, HTML 문서 등 다양한 분야에서 괄호로 구분문자를 사용한다.

이들은 주로 간단한 데이터나 문자열을 묶어 그룹으로 만들고 그룹으로 끝낸다.

 

예를 들어 다음과 같은 소스코드가 있을때,

array_max.h

int find_array_max(int score[], int n)
{
    int i, tmp = score[0];
    
    for (i = 1; i<n; i++){
        if(score[i] > tmp){
            tmp = score[i];
        }
    }
    return tmp;
}

 

해당 프로그램이 정상작동 하려면, 괄호들이 같은 유형들 끼리 쌍을 이루어야 한다. 해당 코드에서 괄호를 검사 시 다음과 같은 조건이 해당되어야 한다.

 

1. 왼쪽 괄호의 갯수와 오른쪽 괄호 갯수가 같아야 한다.

2. 같은 타입의 괄호에서 왼쪽 괄호가 오른쪽 괄호보다 먼저 나와야 한다.

3. 서로 다른 타입의 괄호 쌍이 서로를 교차하면 안된다.

 

예시를 보면

{A[(i+1)]=0;} 				## 오류 없음
if ((i==0) && (j==0)) 		## 오류: 조건 1위반
while (it < 10)) { it--;} 	## 오류 : 조건 2위반
A[(i+1])=0; 				## 오류 : 조건 3 위반

 

 

코드들을 보면, 가장 가까운 거리에 있는 괄호들끼리 서로 쌍을 이러우야 된다. 입력 문자열에서 왼쪽 괄호가 나오면 스택에 삽입하고, 오른쪽에 괄호가 나오면 삽입된 괄호를 꺼내 짜긍ㄹ 맞추어보면 검사가 가능하다.

• 문자를 저장하는 스택을 준비
• 입력 문자열의 문자를 하나씩 읽어 왼쪽 괄호를 만나면 스택 삽입
• 오른쪽 괄호를 만나면 pop()연산으로 최근 삽입된 괄호를 꺼냄 이때 비었다면 조건2에 위반
• 꺼낸 괄호가 오른쪽 괄호와 짝이 맞지 않으면 조건 3에 위배
• 끝까지 처리 했는데 괄호가 남아 있으면 조건 1위 위배

 

괄호검사구현

class Stack:
    def __init__(self):
        self.top = []

    def __str__(self):
        return str(self.top)

    def isEmpty(self): return len(self.top) == 0
    def size(self): return len(self.top)
    def clear(self): self.top = []

    def push(self, push):
        self.top.append(push)
    
    def pop(self):
        if not self.isEmpty():
            return self.top.pop(-1)
        
    def peek(self):
        if not self.isEmpty():
            return self.top[-1]


def checkBrackets(statement):
    stack = Stack()
    for ch in statement:
        if ch in ("{", "[", "("):
            stack.push(ch)
        elif ch in ("}", "]", ")"): ## 오른쪽 괄호가 나오지 않음
            if stack.isEmpty():
                return False
            else:
                left = stack.pop()
                if (ch == "}" and left != "{") or \
                    (ch == "]" and left != "[") or \
                    (ch == ")" and left != "(") :
                    return False
    return stack.isEmpty()

if __name__=="__main__":
    filename = "ArrayStack.h"
    with open(filename, "r") as code:
        line = code.read()
        result = checkBrackets(line)
        print(filename, "-->", result)