📌스택
자료(data element)를 보관할 수 있는 (선형) 구조
넣는(push) 곳과 꺼내는(pop) 곳이 같다.
후입선출(LIFO)인 선형 자료구조다.
스택에서 발생하는 오류
stack underflow : 비어있는데 pop할 때
stack overflow : 꽉 차 있는데 push할 때
✍스택의 추상적 자료구조 구현
-
배열을 이용하여 구현
파이썬 리스트와 메서드들을 이용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] -
연결리스트를 이용하여 구현
양방향 연결 리스트 이용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
- 연산의 정의
size() - 현재 스택에 들어 있는 데이터 원소의 수를 구함
isEmpty() - 현재 스택이 비어 있는지를 판단
push(x) - 데이터 원소 x를 스택에 추가
pop() - 스택의 맨 위에 저장된 데이터 원소를 제거하며 반환
peek() - 스택의 맨 위에 저장된 데이터 원소를 반환(제거X)
✍Stack 파이썬 라이브러리
from pythonds.basic.stack import Stack 해서 가져올 수 있음
✍스택의 응용 - 수식의 후위 표기법 (Postfix Notation)
-
중위 표기법 (infix notation)
(a+b)*(c+d) ->연산가자 피연산자들의 사이에 위치
-
후위 표기법 (postfix notation)
ab+cd+* -> 연산자가 피연산자들의 뒤에 위치위 예시는 같은 연산이다.
스택을 활용해 중위표현식을 후위표현식으로 만든다.
- 알고리즘의 설계
연산자의 우선순위 설정
prec = {
'*' : 3, '/' : 3,
'+' : 2. '-' : 2,
'(' : 1
}
여는 괄호(의 우선순위를 제일 낮게!
- 중위 표현식을 왼쪽부터 읽어서
- 피연산자이면 그냥 출력
- '('이면 스택에 push
- ')'이면 '('이 나올 때까지 스택에서 pop, 출력
- 연산자이면 스택에서 이보다 높거나 같은 우선순위 것들을 pop, 출력 그리고 이 연산자는 스택에 push
- 스택에 남아 있는 연산자는 모두 pop, 출력
! 스택의 맨 위에 있는 연산자와의 우선순위 비교 - peek()사용
스택에 남아 있는 연산자 모두 pop()하는 순환문 - while not opStack.isEmpty():
def solution(S):
opStack = ArrayStack()
answer = ''
for i in S:
if i not in prec and i != ')': #피연산자이면 answer에 출력
answer += i
continue
elif i == '(': #(면 일단 스택에 넣기
opStack.push(i)
continue
elif i in prec: #연산자이고
while opStack.size() > 0 and prec[opStack.peek()] >= prec[i]: #스택이 비어있지 않고 앞선 연산자가 현 연산자보다 우선될 때
# not opStack 했을 때는 "A*B+C가 ABC+*로 나왔었다. 차이점?
answer += opStack.pop() # 들어있는 연산자들을 모두 출력 (여러개 있을 수 있으니 반복문으로 다 빼줌)
opStack.push(i) #빼준 다음에 현 연산자를 넣어준다.
continue
while opStack.peek() != '(': # 스택에 (가 제일 위에 있지 않다면?
answer += opStack.pop() # (만 남을때까지 나머지 애들 출력
opStack.pop() # 남은 ( 지워버리기
while opStack.isEmpty() == False: # 스택이 빌 때까지
answer += opStack.pop() # 남은 애들 출력
return answer
스택을 활용해 후위표현식을 계산하기
문자열로 주어진 수식을 중위 표기법으로부터 후위 표기법으로 변환하고 (스택 이용), 이 결과 후위 표현식을 계산하는 (스택 이용) 코드
- 알고리즘의 설계
연산자의 우선순위 설정
prec = {
'*' : 3, '/' : 3,
'+' : 2. '-' : 2,
'(' : 1
}
여는 괄호(의 우선순위를 제일 낮게!
- 후위 표현식을 왼쪽부터 읽어서
- 피연산자이면 스택에 push
- 연산자를 만나면 스택에서 pop -> 1, 또 pop ->2. 2연산1을 계산하고 결과를 스택에 push (2가 더 먼저 들어간 피연산자라 2연산자1로 계산한다.)
- 위 과정을 반복하다 수식의 끝에 도달하면 하나의 값이 스택에 남는다
- 그것이 계산 결과이니 pop
def splitTokens(exprStr):
tokens = []
val = 0
valProcessing = False
for c in exprStr:
if c == ' ':
continue
if c in '0123456789':
val = val * 10 + int(c)
valProcessing = True
else:
if valProcessing:
tokens.append(val)
val = 0
valProcessing = False
tokens.append(c)
if valProcessing:
tokens.append(val)
return tokens
def infixToPostfix(tokenList):
prec = {
'*': 3,
'/': 3,
'+': 2,
'-': 2,
'(': 1,
}
opStack = ArrayStack()
postfixList = []
for token in tokenList:
if type(token) is int: #피연산자는 리스트에 넣기
postfixList.append(token)
elif token == '(':
opStack.push(token)
elif token == ')':
while opStack.peek() != '(':
postfixList.append(opStack.pop())
opStack.pop()
elif token in prec:
if opStack.size() > 0 and prec[opStack.peek()] >= prec[token]:
postfixList.append(opStack.pop())
opStack.push(token)
else:
postfixList.append(token)
while not opStack.isEmpty():
if opStack.peek() != '(':
postfixList.append(opStack.pop())
return postfixList
def postfixEval(tokenList):
valStack = ArrayStack()
for token in tokenList:
if type(token) is int:
valStack.push(token)
else:
f = valStack.pop()
s = valStack.pop()
if token == '*':
valStack.push(s * f)
elif token == '/':
valStack.push(s / f)
elif token == '+':
valStack.push(s + f)
elif token == '-':
valStack.push(s-f)
return valStack.pop()
def solution(expr):
tokens = splitTokens(expr)
postfix = infixToPostfix(tokens)
val = postfixEval(postfix)
return val