[자료구조와 알고리즘] #5. 스택

스택은 접시쌓기와 유사함

 

스택

• 선형 자료 구조로 Last in First out 구조를 가짐 
  • Push : 데이터를 넣는 것 
  • Pop : 원소 꺼내기 

S = Stack()
#A,B를 스택에 넣음 
S.push(A)
S.push(B)
#A,B를 각각 꺼내서 r1,r2에 넣음 
r1 = S.pop(). #B먼저 인출
r2 = S.pop(). #A인출 

#비어있는 스택에서 데이터 원소를 꺼내려고 할경우 오류 발생 : 스택언더플로우 
r3 = S.pop() 

#꽉찬 스택에 데이터 원소를 넣으려고 할 경우 : 스택오버플로우 
S.push(E)

 

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

1. 배열(array)를 이용하여 구현

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

2. 연결리스트를 이용하여 구현 

• 양방향 연결 리스트 이용 

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) #마지막에 Node를 추가해라 

	def pop(self):
		return self.data.popAt(self.size()) #맨마지막 노드를 pop 

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

3. 연산의 정의

• size() : 데이터 원소의 수 
• isEmpty() : 비어있는 여부 판단
• push(x) : x를 스택에 추가 
• pop() : 스택 맨위 원소를 제거 및 반환 
• peek() : 스택 맨위 원소를 반환(제거X) 

 

연습문제

def solution(expr):
    match = {
        ')': '(',
        '}': '{',
        ']': '['
    }
    S = ArrayStack()
    for c in expr:
        if c in '({[':
            
			S.push(c)

        elif c in match:
            if S.isEmpty():       #S가 비어있다면 False반환 
                return False
            else:
                t=S.pop()       #비어있지 않다면 pop 수행 

                if t != match[c]:  #pop 수행 결과가 match 안에 없다면 False 
                    return False
    return S.isEmpty()             #이 모든것이 끝나면 정상적인 경우 스택이 비어있어야 함

 

스택 후위 표기법 

후위표기법 : 연산자가 피연사자들의 뒤에 위치

• (A+B)*(C+D) →AB + CD+*
• A*B+C → AB*C+
• A+B*C →ABC*+
• A+B+C →AB+C+ 
• (A+B)*C → AB+C*
• A*(B+C) →ABC+*
• (A+(B-C))*D → ABC-+D*
• A*(B-(C+D)) → ABCD +-*  
  • 피연산자는 그냥 적음
  • 연산들은 나오는 순서대로 스택에 넣되, 우선순위가 높은 연산(곱셈,나눗셈)이 먼저 나오고 뒤에 낮은 연산(덧셈,뺄셈)이 나올 경우 높은 연산은 pop으로 스택에서 꺼내어 지금까지 나온 피연산자들 뒤에 적고 이후 낮은 연산을 스택에 넣음. 동일한 우선순위의 연산일 경우엔 기존에 있던 애를 먼저 꺼내줌. 피연산자가 모두 적혀진 이후엔 차례대로 스택에서 연산자들을 꺼냄 
  • 괄호가 있는 경우, 여는 괄호는 스택에 push, 닫는 괄호를 만나면 여는 괄호가 나올 때 까지 pop
  • 괄호가 뒤에 있을 경우, 연산자를 만났을 때 여는 괄호너머까지 pop하지 않도록 여는 괄호의 우선순위는 가장 낮게 설정 ㅇ

알고리즘 설계 

• 중위 표현식을 왼쪽부터 한글자씩 읽어서
  • 피연산자면 그냥 출력
  • ( 이면 스택에 push
  • ) 이면 (이 나올 때 까지 스택에서 pop출력 
  • 연산자이면 스택에서 이보다 높거나 같은 우선순위를 pop,출력 
    • 지금 만난 연산은 스택에 push 
  • 수식 끝에서 스택에 남아있는 연산자는 모두 Pop, 출력 
    • while not opStack.isEmpty(): -> 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):
    opStack = ArrayStack()
    answer = ''
    
    for i in S:
        if i.isalpha() :
            answer += i 
        elif i == '(':
            opStack.push(i)
        elif i == ')':
            while not opStack.isEmpty():
                op = opStack.pop()
                if op == '(':
                    break
                else :
                    answer += op 
        else :
            if not opStack.isEmpty():
                while not opStack.isEmpty():
                    if prec[opStack.peek()] >= prec[i]:
                        answer += opStack.pop()
                    else:
                        break
                opStack.push(i)
            else :
                opStack.push(i)
    while not opStack.isEmpty():
        answer += opStack.pop()
                
    return answer

 

스택 후위 계산법 

후위 계산법 

• 왼쪽부터 차례대로 읽어들이면서 피연산자가 나타나면 스택에 넣음
• 연산자가 나타나면 스택에 들어있는 피연산자 두개를 꺼내서 연산 적용 후 그 결과를 스택에 push 

알고리즘 설계

• 왼쪽부터 한글자씩 읽기
• 피연산자일 경우 스택에 push
• 연산자를 만날 경우 스택에서 두개의 연산 차례대로 pop (이때 2번째로 나온 것이 앞으로 나와야 함) 
• 피연산자와 연산자 계산
• 계산 결과 스택에 push
• 수식의 끝에 도달하면 스택에서 pop -> result 

#문자열로 들어온 표현식을 수식으로 만들기 
def splitTokens(exprStr): 
	tokens = []     #중위표현식 수식으로 표현해서 담기 
    val = 0
    valProcessing = False 
    
    for c in exprStr : 
    	if c in exprStr:
        	if c == ' ': continue 
            if c in '0123456789':           #숫자를 만나면 
            	val = val * 10 + int(c)     #지금마주친 값을 정수로 변환해서 더해라 
                valProcessing = True        
            else :                          #숫자가 아니라면(연산자, 괄호)
            	if valProcessing :           #지금까지 십진수 표현을 하고 있었다면
                	tokens.append(val)       #토큰에 현재까지의 변수를 넣어주고 0으로 하기 
                    val = 0
                valProcessing = False
                tokens.append(c)
       if valProcessing :                   #마지막에 10진수를 처리하고 있었다면 마지막 피연산자도 넣어주기 
       		tokens.append(val)
            
       return tokens
       
#중위표현식 후위표현식으로 변환        

def infixToPostfix(tokenList):
    prec = {
        '*': 3,
        '/': 3,
        '+': 2,
        '-': 2,
        '(': 1,
    }

    opStack = ArrayStack()
    postfixList = []
    
    for c in tokenList:
        if c == '(':
            opStack.push(c)
        elif c==')':
            while opStack.peek() != '(':            #닫힌괄호 이후 (가 나오지 않는 이상
                postfixList.append(opStack.pop())   #다음걸 리스트에 넣어라 
            opStack.pop()                           #그게 아니라면 pop해라 
        else :
            if c in prec:                                    #연산자라면 
                if opStack.isEmpty():                        #스택이 빈 경우 스택에넣어라 
                    opStack.push(c)
                elif prec[opStack.peek()]>=prec[c]:          #스택 내 연산이 우선순위가 높으면
                    while not opStack.isEmpty():             #스택이 비지 않은 이상 
                        postfixList.append(opStack.pop())    #스택 내 연산을 리스트에 넣어라 
                    opStack.push(c)                          #스택이 비었다면 c를 스택에 넣자
                else:                                        #스택내 연산이 우선순위가 낮다면
                    opStack.push(c)                          #스택에 c를 넣자 
            else :                                           #연산자가 아니라면 리스트에넣자 
                postfixList.append(c)
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
    
    return postfixList


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


def solution(expr):
    tokens = splitTokens(expr)
    postfix = infixToPostfix(tokens)
    val = postfixEval(postfix)
    return val