1918. 후위표기식

역시 골드는 어렵구나

 

스택을 사용한 문제이며, 이 문제에서 고려해야 하는 것들은 이렇다.

1. 피연산자(문자)는 무조건 바로 집어넣는다.

2. 연산자는 스택에 넣는데, 이 때 우선순위가 높은 연산자는 무조건 상위에 있어야 한다. (그래야 먼저 뽑아서 정답에 집어넣을 수 있다.) 따라서 우선순위가 더 같거나 낮은 연산자를 만나면 그것보다 높은 연산자들은 모두 뽑아져야 한다. 

- 여기서 우선순위가 같은 연산자를 만날 때도 pop을 해야하는 이유는, 우선순위가 같더라도 새로운 연산자가 더 뒤에 나와야 하기 때문으로, 즉 우선순위가 같아도 이전의 연산자들이 먼저 뽑아져야 하는 것이다. 

3. 위와 같은 작업을 위해 괄호의 우선순위는 가장 낮아야 한다. (그래야 위에 다른 연산자를 쌓을 수 있다.)

이 때, ')' 닫는 괄호를 만나면 '(' 까지의 연산자를 모두 뽑아낸다.

 

import sys
input = sys.stdin.readline

def make_formula(arr) :
    priority = {'*' : 1, '/' : 1, '+' : 2, '-' : 2, '(' : 3, ')' : 3}
    symbol = []
    ans = []
    for c in arr :
        if c not in priority :
            ans.append(c)
        elif c == '(' :
            symbol.append(c)
        elif c == ')' :
            while symbol and symbol[-1] != '(' :
                ans.append(symbol.pop())
            symbol.pop()
        else : 
            while symbol and priority[c] >= priority[symbol[-1]] :
                ans.append(symbol.pop())
            symbol.append(c)
    while symbol :
        ans.append(symbol.pop())
    return ans

formula = input().rstrip()
print("".join(make_formula(formula)))

우선순위를 만들어야 한다는 생각을 하기가 참 쉽지 않다.