[Python] 백준 / gold / 1918 : 후위 표기식

문제 링크 : https://www.acmicpc.net/problem/1918

스택 자료구조를 잘 사용해야 됐던 문제다. 스택에 수식들을 쌓아가면서 어느 타이밍에 어느 지점까지 pop 할지 잘 생각해야 된다. 4시간 걸려 문제를 풀고 느낀건데, 고려할 케이스가 좀 많아서, 후위수식은 만드는게 푸는 것보다 훨씬 까다롭다. 당연한건가.. 이 문제를 한번 더 풀어보라해도 1시간 안에 풀 수 있을지는 장담 못할 거 같다. 그냥 덕분에 뇌 근육 4시간동안 펌핑시켰다고 좋게 생각해야겠다.

stack 에서 pop 할때는 비어있지는 않은지 체크하는 것도 까먹지말것.

파이썬 코드

from collections import defaultdict
import sys
formula = list(sys.stdin.readline().strip())

alphabetStack = []
operatorStack = []


def isNowStronger(now, t):
    operator = ['?', '(', '+', '-', '*', '/']
    scoreNow = operator.index(now) // 2
    scoreTop = operator.index(t) // 2
    return scoreNow > scoreTop


for x in formula:
    if x.isalpha():
        alphabetStack.append(x)
    else:
        if not operatorStack:
            operatorStack.append(x)
        else:
            if x == '(':
                operatorStack.append(x)
            elif x == ')':
                while operatorStack[-1] != '(':
                    top = operatorStack.pop()
                    one = alphabetStack.pop()
                    two = alphabetStack.pop()
                    alphabetStack.append(two + one + top)

                operatorStack.pop()
            else:
                if isNowStronger(x, operatorStack[-1]):
                    operatorStack.append(x)
                else:
                    while operatorStack and not isNowStronger(x, operatorStack[-1]):
                        top = operatorStack.pop()
                        one = alphabetStack.pop()
                        two = alphabetStack.pop()
                        alphabetStack.append(two + one + top)
                    operatorStack.append(x)

while operatorStack:
    nowOperator = operatorStack.pop()
    one = alphabetStack.pop()
    two = alphabetStack.pop()
    alphabetStack.append(two + one + nowOperator)

print(alphabetStack[0])