1. Stack 구현
1) 스택에서 발생하는 오류
- stack underflow : 비어있는 스택에 데이터를 꺼내려고 할 때
- stack overflow : 꽉 찬 스택에 데이터를 추가하려고 할 때
2) 스택의 추상적 자료구조 구현
- 배열 : 파이썬 리스트와 메서드 이용
- 연결리스트 : 양방향 연결 리스트 이용
3) 연산 정의
size() : 스택에 들어있는 데이터 원소 수
isEmpty() : 스택이 비어 있는지 여부
push(x) : 스택에 x를 추가
pop() : 스택 맨 위(top)에 저장된 데이터를 반환 후 제거
peek() : 스택 맨 위(top)에 저장된 데이터 반환
4) Array로 Stack 구현
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): # 스택의 top에 있는 원소 반환
return self.data[-1] 5) Doubly LinkedList로 Stack 구현
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) # 맨 뒤에 삽입
def pop(self):
return self.data.popAt(self.size()) # 맨 뒤 노드 삭제 후 리턴
def peek(self):
return self.data.getAt(self.size()).data # 맨 뒤 노드 리턴6) 수식의 괄호 유효성 검사
from arrayStack import ArrayStack
def solution(expr): # 수식 괄호 유효성 검사
match = {
')': '(',
'}': '{',
']': '['
}
S = ArrayStack()
for c in expr: # 수식을 왼쪽부터 한 글자씩 읽음
if c in '({[': # 여는 괄호를 만나면 스택에 push
S.push(c)
elif c in match: # 닫는 괄호를 만나면
if S.isEmpty(): # 스택이 비어 있으면 올바르지 않은 수식
return False
else:
t = S.pop() # 스택에서 pop
if t != match[c]: # 쌍을 이루는 여는 괄호인지 검사
return False
return S.isEmpty() # 끝까지 검사한 후 스택이 비어 있어야 올바른 수식
# 올바른 수식 (print : True)
print(solution("(A+B)"))
print(solution("{(A+B)*C}"))
print(solution("[(A+B)*(C-D)]"))
# 올바르지 않은 수식 (print : False)
print(solution("(A+B"))
print(solution("A+B)"))
print(solution("{A*(B+C})"))
print(solution("[(A+B)*(A-B)}"))2. 수식의 후위 표기법(Postfix)
중위 : (A + (B - C)) x D
= 후위 : A B C - + D x
중위 : A x (B - (C + D))
= 후위 : A B C D + - x
prec = {
'*': 3, '/': 3,
'+': 2, '-': 2,
'(': 1
}
def solution(S):
answer = ''
opStack = ArrayStack()
for s in S: # 중위 표현식을 왼쪽부터 한 글자씩 읽음
if s == '(': # 여는 괄호이면 stack에 push
opStack.push(s)
elif s == ')': # 닫는 괄호이면
while True: # 여는 괄호가 나올 때까지 스택에서 pop, 출력
v = opStack.pop()
if v == '(':
break
answer += v
elif s not in prec: # 피연산자이면 그냥 출력
answer += s
else: # 연산자이면
if opStack.isEmpty(): # 스택이 비어 있다면 해당 연산자를 스택에 바로 push
opStack.push(s)
else: # 스택이 비어 있지 않다면 연산자 우선 순위 비교
while not opStack.isEmpty():
v = opStack.peek() # 스택 맨 위에 있는 값을 가져옴
if prec[v] >= prec[s]: # 해당 연산자보다 높거나 같은 우선순위를 가진 것들이라면 pop, 출력
v2 = opStack.pop()
answer += v2
else:
break # 우선순위가 더 낮다면 반복 비교문 종료
opStack.push(s) # 해당 연산자를 스택에 push
while not opStack.isEmpty(): # stack에 남아 있는 연산자를 모두 pop, 출력
v = opStack.pop()
answer += v
return answer
print(solution("A*B+C")) # AB*C+
print(solution("(A+B)*(C+D)")) # AB+CD+*
print(solution("A+B*C")) # ABC*+
print(solution("A+B+C")) # AB+C+
print(solution("(A+B)*C")) # AB+C*
print(solution("A*(B+C)")) # ABC+*3. 후위 표기 수식 계산
- 후위 표현식을 왼쪽부터 한 글자씩 읽어서
- 피연산자이면 스택에 push
- 연산자를 만나면 스택에서 pop -> (1), pop -> (2)
(2) 연산 (1)을 계산하고 결과를 스택에 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]
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 True:
v = opStack.pop()
if v == '(':
break
postfixList.append(v)
else:
if opStack.isEmpty():
opStack.push(token)
else:
while not opStack.isEmpty():
v = opStack.peek()
if prec[v] >= prec[token]:
v1 = opStack.pop()
postfixList.append(v1)
else:
break
opStack.push(token)
while not opStack.isEmpty():
v = opStack.pop()
postfixList.append(v)
return postfixList
def postfixEval(tokenList): # 후위 표기 수식 계산
valStack = ArrayStack()
for token in tokenList: # 후위 표현식을 왼쪽부터 한 글자씩 읽음
if type(token) is int: # 피연산자이면 stack에 push
valStack.push(token)
elif token == '*': # 연산자이면
v1 = valStack.pop() # pop (1)
v2 = valStack.pop() # pop (2)
valStack.push(v2 * v1) # (2) 연산 (1) 계산 결과를 push
elif token == '/':
v1 = valStack.pop()
v2 = valStack.pop()
valStack.push(v2 / v1)
elif token == '+':
v1 = valStack.pop()
v2 = valStack.pop()
valStack.push(v2 + v1)
elif token == '-':
v1 = valStack.pop()
v2 = valStack.pop()
valStack.push(v2 - v1)
return valStack.pop() # 수식의 끝에 도달하면 stack에서 pop => 최종 연산 결과
def solution(expr):
tokens = splitTokens(expr)
postfix = infixToPostfix(tokens)
val = postfixEval(postfix)
return val
print(solution("5 + 3")) # 8
print(solution("(1 + 2) * (3 + 4)")) # 21
print(solution("7 * (9 - (3+2))")) # 28
Backend development