[Python 알고리즘] 스택(Stack)-2 괄호 검사 프로그램 만들기

안녕하세요!

저번에 파이썬으로 자료구조인 스택(Stack)을 만들었었는데

오늘은 스택을 이용해서 괄호 검사 프로그램을 만들어보려고 합니다.

 

저번에 만든 스택 코드입니다!

# 배열 스택(리스트 만들기)
class ArrayStack:
    # 초기화
    def __init__(self, capacity):
        # 배열의 크기를 정할 변수
        self.capacity = capacity
        # 배열의 크기 설정
        self.array = [None] * capacity
        # 배열의 최상단()
        self.top = -1

    # 비어있는지 확인
    def isEmpty(self):
        return self.top == -1
    
    # 가득 차있는지 확인
    def isFull(self):
        return self.top == self.capacity - 1
    
    # 최상단에 값 추가
    def push(self, item):
        # 가득 차있지 않다면
        if not self.isFull():
            self.top += 1
            self.array[self.top] = item
        else: pass

    # 최상단에 값 제거 + 리턴
    def pop(self):
        # 비어있는지 않다면
        if not self.isEmpty():
            self.top -= 1
            return self.array[self.top + 1]
        else: pass

    # 최상단 값 리턴 (제거 x)
    def peek(self):
        if not self.isEmpty():
            return self.array[self.top]
        else: pass

    # 몇개의 값이 들어있는지 리턴
    def size(self): return self.top + 1

 

이제 checkBrackets라는 괄호를 검사하는 함수를 만들겠습니다.

이 함수는  "{", "[", "(" 를 만나면 스택에 넣고 "}", "]", ")"를 만나면

스택의 pop()을 동작시켜 값을 비교합니다.

 

여기서 이 3가지 조건을 만족시키지 못한다면 괄호가 잘못 설정된 것인데요

# 조건1: 왼쪽 괄호와 오른쪽 괄호의 개수가 같아야 한다.

(괄호가 열렸는데 닫히는 괄호가 없는 경우입니다.)

# 조건2: 같은 종류인 경우 왼쪽 괄호가 오른쪽보다 먼저 나와야 한다.

(괄호가 닫혔는데 한번 더 닫으려고 하는 경우입니다.)

# 조건3: 다른 종류의 괄호 쌍이 서로 교차하면 안된다.

(다른 괄호를 먼저 닫으려고 하는 경우입니다.)

 

코드는 다음과 같습니다.

# 배열 스택(리스트 만들기)
class ArrayStack:
    # 초기화
    def __init__(self, capacity):
        # 배열의 크기를 정할 변수
        self.capacity = capacity
        # 배열의 크기 설정
        self.array = [None] * capacity
        # 배열의 최상단()
        self.top = -1

    # 비어있는지 확인
    def isEmpty(self):
        return self.top == -1
    
    # 가득 차있는지 확인
    def isFull(self):
        return self.top == self.capacity - 1
    
    # 최상단에 값 추가
    def push(self, item):
        # 가득 차있지 않다면
        if not self.isFull():
            self.top += 1
            self.array[self.top] = item
        else: pass

    # 최상단에 값 제거 + 리턴
    def pop(self):
        # 비어있는지 않다면
        if not self.isEmpty():
            self.top -= 1
            return self.array[self.top + 1]
        else: pass

    # 최상단 값 리턴 (제거 x)
    def peek(self):
        if not self.isEmpty():
            return self.array[self.top]
        else: pass

    # 몇개의 값이 들어있는지 리턴
    def size(self): return self.top + 1

# 괄호 검사기
def checkBrackets(statement):
    # 용량이 100인 스택 생성
    stack = ArrayStack(100)
    
    # for문으로 한글자씩 코드 검사
    for ch in statement:
        # 왼쪽 괄호 스택에 넣기
        if ch in ('{[('):
            stack.push(ch)
        # 오른쪽 괄호일 때 왼쪽 괄호 꺼내기
        elif ch in ('}', ']', ')'):
            # 조건2 위반 (오른쪽 괄호가 먼저 나옴)
            if stack.isEmpty():
                return False
            else:
                # 꺼낸 왼쪽 괄호와 오른쪽 괄호 비교
                left = stack.pop()
                # 조건3 위반 (쌍이 맞지 않을 경우)
                if (ch == "}" and left != "{") or \
                    (ch == "]" and left != "[") or \
                    (ch == ")" and left != "("):
                    return False
    
    # 스택이 비었으면 TRUE 리턴 스택이 비지 않았으면 조건1 위반(괄호의 갯수가 다름)
    return stack.isEmpty()