Baekjoon 1918. 후위 표기식 / Python

알고리즘 설명

1. 피연산자는 출력 문자열에 바로 추가합니다.
2. 연산자는 스택에 저장하지만, 우선순위를 고려하여 스택에서 적절한 시점에 연산자를 꺼내어 출력 문자열에 추가합니다.
3. 괄호는 특별하게 처리합니다:
   • 여는 괄호 (는 스택에 무조건 추가합니다.
   • 닫는 괄호 )는 여는 괄호 (가 나올 때까지 스택의 연산자를 모두 출력 문자열에 추가합니다.

우선순위

• 괄호 (, )는 특별한 처리
• 곱셈 *와 나눗셈 /는 높은 우선순위
• 덧셈 +와 뺄셈 -는 낮은 우선순위

inlst = input()

# 결과를 저장할 리스트
ans = ''

# 연산자를 저장할 스택
lst = []

# 주어진 수식을 순회하면서 후위 표기식으로 변환
for i in inlst:
    if i == '(':
        # 여는 괄호는 무조건 스택에 넣기
        lst.append(i)
    elif i == ')':
        # 닫는 괄호가 나오면 여는 괄호가 나올 때까지 스택에서 pop
        while lst and lst[-1] != '(':
            ans += lst.pop()
        # 여는 괄호 '(' 제거
        lst.pop()
    elif i == '*' or i == '/':
        # '*'와 '/'는 높은 우선순위
        while lst and (lst[-1] == '*' or lst[-1] == '/'):
            ans += lst.pop()
        lst.append(i)
    elif i == '+' or i == '-':
        # '+'와 '-'는 낮은 우선순위
        while lst and lst[-1] != '(':
            ans += lst.pop()
        lst.append(i)
    else:
        # 피연산자는 바로 출력
        ans += i

# 스택에 남아있는 모든 연산자를 출력
while lst:
    ans += lst.pop()


print(ans)