11강 요약

스택 자료구조에 대한 강의, 자료를 넣고 빼고 확인할 수 있다. 배열로도, 이전에 배웠던 연결리스트로도 구현 가능

스택이란?

선입 후출(LIFO)의 입출력을 가지는 자료구조로 스택의 top(가장 최근 자료를 가리킴)의 위치에 따라 늦게 들어온 순서대로 입력,삭제를 수행한다.

https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D
-위키백과

Stack의 메서드

size(): 현재 스택에 들어 있는 데이터 원소의 수를 구함
isEmpty(): 현재 스택이 비어 있는지를 판단 (size() == 0?)
push(x): 데이터 원소 x 를 스택에 추가
pop(): 스택에 가장 나중에 저장된 데이터 원소를 제거 (또한, 반환)
peek(): 스택에 가장 나중에 저장된 데이터 원소를 참조 (반환), 그러나 제거하지는 않음

문제

수식 괄호 검사, 대괄호[], 중괄호{}, 소괄호()를 스택을 이용하여 구분

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 True if S.isEmpty() else False

GitHub

https://github.com/ds02168/Study_Algorithm/tree/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/%EC%96%B4%EC%84%9C%EC%99%80%20%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%80%20%EC%B2%98%EC%9D%8C%EC%9D%B4%EC%A7%80/11%EA%B0%95