[Programmers] 5. 기본 자료구조: 스택 (Stack) 그리고 스택의 활용

illstandtall·2021년 4월 28일

programmers python 괄호검사 스택 자료구조 후위표기법

Programmers dev course

목록 보기

6/34

오류에 대한 지적이나 질문, 토의 환영합니다. 자유롭게 댓글 남겨주세요!.!

자료구조 3. 스택 (Stack)

데이터를 넣을 때에는 한 쪽 끝에서 밀어넣고, 꺼낼 때에는 같은 쪽에서 꺼내는 자료구조입니다.
후입선출(Last In First Out: LIFO) 자료구조라고도 합니다.

스택에서 발생하는 오류

비어있는 스택에서 데이터를 꺼내려 할때 (스택 언더플로우: Stack Underflow)
꽉찬 스택에 데이터를 넣으려 할 때 (스택 오버플로우: Stack Overflow)

스택의 연산

size(): 현재 스택에 들어 있는 데이터 원소 개수를 반환합니다.
isEmpty(): 현재 스택이 비어 있는지를 판단합니다.
비어있으면 True를 비어있지 않으면 False를 반환합니다.
push(x): 스택에 데이터 x를 추가합니다.
pop(): 스택의 맨 위의 데이터 원소를 제거하며, 반환합니다.
peek(): 스택의 맨위의 데이터 원소를 반환합니다.

스택의 구현

배열을 이용한 구현 (Python 리스트와 매서드를 이용)

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]

연결리스트를 이용한 구현 (양방향 연결리스트 이용)

from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList

class LinkedListStack:
    def __init__(self):
        self.data = DoublyLinkedList()
        
    def size(self):
        return self.data.getLength()
    
    def isEmpty(self):
        return self.size() == 0
        
    def push(self, item):
        node = Node(item)
        self.data.insertAt(self.size() + 1, node)
        
    def pop(self):
        return self.data.popAt(self.size())
        
    def peek(self):
        return self.data.getAt(self.size()).data

스택 연습문제 1.: 수식의 괄호 유효성 검사

올바른 수식들
- $(A + B)$
- ${(A + B) * C}$
- $[(A + B) * (C + D)]$
잘못된 수식들
- $(A + B$
- ${A + B) * C}$
- $(A + B] * [C + D)$

알고리즘: 수식을 왼쪽부터 한 글자씩 읽으며 판단
- 1) 여는 괄호를 만났을 때: 스택에 push
- 2) 닫는 괄호를 만났을 때
  - 2-1) 스택이 비어 있을 때: 올바르지 않은 수식
    - 2-2) 스택이 비어있지 않을 때:
      - 2-2-1) 스택에서 pop한 값이 쌍을 이루는 여는 괄호일 때: Pass
      - 2-2-2) 맞지 않는 괄호일 때: 올바르지 않은 수식
- 3) 끝까지 검사한 후 스택이 비어있으면 올바른 수식

python code 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 S.isEmpty()

스택의 연습문제 2: 수식의 후위표기법

중위 표기법 (infix notation): 연산자가 피연산들의 사이에 위치
후위 표기법 (postdix notation): 연산자가 피연산자들의 뒤에 위치

중위 표기	후위 표기
$(A + B)$	$AB+$
${(A + B) * C}$	$AB+C*$
$[(A + B) * (C + D)]$	$AB+CD+*$

알고리즘: 수식을 왼쪽부터 한 글자씩 읽으며 판단
- 1) 피연산자를 만날 경우: 그냥 출력
- 2) 연산자를 만날 경우: 스택에 push()
  - 2-1) 스택이 비어 있는 경우: push()
  - 2-2) 스택이 비어있지 않은 경우:
    - 2-2-1) 개괄호일 경우: push()
    - 2-2-2) 폐괄호일 경우: 개괄호를 만날 때까지 스택에 있는 연산자 pop() (괄호는 버림)
    - 2-2-3) 다른 연산자일 경우:
    - 2-3-3-1) 스택에 들어있는 연산자가 우선순위가 높거나 같을 경우: pop()하고 출력
    - 2-3-3-2)스택에 들어있는 연산자가 우선순위가 낮을 경우: push()

python code 2

def solution(S):
    opStack = ArrayStack()
    answer = ''
    
    for c in S:
        # operand
        if 'A' <= c and c <= 'Z':
            answer += c
        # operator
        else:
            # empty
            if opStack.isEmpty():
                opStack.push(c)
            # not empty
            else:
                # open braket
                if c == '(':
                    opStack.push(c)
                # closed bracket
                elif c == ')':
                    while opStack.peek() != '(':
                        answer += opStack.pop()
                    opStack.pop()
                # other operators
                else:
                    # high or same priotity of stack.peek
                    while not opStack.isEmpty() and prec[c] <= prec[opStack.peek()]:
                        answer += opStack.pop()
                        
                    # low priotity of stack.peek
                    opStack.push(c)
        
    while not opStack.isEmpty():
        answer += opStack.pop()
    
    return answer

스택의 연습문제 3: 후위표기된 수식의 계산

알고리즘: 수식을 왼쪽부터 한 글자씩 읽으며 판단
- 1) 피연산자를 만났을 때: 스택에 푸쉬
- 2) 연산자를 만났을 때: 두 개를 pop하여 연산

python code 3

def postfixEval(tokenList):
    st = ArrayStack()
    
    for token in tokenList:
        if type(token) is int:
            st.push(token)
        else:
            tmp2 = st.pop()
            tmp1 = st.pop()
            
            if token == '+':
                st.push(tmp1+tmp2)
            elif token == '-':
                st.push(tmp1-tmp2)
            elif token == '*':
                st.push(tmp1*tmp2)
            else:
                st.push(tmp1//tmp2)
    
    return st.pop()