Problem Solving
[백준 BOJ - 1918 / 파이썬] 후위 표기식
Oh Seokjin
2022. 8. 28. 23:10
1918번: 후위 표기식
첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의
www.acmicpc.net
🔍 문제 분석
중위표기식을 후위표기식으로 변환하는 문제
❗ 해결 아이디어
우선순위가 낮은 연산자가 나올 때까지 stack에 저장한 후 pop
괄호는 따로 연산
✔️ 최종 풀이
import sys
operator = sys.stdin.readline().rstrip()
stack = []
answer = ""
for token in operator:
if 'A' <= token <= 'Z': # 피연산자면 바로 추가
answer += token
elif token == '(':
stack.append('(')
elif token == '*' or token == '/':
while stack and (stack[-1] == '*' or stack[-1] == '/'):
# *, /는우선순위가 같으므로 pop
answer += stack.pop()
stack.append(token)
elif token == '+' or token == '-':
# 가장 우선순위가 낮으므로 괄호 전까지 모두 pop
while stack and (stack[-1] !='('):
answer += stack.pop()
stack.append(token)
elif token == ')':
while stack and stack[-1] != '(': # 여는 괄호 나올때까지 pop
answer += stack.pop()
stack.pop() # 여는 괄호 지워줌
while stack:
answer += stack.pop()
print(answer)