[Python 자료구조] 스택(Stacks)

(스택의 구조, wikipedia)

 

#연산의 정의

• 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]

 

 

#양방향연결리스트로 구현한 스택

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) #1만큼 사이즈가 늘어난 뒤 추가

	def pop(self):
		return self.data.popAt(self.size())

	def peek(self):
		return self.data.getAt(self.size()).data

 

 

#수식의 후위 표기법 (Postfix Notation)

-  연산자가 피연산자들의 뒤에 위치

중위	후위
A*B+C	A+B*C
AB*C+	ABC*+
A+B+C	AB+C+
(A+B)*C	AB+C* 여는 괄호는 스택에 push 닫는 괄호를 만나면 여는 괄호가 나올 때까지 pop
A*(B+C)	ABC+** 연산자를 만났을 떄 여는 괄호 너머까지 pop하지 않도록 여는 괄호의 우선순위는 가장 낮게 설정
(A+B) * (C+D)	AB+CD+*
(A+(B-C))*D	ABC-+D*
A*(B-(C+D))	ABCD+-*

- 중위 표현식 왼쪽부터 한 글자씩 읽어서 피연산자이면 그냥 출럭

- '('이면 스택에 push

- ')'이면 '('이 나올 때까지 스택에서 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):
    stack = []
    answer = ''
    for c in S:
        if c not in '()+-*/':
            answer += c
        elif  c == '(':
            stack.append(c)
        elif c == ')':
            while stack[-1] != '(':
                answer += stack.pop()
            stack.pop()
        elif stack and prec[c] <= prec[stack[-1]]:
            answer += stack.pop()
            stack.append(c)
        else:
            stack.append(c)
            
    while stack:
        answer += stack.pop()
                
    return answer

 

 

 

#후위 표기 수식 계산

def postfixEval(tokenList):
    valStack = ArrayStack()
    
    for token in tokenList:
        if type(token) is int:
            valStack.push(token)
            
        elif token == '+':
            n1 = valStack.pop()
            n2 = valStack.pop()
            valStack.push(n2+n1)
        
        elif token == '-':
            n1 = valStack.pop()
            n2 = valStack.pop()
            valStack.push(n2-n1)
            
        elif token == '*':
            n1 = valStack.pop()
            n2 = valStack.pop()
            valStack.push(n2*n1)
            
        elif token == '/':
            n1 = valStack.pop()
            n2 = valStack.pop()
            valStack.push(int(n2/n1))
        
    return valStack.pop()

 

 

(솔루션 출처)

velog.io/@inyong_pang/12%EA%B0%95-%EC%8A%A4%ED%83%9D%EC%9D%98-%EC%9D%91%EC%9A%A9-%EC%88%98%EC%8B%9D%EC%9D%98-%ED%9B%84%EC%9C%84-%ED%91%9C%EA%B8%B0%EB%B2%95Postfix-Notation

velog.io/@inyong_pang/13%EA%B0%95-%ED%9B%84%EC%9C%84-%ED%91%9C%EA%B8%B0-%EC%88%98%EC%8B%9D-%EA%B3%84%EC%82%B0