자료구조 스택(Stack)

 이번 포스팅에서는 자료구조 중 스택에 대해서 알아보도록 하겠습니다.

 

1. 스택이란?

• 스택은 push연산으로 값을 입력받은 순서대로 삽입하고, pop연산으로 가장 최근에 삽입된 값을 삭제하는 자료구조입니다. 이 삽입/삭제 원칙을 후입선출(LIFO) 원칙이라고 합니다.

아래부터 push된 순서. 맨 위 값부터 pop

2. 스택의 코드 구현

class Stack:
    def __init__(self): ##생성자 Stack클래스 생성
        self.items = []

    def push(self, val): ## push 기능 구현
        self.items.append(val)

    def pop(self): ## pop 기능 구현 .. 여기까지 필수
        return self.items.pop()

    def top(self): ## pop될 때 나오는 가장 마지막에 입력된 데이터
        return self.items[-1]

    def __len__(self): ## Stack에 입력되어 있는 데이터 수
        return len(self.items)

    def isEmpty(self): ## 스택이 비어있을 때
        return self.__len__() == 0

• init생성자로 인스턴스를 생성할 수 있습니다. S = Stack() -> 자동으로 S라는 Stack의 인스턴스가 생성됩니다.
• append는 list 끝에 요소를 추가하는 메소드입니다. pop은 list 끝 요소를 제거하는 메소드입니다. pop은 제거되는 요소를 출력해줍니다.
• __init__, push, pop은 스택의  필수적인 요소고, 스택의 특성을 활용하여 알고리즘 짤 때 유용한 요소들을 Stack클래스에 구현해 놓을 수 있습니다. top 메소드는 가장 마지막에 입력된 데이터를 알 수 있습니다. len메소드로 Stack의 길이를 알 수 있고, isEmpty메소드로 스택이 비어있는지 확인 할 수 있습니다.

3. 스택의 응용 예제(Infix to Postfix)

 이번에는 문제를 풀면서 스택이 어떻게 활용되는지 살펴보도록 하겠습니다. 우리가 흔히 사용하는 연산식, 예를 들면

'1 + (2 + 3) / 5'이러한 연산식은 연산할 요소 가운데(In)에 연산자가 존재하여 Infix방식이라고 부릅니다. Postfix방식은 연산할 요소 뒤에 연산자가 존재합니다. 이를테면 2+3 -> 23+로 표현하는 것입니다. 위 식을 Postfix방식으로 표현하면

'123+5/+'가 됩니다. 수식을 Infix방식으로 입력받았을 때 이것을 Postfix방식으로 바꾸는 문제를 풀어보도록하겠습니다.

class Stack:
    def __init__(self):
        self.items = []

    def push(self, val):
        self.items.append(val)

    def pop(self):
        return self.items.pop()

    def top(self):
        return self.items[-1]

    def __len__(self):
        return len(self.items)

    def isEmpty(self):
        return self.__len__() == 0 ## 스택 정의

prec = {'(': 3, '*': 1, '/': 1, '+': 2, '-': 2, '^': 0} ## 연산자 우선순위 정의. 값을 통해서 비교

def infix_to_postfix(infix):
    opStack = Stack() ## 인스턴스 생성
    outstack = [] ## 스택에서 값을 꺼내서 넣을 리스트 생성  
    token_list = infix.split() ## 입력 받은 값을 ' '(스페이스)로 구분
    for token in token_list:
        if token == '(':
            opStack.push(token) ## ()가 최우선 연산순위이므로 나중에 괄호가 닫히게 되면 안에 있는 연산을 한번에 수행
        elif token == ')':
            while (opStack.top() != "("):
                outstack.append(opStack.top()) ## ()내의 연산자들을 스택에 차례로 append
                opStack.pop() ## append되었으니 스택에서 제거
                
            opStack.pop() ## 스택에 있는 '('제거
            
        elif token in '+-/*^': ## 연산자일 경우 우선순위에 따라 연산
            if opStack.isEmpty():
                opStack.push(token) ## 스택에 비어있으니 일단 push
            elif prec.get(token) < prec.get(opStack.top()): ##스택이 비어 있지 않으면 우선순위를 비교                              
                opStack.push(token)
            else:
                while prec.get(token) >= prec.get(opStack.top()): ## while문 실행으로 token에 비해 우선 순위높은 연산자들을 append
                    outstack.append(opStack.top())
                    opStack.pop()
                    if opStack.isEmpty():
                        break
                opStack.push(token) ## 토큰을 스택에 추가하고 다시 for문 반복
                          
        else: ##토큰이 operand(숫자)일 경우 리스트에 값을 추가해줍니다.
            outstack.append(token)
            
    while opStack: ##for문이 끝나고 Stack에 남아 있는 연산자들을 리스트에 append합니다.
        outstack.append(opStack.top())
        opStack.pop()

    return " ".join(map(str,outstack))
  	
infix_expr = input()
postfix_expr = infix_to_postfix(infix_expr)
print(postfix_expr)

• 우선 스택 클래스를 정의합니다. 그 다음 prec딕셔너리를 통해 연산자마다의 우선순위를 정해줍니다. 추후 if문을 통해 우선순위에 따라 스택에서 push 또는 pop할 수 있습니다.
• ()가 최우선 연산순위이므로, 토큰이 '('일 때 스택에 저장해둡니다. 그리고 토큰이 ')'이 되면 괄호가 닫힌 것이므로, 괄호 내의 연산을 '('가 나올 때까지 수행해주면 됩니다.
• 토큰이 연산자일 때, 예를 들면 2+3*5면 235*+가 되고, 2-3+5면 23-5+가 됩니다. 2+3*5의 경우 토큰이 *일 때 스택에 +가 있을 것입니다. 이럴 때 스택에 *를 push하고 5를 리스트에 추가를 하면 스택에 +*순으로 남게됩니다. 해당 값을 차례로 pop해서 리스트에 append하면 원하는 후순위 식이됩니다. 하지만 2-3+5일 때 위의 방식으로 하면 이상해집니다. 그러므로 연산 우선순위가 같거나 낮을 경우 스택의 연산자를 pop해서 리스트에 append시켜 줘야됩니다. 만약 우선순위가 높은 연산자의 경우는 스택에 push하면 됩니다. 
• 숫자들의 순서는 바뀌지 않으므로 토큰이 숫자이면 리스트에 그대로 append해줍니다.

 궁금하신 사항이나 잘못된 내용이 있으면 댓글로 알려주시면 감사하겠습니다~