[백준/Python3] 1918 후위 표기식

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

---

풀이

지난 번에 풀었던 후위 표기식2와 달리 이번에는 중위 표기식에서 후위 표기식으로 바꾸는 문제다. 단, 이번에도 마찬가지로 자료구조 중 스택을 사용한다. 이 문제를 풀 때 가장 중요한 점은 연산자의 우선순위인데 잘 알다시피 ()안의 연산이 우선이고, 그 다음은 *,/ 마지막으로는 +,- 순이다.

기본적으로 모든 알파벳은 순서대로 정답에 나올 것이고 중요한 것은 연산자의 위치인데 연산자는 피연산자들 바로 뒤에 나와야하므로 연산자들은 기본적으로 스택에 집어넣는다. 이후에 다른 연산자가 나오면 앞서 나온 연산자의 피연산자가 나왔다는 의미이므로 스택에 들어있던 연산자를 꺼낸다.

여기서 괄호안에 있는 연산자는 우선적으로 계산해야하므로 ')'가 나왔을 경우 '('가 나올 때 까지 모든 연산자를 꺼내야한다.

중위 연산자 문장의 탐색을 완료했으면 스택에 연산자가 남아 있을 수 있으므로 스택이 빌 때까지 pop한다.

코드

infix = list(input())

operator = list()
ans = ''

for i in infix :
    if i.isalpha():
        ans += i
    elif i == '(':
        operator.append(i)
    elif i == '*' or i == '/':
        while operator and (operator[-1] == '*' or operator[-1] == '/'):
            ans += operator.pop()
        operator.append(i)
    elif i == '+' or i == '-':
        while operator and operator[-1] != '(':
            ans += operator.pop()
        operator.append(i)
    elif i == ')':
        while operator and operator[-1] != '(':
            ans += operator.pop()
        operator.pop() ## ( 반환

while operator:
    ans += operator.pop()

print(ans)