후위 표기식 만들기

생성일: 2022년 1월 24일 오후 5:23

코드

# 후위표기식 만들기
import sys
sys.stdin = open("input.txt", "rt")
s = input()
stack = []
res = ''

for x in s:
    if x.isdecimal():
        res += x
    else:
        if x == '(':
            stack.append(x)
        elif x == '*' or x == '/':
            while stack and (stack[-1] == '*' or stack[-1] == '/'):
                res += stack.pop()
            stack.append(x)
        elif x == '+' or x == '-':
            while stack and stack[-1] != '(':
                res += stack.pop()
            stack.append(x)
        elif x == ')':
            while stack and stack[-1] != '(':
                res += stack.pop()
            stack.pop() # '(' 를 스택에서 제거

while stack:
    res += stack.pop()

print(res)

• 아이디어
  • res 문자열에 숫자는 곧바로 추가하고 연산자는 stack에 넣는다.
  • 해당 연산자보다 연산 우선 순위가 높거나 같은 연산자들이 stack에 있다면 stack에서 빼고 res 에 추가한다.
  • ‘)’ 를 만났을 때에는 stack에서 ‘(’ 전까지의 연산자를 pop하여 res에 추가한다.
  • stack에 남아있는 연산자를 res에 더해준다.