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

• Problem Link : https://www.acmicpc.net/problem/1918

문제

• 중위 표기식이 주어질 때 이를 후위 표기식으로 변환한다.
• 표기식은 + - * / ( ) 연산자와 영대문자 피연산자로만 구성된다.
• '-A'와 같이 마이너스가 가장 앞에 오거나 AB 같은 * 연산자가 생략되는 등의 수식은 주어지지 않는다.

입력

• 첫째 줄, 중위 표기식이 주어진다.

출력

• 후위 표기식을 출력한다.

전위, 중위, 후위 표기식에 대한 설명은 이 문서를 참고하자

풀이

중위 표기식을 후위 표기식으로 어떻게 변환하는지에 대해 잘 알아야만 간단하게 해결할 수 있는 문제이다. 원래는 중위 표기식의 연산자 우선순위에 따라 괄호를 친 후 연산자를 괄호 오른쪽으로 꺼내고 괄호만 지우는 방식으로 후위 표기식으로 바꾸는 방법이 가장 일반적이라고 하여 프로그램 알고리즘도 그러한 방향으로 구현하려 했으나, 1. 괄호를 추가하고, 2. 연산자를 옮기고,
3. 괄호를 지우는 방식이 번거롭고 코딩 분량도 많아져서 규칙을 찾아내서 간단하게 구현하고자 했다.

후위 표기식에서 중요한 점은 연산자 우선순위이다. 후위 표기식은 연산자의 우선순위에 따라 연산자의 위치가 변한다는 점을 꼭 인지해야한다.

연산자의 우선순위는 어떻게 결정될까?

1. 괄호 안에서부터 계산하는 것이 우선순위가 높다. 
2. 앞에서부터 계산하는 것이 우선순위가 더 높다.
3. 같은 우선순에 있는 연산자들은 **앞에서부터 계산**한다. 

문제의 예시를 보기로 들자면.

• A, B, C가 피연산자로 사용되는 부분에서 * + 가 순서대로 온 것을 알 수 있다. 먼저 피연산자들이 위치하고 그 뒤에 우선순위가 높은 연산자, 그 뒤에 우선순위가 낮은 연산자가 위치한다.
• D E 또한 피연산자 D E가 그대로 위치하고 /가 뒤에 위치한다.

이를 스택으로 한번 생각해보자. 이 때 중요한 점은 기존 후기 표기식을 풀 때는 피연산자를 스택에 넣었던 것과는 반대로 중위 표기식을 후기 표기식으로 바꿀 때는 연산자를 스택에 유지해야한다. 한번 문제의 식을 예로 들어 스택으로 후기 표기식으로 바꿔보자.

즉,

• 1. '('는 연산자이므로 스택에 push한다.
     
• 2. A는 단순 피연산자이므로 바로 정답 리스트에 추가한다.
     
• 3. +는 연산자이므로 스택에 넣는데 이 때 자신보다 높은 우선순위의 연산자가 있는지 확인한다.
     - 자신보다 우선순위가 높은 연산자가 있으면 연산을 진행해야하므로 pop을 해줘야 함
     
• 4. '('는 연산자이므로 스택에 push한다.
     
• 5. B는 피연산자이므로 정답에 추가한다.
     
• 6. * 연산자를 스택에 넣는데 이 때 자신보다 우선순위가 높은 연산자가 없으니 pop을 하지 않고 push만 진행한다.
     - '(' 연산자는 사칙연산보다 우선순위가 높다.
     
• 7. 피연산자 C를 정답에 추가
     
• 8. ')'가 들어왔으니 이제 괄호 안에 있는 연산이 가장 우선순위가 높다는 것을 의미하고 우선순위 가장 높은 연산을 pop해서 답에 push해준다.
     - 우선순위가 높은 연산자가 연산자들 중 가장 앞에 위치해야한다.
     - '('는 후기 표기식에는 표시하지 않기 때문에 단순히 pop만 해주고 push는 해주지 않는다.
     
• 9. 위 8번과 동일하게 그 다음 괄호안에 있는 연산들을 pop해주면서 그대로 정답에 push한다.
     - 이 때 사칙연산간의 우선순위를 따질 필요 없는 것이 추후에 * / 연산자가 들어오면 그 때 알아서 우선순위를 처리해주면서 집어넣기 때문에 그냥 pop해서 바로 push만 해주면 된다
     
• 10. '-'를 연산자 스택에 추가한다.
      
• 11. '('를 연산자 스택에 추가한다.
      
• 12. '\'를 연산자 스택에 추가한다.
      
• 13. D는 피연산자이므로 바로 정답에 추가한다.
      
• 14. '/'는 연산자 스택에 추가한다.
      - 위와 동일하게 '(' 연산자는 '/' 연산자보다 우선순위가 높으므로 pop 하지 않는다.
      
• 15. E는 피연산자이므로 정답에 추가한다.
      
• 16. ')'가 들어왔으니 이제 괄호 안에 있는 연산들을 pop 해서 정답에 push 한다.
      
• 17. 남은 연산자 스택에 있는 연산자들을 마지막으로 정답에 추가한다.
      - 우선순위가 제일 낮아서 남아있는 연산자들이다.
      

위와 같은 과정으로 우리가 원하는 후기 표기식을 얻을 수 있다.

위 과정의 규칙은 크게 두가지를 적용시켰다.

1. 피연산자의 경우에는 그냥 정답에 바로 추가
2. 연산자는 스택에 유지하면 들어오는 연산자보다 우선순위가 높은 연산자는 pop 해서 정답에 push 해준다.

위 두 가지 규칙을 적용시켜 중위 표기식을 한 바퀴 돌고나면 우리가 원하는 후기 표기식을 구할 수 있고 이를 코드로 구현하면 아래와 같다.

코드

import sys
from collections import deque

input = sys.stdin.readline

s = input().strip()

q = deque()

ans = []
for c in s:
    if c in ["+", "-", "*", "/", "(", ")"]:
        if c == ")": #괄호가 닫히면 괄호안에 있는 연산들 모두 pop
            while q[-1] != "(":
                ans.append(q.pop())
            q.pop()
        elif c in ["*", "/"]: 
        #곱셈, 나눗셈 연산의 경우
        #먼저 들어온 곱셈, 나눗셈이 우선순위 높으므로 앞에있는 곱셈, 나눗셈 연산자만 pop해준다.
            while q and q[-1] in ["*", "/"]:
                ans.append(q.pop())
            q.append(c)
        elif c in ["+", "-"]:
        #덧셈, 뺼셈 연산의 경우
        #먼저 들어온 모든 사칙연산자가 자신보다 우선순위가 높으므로 모든 사칙연산에 대해 pop해준다.
            while q and q[-1] in ["+", "-", "*", "/"]:
                ans.append(q.pop())
            q.append(c)
        else:
            q.append(c)
    else:
        ans.append(c)
while q:
    ans.append(q.pop())

print("".join(ans))