[백준] 1918 후위 표기식 python

www.acmicpc.net/problem/1918

1918번: 후위 표기식

import sys; input = sys.stdin.readline
ans = ''
s = []
for ch in input().rstrip():
    if ch == '+' or ch == '-':
        while s:
            if s[-1] == '(':
                break
            ans += s.pop()
        s.append(ch)
    elif ch == '*' or ch == '/':
        while s:
            if s[-1] == '(' or s[-1] == '+' or s[-1] == '-':
                break
            ans += s.pop()
        s.append(ch)
    elif  ch == '(':
        s.append(ch)
    elif ch == ')':
        while s:
            tmp = s.pop()
            if tmp == '(':
                break
            ans += tmp
    else:
        ans += ch
else:
    while s:
        ans += s.pop()
print(ans)

스택을 활용하여 풀면된다

후위표기로 바꿀때 연산자끼리의 우선순위를 생각하면 되는데,

stack의 맨 윗부분이 현재의 연산자보다 우선순위가 높은 경우에 빼서 결과에 넣어주면된다.

이때 연산자끼리의 우선순위는 스택 내부의 괄호 < 덧셈, 뺄셈 기호 < 곱하기, 나누기 기호 < 스택 외부의 괄호 와 같이 나타낼수 있다.