Stack
후입 선출의 자료구조 (Last In First Out)
- 한쪽 끝에서만 자료를 삽입, 삭제가 가능하다.
- 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이다.
Stack 구현
-
pop()
스택에서 최근에 추가한 요소를 삭제하고, return 한다.
스택이 비어있다면 -1을 반환한다. -
empty()
스택의 길이가 0 이면 True를 반환하고, 길이가 1이상이면 False를 반환한다. -
push()
스택에 요소를 추가한다. -
size()
스택의 length를 return 한다. -
top()
스택에서 최근에 추가한 요소를 return한다.
스택이 비어있다면 -1을 return 한다.
Stack 코드
class Stack():
def __init__(self):
self.stack = []
self.length = 0
def ft_pop(self):
if self.length < 1:
return -1
else:
self.length -= 1
return self.stack.pop()
def ft_push(self, data):
self.stack.append(data)
self.length += 1
def ft_size(self):
return self.length
def ft_empty(self):
if self.length < 1:
return True
else:
return False
def ft_top(self):
if self.length < 1:
return -1
else:
return self.stack[self.length - 1]백준 1918 후위 표기식
- 중위 표기식 → 후위 표기식의 경우 연산자 우선 순위를 고려한 후, 피연산자는 그냥 출력해주면 된다.
def write(self):
while (self.ft_top() != -1):
print(self.ft_pop(), end = "")
def compare(top, N):
dic = {"*" : 2, "/" : 2, "+" : 1, "-" : 1, "(" : 3}
return dic[N] - dic[top]
expression = list(str(input()))
flag = 0
stack = Stack()
for i in range(len(expression)):
if expression[i].isalpha():
print(expression[i] , end = "")
elif expression[i] == ")":
while (stack.ft_top() != "("):
print(stack.ft_pop(), end = "")
stack.ft_pop()
elif stack.ft_empty():
stack.ft_push(expression[i])
elif expression[i] == '(':
stack.ft_push(expression[i])
elif compare(stack.ft_top(), expression[i]) > 0:
stack.ft_push(expression[i])
elif compare(stack.ft_top(), expression[i]) == 0:
print(stack.ft_pop(), end = "")
stack.ft_push(expression[i])
elif compare(stack.ft_top(), expression[i]) < 0:
while (stack.ft_empty() != True):
if (stack.ft_top() == "("):
break
print(stack.ft_pop(), end = "")
stack.ft_push(expression[i])
stack.write()-
알파벳이 들어온 경우 그냥 출력해준다.
-
“)”이 들어온 경우에 “(”이 나올 때까지 출력한다.
-
“(”이 들어온 경우 스택에 넣는다.
-
연산자의 우선 순위를 비교하여 결정한다.
-
입력 문자의 우선순위가 스택 맨 위에 있는 연산자의 우선순위보다 높은 경우
스택에 연산자를 넣는다. -
입력 문자의 우선순위가 스택 맨 위에 있는 연산자의 우선순위랑 같은 경우
스택 맨 위에 있는 연산자를 pop하고 입력 문자를 스택에 넣는다. -
입력 문자의 우선순위가 스택 맨 위에 있는 연산자의 우선순위보다 낮은 경우
스택이 빌 때까지, 스택 맨 위 연산자가 “(” 일 때까지 혹은 스택의 길이가 0이 될 때까지 pop 하여 출력한 후에 입력 문자를 스택에 넣는다.
-
