[Python] 자료구조 - 스택

스택

3. 스택(Stack)

- 선형 데이터 구조

- 데이터의 한쪽에서만 삽입(push)과 삭제(pop)가 발생함.

- ★LIFO(Last In First Out), 나중에 입력된 데이터가 가능 먼저 삭제됨.

- 데이터를 저장할 공간이 부족하면 오버플로(Overflow) 발생

- 삭제할 데이터가 없으면 언더플로(Underflow) 발생

- 한번에 하나의 데이터만 처리 가능

#파이썬에서 제공하는 list로 구현

stack = []

#push - 입력
stack.append(10)
stack.append(5)
stack.append(7)

print(stack)

#pop - 삭제
stack.pop()
print(stack)

 

#노드를 이용하여 구현

class Node :

    def __init__(self, data):
        self.data = data
        self.prev = None

class Stack :

    def __init__(self):
        self.top = None
        self.size = 0

    def printStack(self) :
        tmp = self.top
        out = ''
        while tmp :
            out = ',' + str(tmp.data) + out #거꾸로 출력
            tmp = tmp.prev
        print(out)

    def push(self, new_data) :
        if self.size == 0 :
            new_node = Node(new_data)
            self.top = new_node
            self.size = 1
        
        else :
            new_node = Node(new_data)
            new_node.prev = self.top
            self.top = new_node
            self.size += 1

    def pop(self) :
        if self.size == 0 :
            print("빈 스택입니다.")

        else :
            self.top = self.top.prev
            self.size -= 1
       

stack = Stack() #클래스를 객체로 만듦
stack.push(10) 
stack.push(5) 
stack.push(7) 
stack.printStack()# 10, 5, 7

stack.pop() 
stack.printStack() # 10, 5,

stack.pop() 
stack.printStack() # 10,

stack.pop() 
stack.printStack() #

stack.pop() 
stack.printStack() #빈 스택입니다.

---

중위표기법 -> 후위표기법

#중위표기법을 후위표기법으로 변환하기

- list.append, list.pop 이용

<리스트>
1. 숫자 리스트
2. 연산자 리스트

◆괄호 有
- 연산자 리스트에 닫힌 괄호를 넣으면 열린 괄호를 만날 때까지 pop한 다음 pop된 그 연산자를 숫자 리스트에 쌓음

◆괄호 無
① 연산자 리스트에 연산자를 넣을 때 나중에 넣는 연산자의 우선순위가 더 높을 경우 그냥 그대로 위에 쌓음
② 연산자 리스트에 연산자를 넣을 때 나중에 넣는 연산자의 우선순위가 같거나 더 낮을 경우 이전 거 pop하고 pop된 그 연산자를 숫자 리스트에 쌓음
    ※하나가 pop 되었을 때 그 밑에 있는 것과도 추가로 비교해야 하는 것 놓치지 말기!!!

#참고 ) list[-1] : top을 의미

def postfix(exp) :

    number_list = [] #숫자 리스트
    op_list = [] # 연산자 리스트

    for i in exp :
        if i.isdigit() == True :
            number_list.append(i)

        elif i == '(' :
            op_list.append(i)

        elif i == ')' :
            while op_list[-1] != '(' :  # 열린 괄호 만날 때까지 pop하고 그 값을 숫자 list에 넣기
                number_list.append(op_list.pop())
                
            op_list.pop() # (빼기 
            
            
        elif i == '*' or i == '/' :
            while op_list and (op_list[-1] == '/' or op_list[-1] =='*') : #op_list가 있고 op_list의 top이 /일 경우
                number_list.append(op_list.pop())

            op_list.append(i)

        elif i == '+' or i == '-' :
            while op_list and (op_list[-1] =='*' or op_list[-1] == '/' or op_list[-1]  == '-' or op_list[-1]  == '+') :
                number_list.append(op_list.pop())

            op_list.append(i)

    #op_list에 남아있는 연산자 처리
    while op_list :
        number_list.append(op_list.pop())


    return number_list

postfix = postfix('7-3*5/3+(4-2)')

print(postfix)

 

#후위표기법을 보고 계산하기

def calcPostfix(list) :

    number_list = []

    for i in list :
        if i.isdigit() == True :
            number_list.append(i)
            
        elif i == '*':
            a = int(number_list.pop()) #두 번째 숫자
            b = int(number_list.pop()) #첫 번째 숫자
            number_list.append(a*b)
            
        elif i == '/':
            a = int(number_list.pop()) 
            b = int(number_list.pop()) 
            number_list.append(b/a)
            
        elif i == '+':
            a = int(number_list.pop()) 
            b = int(number_list.pop()) 
            number_list.append(a+b)
            
        elif i == '-':
            a = int(number_list.pop()) 
            b = int(number_list.pop()) 
            number_list.append(b-a)

    return number_list

calcpostfix = calcPostfix(['4', '5', '3', '-', '*', '7', '+'])

print(calcpostfix)