[백준/1918/파이썬] 후위 표기식(postfix)

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

조건

• 중위 표기식을 후위 표기식으로 바꾸세요!
• -A+B와 같이, - 가 가장 앞에 오거나, AB와 같이 *가 생략되는 등의 수식은 주어지지 않음.
• 표기식은 +,-,*,/,(,)로만 이루어져 있으며, 길이는 100을 넘지 않음.

입력

• IN: A*(B+C) Out: ABC+*
• IN : A+BC Out: ABC+

SOl)

일단, 후위 표기식은 진짜 Stack의 스테디 셀러 같은 느낌이라, Stack 사용 예제의 바이블이라..

스택을 사용해봅시다.

스택에는 연산자만 담을거임.

• string.isalpha()를 이용해서, 알파뱃이면 postfix에 바로 추가할거임.
• 괄호가 있으면, 괄호를 먼저 처리해야하니까, 괄호를 먼저 검사해줄거임.
• '(' 괄호면, 일단 stk에 쌓고, ')' 들어오면, 비어있지 않고, Stk의 탑이 '('일때까지, 계속 pop 해줘야함.
• 연산자의 우선순위도 생각해줘야함.
• stack에 들어갈 친구가 stack의 Top보다 우선순위가 더 높다면, stack에 쌓고, stack에 들어갈 친구가 stack의 Top보다 우선순위가 작거나 같다면,스택에서 pop 해줘야함.(빌때까지)

import sys
input= sys.stdin.readline
infix = list(input())
postfix=''
stk=[]
# stk[-1] = Top 
#"(,)": 0 순위 "*,/" :1 순위   "+,-" : 2순위
# 부등호를 써야하므로, *,/ : 2 , + , - : 1 
def priority(a):
	if a =="*" or a=="/":
		return 2
	elif a=="+" or a=="-":
		return 1
	
for x in infix:
	if x.isalpha():
		postfix+=x
		continue
	if x =='(':
		stk.append(x)
	elif x==')':
		while True:
			if stk and stk[-1] !='(':
				#비어있지 않고, stk[-1]이 '('가 아닌 연산자라면, pop해서 result에 저장!
				postfix+=stk.pop()
			else:
				stk.pop()
				#stk에 '('가 남아있을 수 있으니, pop 해줘야함.
				break;
		else: # (, )가 아닌 연산자일 떄, 
			while True:
				if stack and (priority(stack[-1]) >= priority(x):
					# 스택이 비지 않고(연산자가 1개밖에 없는경우)
					# x가 우선순위가 낮으면, stk에 쌓여있는 연산이 먼저 진행 
					# x와 우선순위가 같으면, stk에 쌓여있는 연산이 먼저 들어온거니까, 먼저 진행
					postfix+=stk.pop()
				else:
						stk.append(x)
					# x가 우선순위가 높다면, stk에 저장.
						break;
# 식을 전체적으로 다 봤는데, 괄호도 없고, 우선순위에 맞게 스택에 쌓여있다면
# stack에서 빼주기면 하면 됨.
while stk:
	postfix+= stack.pop()

print(postfix)