[Python] 백준1918 후위 표기식

04 Jul 2023 in Study on Algorithm

백준1918 후위 표기식 링크

문제

예제 입력

---

코드

from collections import deque
arr = list(input().strip())

# 후위 표기식 
ans = []
st = deque()
for a in arr:
    if a == "(" :
        st.append(a)

    elif a == ")":
        while st and st[-1] != "(":
            ans.append(st.pop())
        st.pop()

    elif a in ["*", "/"]:
        if len(st) != 0:
            while st and st[-1] in ["*", "/"]:
                ans.append(st.pop())
        st.append(a)

    elif a in ["+", "-"]:
        if len(st) != 0:
            while st and st[-1] in ["+", "-", "*", "/"]:
                ans.append(st.pop())
        st.append(a)

    else:
        ans.append(a)
while st:
    ans.append(st.pop())

print("".join(ans))

# 일반적으로 곱셈/나눗셈을 먼저하기 때문에 후위 표기식로도 먼저 계산되어야함.
# 그래서 스택에서 + - 보다 순위를 낮게하여 빨리 계산함.
# A - B 가 있을때는 - 입장에서는 왼쪽과 오른쪽을 그대로 연산하면되지만
# A * B - C 가 있을때는 - 입장에서 왼쪽이(A * B) 먼저 연산이 되어있어야 할 수 있기때문에
# 스택에 *가 있으면 -는 자신을 기준으로 왼쪽을 먼저 계산하고 대기합니다.
# 예외 : ( )
# 1순위 : + -
# 2순위 : * /
# 앞에 자신보다 낮거나 같은 순위이면 스택을 비움
# 높으면 스택에 저장
# 예외가 있을시 무조건 저장

# 여는 괄호
# 여는 괄호를 스택에 append한다.

# 닫는 괄호
# 여는 괄호를 만날때까지, 스택에 pop하여 결과에 append한다.
# 만난 여는 괄호는 버린다.

# * /
# 스택이 비어있을 경우, 스택에 append한다.
# 스택이 비어있지 않을 경우, 스택의 top이 * / 아닐때까지(즉, 괄호와 1순위까지) pop하여 결과에 append한다.
# 그리고 스택에 * / 를 append한다.

# + -
# 스택이 비어있을 경우, 스택에 append한다.
# 스택이 비어있지 않을 경우, 스택의 top이 * / + - 아닐때까지(즉, 괄호일때까지) pop하여 결과에 append한다.
# 그리고 스택에 + - 를 append한다.

# 그 외
# 결과에 append한다.

설명

파이썬을 통해서 사용자로부터 입력받아 스택을 사용하여 후위 표기식를 구현했습니다.

---

결과