스택(Stack)

후입선출(LIFO : Last In First Out) : 나중에 들어온 것이 먼저 나감.

스택에서 발생하는 오류

• 스택 언더플로우(stack underflow) : 빈 스택에서 데이터를 꺼내려 할 때
• 스택 오버플로우(stack overflow) : 꽉찬 스택에 데이터를 추가하려 할 때

스택의 추상적 자료구조 구현

• size() : 스택에 들어있는 데이터의 개수
• isEmpty() : 스택이 비어있는지 판단
• push(x) : 스택에 데이터 x 추가
• pop() : 스택의 TOP원소 제거하면서 반환
• peek() : 스택의 TOP원소 반환

스택 예제 1 : 수식의 괄호 유효성 검사

• 알고리즘

수식을 왼쪽부터 한 글자씩 읽음.

• '(, {, ['인 경우 --> 스택에 push
• '), }, ]'인 경우
  1) 스택이 비어 있으면 --> 올바른 수식 X
  2) 스택에서 pop하면서 여는괄호와 맞는 쌍인지 확인 --> 맞지 않으면 올바른 수식 X

수식을 다 읽은 후, 스택이 비어있지 않다면 올바른 수식 X

스택 예제 2 : 수식의 후위표기법

후위표기법(postfix notation) : 연산자가 피연산자들의 뒤에 위치
ex) 중위표기법 : 2+3*4 -> 후위표기법 : 234*+

알고리즘

수식을 왼쪽부터 한 글자씩 읽는다.

• 피연산자 --> 그냥 출력
• '(' --> 스택에 push
• ')' --> '('이 나올 때까지 스택을 pop하고 pop한 연산자들을 출력
• 연산자 --> 스택에서 현재 연산자보다 높거나 같은 우선순위의 연산자들을 pop하고 출력한다. 그 후 현재 연산자를 스택에 push

수식을 다 읽은 후, 스택에 남아있는 연산자 모두 pop하고 출력

코드

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]

prec = {
    '*': 3, '/': 3,
    '+': 2, '-': 2,
    '(': 1
}

def solution(S):
    answer = ''
    opStack = ArrayStack()
    for s in S:
        # 피연산자인 경우 -> 출력
        if s.isalpha():
            answer += s
        # 왼쪽 괄호 ( 인경우 -> push
        elif s == '(':
            opStack.push(s)
        # 오른쪽 괄호 ) 인경우 -> (이 나올때까지 pop
        elif s == ')':
            while 1:
                pop_s = opStack.pop()
                if pop_s == '(':
                    break
                answer += pop_s 
        # 연산자인 경우
        else: 
            # 스택이 비어있지 않는 경우 -> 스택에 있는 연산자와 현재 연산자 비교
            if not opStack.isEmpty():
                peek_s = opStack.peek()
                while prec[peek_s] >= prec[s]: # 스택 top 연산자 >= 현재 연산자 
                    pop_s = opStack.pop()
                    answer += pop_s
                    try: # 위에서 pop하면서 스택이 비어 peek할때 오류가 발생할 수 있음. 이땐 while문 break하고 스택에 현재 연산자 push
                        peek_s = opStack.peek()
                    except:
                        break                 
            opStack.push(s)
    # 수식을 다 읽은 후에도 스택이 비어있지 않을 경우, 스택이 빌때까지 pop한다.
    while not opStack.isEmpty():
        pop_s = opStack.pop()
        answer += pop_s

    return answer