알고리즘/백준
[백준 / Python] 1918번 후위 표기식 | 초코더
cloud_nice
2020. 1. 30. 15:02
https://www.acmicpc.net/problem/1918
1918번: 후위 표기식
첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다.
www.acmicpc.net
접근법
피연산자를 만나는 경우는 바로 출력해주었습니다.
연산자의 우선순위를 지정해주는 것이 핵심이었습니다. 스택에 들어있는 연산자의 우선순위가 비교하려는 연산자의 우선순위보다 같거나 높은경우가 있으면 모두 pop()해주고난후 비교하려는 연산자를 마지막에 추가해줍니다.
나의 풀이
import sys
str=sys.stdin.readline().strip()
stack=[]
prior={
'*':2,
'/':2,
'+':1,
'-':1,
'(':0
}
for ch in '('+str+')':
if ch.isupper():
print(ch,end='')
elif ch=='(':
stack.append(ch)
elif ch==')':
while True:
o=stack.pop()
if o == '(':
break
print(o,end='')
else:
while stack[-1] != '(' and prior[ch] <= prior[stack[-1]]:
print(stack.pop(),end='')
stack.append(ch)