[Datastructure] 스택과 활용(1)

스택

💡 스택이란

데이터 값을 저장하는 구조로 일차원의 선형 자료구조이다.
리스트가 가로형태로 배열되어있다면, 스택은 세로로 배열되어 있다.

허접한 그림이다. 봐주도록하자.

💡 사용법

list와 마찬가지로 삽입, 삭제, 탐색 연산이 제공된다.
단, 모든 연산은 LIFO원칙을 따라야한다.

💡 예시

push, pop, top, isEmpty, size(len) 의 5가지 연산이 제공된다고 가정하자.

class stack:
    def __init__(self): #클래스의 개게생성함수.
        self.items = []

    def push(self,val): #삽입
        self.items.append(val)

    def pop(self): #마지막 값 삭제, 리턴
        try:
            return self.items.pop()
        except:
            print("stack is empty now")

    def top(self) #마지막 값 리턴
        try:
            return self.items[-1]

        except:
            print("stack is empty now")

    def __len__(self): #len으로 호출하면 길이만 리턴한다.
        return len(self.items)

    def isEmpty(self): #0개면 true, 0이 아니면 false를 반환한다.
        return len(self) == 0

💡 시간복잡도

class stack의 시간복잡도는 O(1)이다. 각각 정의된 함수 모두 O(1)을 따르고 있다.

스택의 활용-괄호체크

수식의 괄호가 올바르게 입력되었는지 확인하는 함수를 스택을 이용해 만들어 보자

💡 문제정의

❗️

1. 괄호의 짝이 맞아야하고
2. 열린괄호로 시작해 닫힌 괄호로 끝나야한다.

이를 스택의 개념을 이용하면,
입력을 왼쪽부터 읽기 시작해 만약 ‘(‘가 등장하면 스택에 추가하고,
‘)’가 등장하면 스택의 ‘(‘를 뺀다.

스택의 개념을 이용하면 1,2를 모두 만족할 수 있는데,

1. 만약 짝이 안 맞는다면, 연산 종료 후, 스택에 ‘(‘가 남거나, 부족하다.
2. 만약 스택에 쌓인 ‘(‘가 없는데 ‘)’가 들어온다면, ‘(‘가 부족하다.

💡 코드

def parchecker(expression):
    s = stack()

    for char in expression:
        if char == '(': #만약'('가 들어오면 스택에 추가한다.
            s.push('(')

        elif char == ')': #만약 ')'가 들어오면
            if s.isempty(): #스택이 비어있을경우, 틀린 수식이다.
                return False
            else:
                s.pop() #스택이 있으면, 맨 위의'('를 삭제하고 리턴한다.

    if s.isempty(): #연산이 종료되고, 스택에 괄호가 남아있으면 틀린수식이다.
        return True
    else:
        return False

중괄호, 대괄호까지 체크해보자

만약 중괄호, 대괄호까지 체크해야한다면?

💡 문제정의

❗️

1. 괄호의 짝이 맞아야하고
2. 열린괄호로 시작해 닫힌 괄호로 끝나야한다.
3. 닫는 괄호가 입력으로 들어오면, s.top()과 짝이 맞는 형태의 값이어야한다. 괄호의 순서에 대한 것은 제외하고, 소,중,대괄호를 모두 체크해야하는 경우,
   위의 경우에서 괄호의 짝들만 추가로 고려해주면된다.
   고려하는 방식은 딕셔너리의 키:밸류 형태로 할 수 있다.

💡 코드

def allparchecker(expression):
    s = stack()
    d = {              #딕셔너리 형태로 짝을 만든다.
        ")" : "(",
        "}" : "{",
        "]" : "["
    }
    
    for char in expression:
        if char in "{[(":  #만약 입력값이 여는괄호라면, 스택에 push
            s.push(char)
        elif char in "}])": #닫는 괄호일때, 짝이 맞으면 스택 맨 위의 값 삭제, 다르거나 비어있으면 false
            if s.top() == d[char]: 
                s.pop()
            elif s.isEmpty():
                return False
            elif s.top() != d[char]:
                return False
                
    if s.isEmpty(): #만약 연산 종료되고, 스택이 비어있으면 올바른 수식이다.
        return True
    else:
        return False

참고자료

개인적인 공부를 위한 글이며, 모든 저작권은 신천수 교수님께 있습니다.
자세한 강의 내용은 신천수 교수님 강의를 참고하시면 좋을 것 같습니다.
😇 신천수 교수님 자료구조 강의