백준 1918 후위 표기식(python)

문제

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

---

스택에 좀 더 익숙해지기 위해 푼 문제, 생각보다 구현이 까다로워서 좀 걸린 것 같다. 조건에 맞게 경우를 좀 나눠 주어야 한다.

• 먼저 알파벳이나 여는 괄호 라면 그대로 스택에 넣어준다.
• 닫는 괄호일 때는 스택에서 여는 괄호가 나오기 전까지 pop 시켜주며 출력해준다.
• 연산자는 우선 순위에 따라 나눠 주는데, 우선순위가 높은 '*'와 '/'가 스택의 top 값에 있을 때 들어오는 값이 같거나 낮다면 이미 들어 가진 스택 값을 pop 해주는데, 기존에 우선순위가 높은 값이 남지 않게 해주는 과정이다. 그 뒤 스택에 값을 넣어 준다.
• 최종적으로 스택에 남은 값을 처리해 준다. 

---

소스코드 

import sys
input = sys.stdin.readline


str = input().rstrip()
st = []

for s in str:  # A-Z 까지 해당되는 알파벳이면 그대로 출력 해준다.
    if 0 <= ord(s)-ord('A') <= ord('Z'):
        print(s, end='')

    elif s == '(':
        st.append(s)

    elif s == ')':
        while st and st[-1] != '(':
            top = st.pop()
            print(top, end="")
        st.pop()  # 마지막 '(' 값 pop 처리

    # 스택의 top 값이 현재 순회중인 값 보다 우선 순위가 높거나 같다면 pop 해서 출력해준다
    elif s == '/' or s == '*':
        while st and (st[-1] == '/' or st[-1] == '*'):
            top = st.pop()
            print(top, end="")
        st.append(s)
    elif s == '+' or s == '-':
        while st and st[-1] != '(':
            top = st.pop()
            print(top, end="")
        st.append(s)

# 스택에 남은 값 처리
while st:
    top = st.pop()
    if top != '(':
        print(top, end="")