후입선출(LIFO : Last In First Out) : 나중에 들어온 것이 먼저 나감.
수식을 왼쪽부터 한 글자씩 읽음.
수식을 다 읽은 후, 스택이 비어있지 않다면 올바른 수식 X
후위표기법(postfix notation) : 연산자가 피연산자들의 뒤에 위치
ex) 중위표기법 : 2+3*4 -> 후위표기법 : 234*+
수식을 왼쪽부터 한 글자씩 읽는다.
수식을 다 읽은 후, 스택에 남아있는 연산자 모두 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):
answer = ''
opStack = ArrayStack()
for s in S:
# 피연산자인 경우 -> 출력
if s.isalpha():
answer += s
# 왼쪽 괄호 ( 인경우 -> push
elif s == '(':
opStack.push(s)
# 오른쪽 괄호 ) 인경우 -> (이 나올때까지 pop
elif s == ')':
while 1:
pop_s = opStack.pop()
if pop_s == '(':
break
answer += pop_s
# 연산자인 경우
else:
# 스택이 비어있지 않는 경우 -> 스택에 있는 연산자와 현재 연산자 비교
if not opStack.isEmpty():
peek_s = opStack.peek()
while prec[peek_s] >= prec[s]: # 스택 top 연산자 >= 현재 연산자
pop_s = opStack.pop()
answer += pop_s
try: # 위에서 pop하면서 스택이 비어 peek할때 오류가 발생할 수 있음. 이땐 while문 break하고 스택에 현재 연산자 push
peek_s = opStack.peek()
except:
break
opStack.push(s)
# 수식을 다 읽은 후에도 스택이 비어있지 않을 경우, 스택이 빌때까지 pop한다.
while not opStack.isEmpty():
pop_s = opStack.pop()
answer += pop_s
return answer