Stack
순차적 구조 중 하나인 Stack는 Last In First Out 정책을 따른다.
나중에 들어온 요소가 먼저 나가는 자료구조 형태이다.
책을 하나씩 쌓아 올린다고 생각하면 된다. 맨 밑의 책을 꺼내기 위해서는 위의 모든 책을 치우고나서 아래에 있는 책을 꺼낼 수 있다.
Stack 구조는 list와 같은 인덱스가 존재하지 않아서 중간에 데이터를 삭제하거나 추가하는 작업이 불가능하다.
오직 맨위의 top에서만 데이터의 추가, 삭제가 가능하다.
class Stack:
def __init__(self):
self.items = []
def push(self, val):
self.items.append(val)
def pop(self):
try:
return self.items.pop()
except IndexError:
print("Stack is Empty")
def top(self):
try:
return self.items[-1]
except IndexError:
print("Stack is Empty")
def __len__(self):
return len(self.items)
리스트를 이용한 Stack 클래스 구현이다.
스택의 push는 리스트의 append, pop은 리스트의 pop과 같다.
top은 가장 위에 있는 요소를 반환해주는 메서드이다.
모든 메서드의 경우 단순히 추가와 삭제만 하게 되므로 O(1)상수만큼의 시간복잡도가 발생한다.
괄호 맞추기
수학적 연산에서 ()는 짝을 이루어서 계산이된다. 열리는 (이 있으면 닫히는 ) 가 존재해야 한다.
두개가 짝을 맞추어서 되어있는지 확인 하는 코드를 Stack을 이용해서 구현할 수 있다.
lst = ["(", ")", "(", ")", "(", "(", ")", ")",")","("]
def is_couple(lst):
try:
stack = Stack() # 스택을 만든다.
for i in range(len(lst)):
# "(" stack에 추가해준다.
if lst[i] == "(":
stack.push(lst[i])
# ")" 라면 stack에서 빼준다.
elif lst[i] == ")":
stack.pop()
else:
continue
# "("가 남은 경우
# for문을 모두 완료 후 stack에 "("이 남아 있다면 짝이 맞지 않은 경우이므로 False를 반환한다.
if len(stack) > 0:
return False
else:
return True
# ")" 가 남은 경우
# for문을 돌때 pop을 해서 아무것도 없는 경우는 예외가 발생하게 된다.
# 이 경우는 ")"왔는데 앞에는 "(" 들어 가 있지 않는 경우리므로 역시 False를 반환한다.
except:
return False계산기코드 작성
계산기 코드를 작성하기 위한 절차
- infix형태 -> postfix형태로 변환한다.
- postfix형태를 계산한다.
infix -> postfix
모든 연산을 괄호로 묶는다. 그리고 자신의 연산의 닫히는 괄호 뒤로 연산자를 옮긴다.
숫자의 경우는 순서가 바뀌지 않는다.
1+2*3 => (1+(2*3)) => 123*+
(1+2)*3 => ((1+2)*3) => 12+3*
infix -> postfix를 구현하는 코드는 Stack과 List를 이용해서 작성한다.
Stack에는 연산자가 들어오게 된다. 들어있는 연산자는 다음 연산자가 자신의 우선순위와 비교에 큰지 작은지에 따라 Stack에 남아있을지 아니면 빠져나갈지를 결정하게 된다.
input = "1*2+(3-2)*4"
token_list = [i for i in input]
stack = Stack()
result_lst = []
def infix_to_postfix(input):
for token in token_list:
# "("의 경우 우선순위가 제일 낮으며, 무조건 push를 해준다.
if token == "(":
stack.push(token)
# ")"의 경우 stack안에 "(" 가 나오기 전까지 쌓여 있는 모든 것을 pop해서 result_list에 담는다.
elif token == ")":
for i in range(len(stack)):
if stack.top() == "(":
stack.pop()
break
else:
result_lst.append(stack.pop())
# "+","-"인 경우는 자신과 같은 우선순위의 "+","-"가 오면 빼내고, 들어간다.
# 우선순위가 높은 "*", "/"가 들어 있다면 다빼고 들어간다.
elif token == "+" or token =="-":
if len(stack) == 0:
stack.push(token)
else:
for i in range(len(stack)):
if stack.top() == "*" or stack.top() == "/":
result_lst.append(stack.pop())
elif stack.top() == "+" or stack.top() == "-":
result_lst.append(stack.pop())
elif stack.top() == "(":
break
stack.push(token)
# "*" 와 "/" 는 같은 stack에 들어있는 연산자가 같은 경우는 빼고 들어간다.
# 우선순위가 낮은 "+", "-"인 경우는 stack에 들어간다.
elif token == "*" or token == "/":
if len(stack) == 0:
stack.push(token)
else:
for i in range(len(stack)):
if stack.top() == "+" or stack.top() == "-" :
continue
elif stack.top() == "*" or stack.top() == "/":
result_lst.append(stack.pop())
elif stack.top() =="(":
break
stack.push(token)
# 숫자가 오는 경우에 해당한다.
else:
result_lst.append(token)
# 마지막으로 stack안에 연산자가 남아 있다면 모두 pop해서 result_lst에 담아준다.
if len(stack) > 0:
for i in range(len(stack)):
result_lst.append(stack.pop())
return result_lstpostfix를 구현하기 위해서는 Stack에 남아있는 연산자가 현재 자신보다 우선순위가 높은지, 낮은지를 보고 결정해서 pop()하고 push()할지 아니면 그대로 push()할지를 결정해야 한다.
postfix형식을 이용해서 실제 계산하는 코드
반복문을 돌면서 확인해나가며 숫자가 나오면 stack에 추가하고, 연산자가 나오면 stack에서 2개 pop() 계산을 하고, 다시 push()해준다.
그리고 stack에 남아있는 결과를 pop()하면 계산기 코드가 완료된다.
# 문자열에 해당하는 연산자를 실제 연산자로서 기능하기 위해서 작성한 코드이다.
import operator
ops = { "+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.floordiv }
stack = Stack()
for token in token_list:
if token in ["+","-","*","/"]:
a = int(stack.pop())
b = int(stack.pop())
result = ops[token](b,a)
stack.push(result)
else:
stack.push(token)
print(stack.pop())
참고
https://www.youtube.com/watch?v=OzFXiukhv8o&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=8
https://www.youtube.com/watch?v=G9ujrSGEB4A&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=9
https://www.youtube.com/watch?v=MYk4autDAJ0&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=10
