후위 표기식

Stack을 활용해 푸는 문제이다.

두개의 리스트를 생성한다.

  • ABC리스트에는 알파벳들을 저장한다.(후위 표기법으로 처리하는 과정에서 연산자도 포함되게 된다.)
  • OP에는 operator를 비롯한 알파벳 외의 수식들을 저장한다.

이 문제를 풀며 주의해야 할 점은 +, - 와 *, /의 우선순위를 잘 생각해봐야 한다는 것이다.

Plus

같은 우선순위라도 앞에 있는 연산자를 후위 표기식에서도 먼저 써주어야 한다. 따라서, E*F*G의 경우 EFG*이 아니라 EFG*가 정답이다! 추가 Test Case

아마 문제를 못 풀고 있는 대다수의 사람들은 이 부분에서 틀렸을거라 예상된다. 나도 후위 표기법으로 바꾸는 방법 까지는 바로 접근할 수 있었지만, 이 부분을 해결하지 못해 오랫동안 고민해야 했다…

중위 표기법은 연산자 사이의 우선순위와 괄호를 이용해서 해결하지만, 후위 표기법에는 이러한 법칙이 없기 때문에 우선순위가 동일한 연산자의 경우에는 앞에 있는 연산자를 더 앞서게 표기해주어야 한다고 한다. - 백준 게시판 참고

CODE

from collections import deque
import sys
read = sys.stdin.readline

infix = list(read().strip())

ABC = list()  # 알파벳 저장
OP = list()   # 알파벳 외의 수식 저장
# 각 수식들의 우선순위가 다르기 때문에 나누어 생각해줘야 한다.
for i in infix:
    # OP가 비거나 ( 가 등장하기 전까지 수식들을 모두 ABC로 옮긴 이후
    # '+'혹은 '-'를 OP에 추가한다.
    if i == '+' or i == '-':
        while OP and OP[-1] != '(':
            ABC.append(OP.pop())
        OP.append(i)
    # 자신과 우선순위가 동일한 연산자들을 모두 ABC로 옮긴 이후
    # 추가해준다.
    elif i == '*' or i == '/':
        while OP and (OP[-1] == '*' or OP[-1] == '/'):
            ABC.append(OP.pop())
        OP.append(i)

    elif i == '(':
        OP.append(i)
    #'('열리는 괄호가 나타나기 전까지 모든 연산자를 ABC로 옮긴다.
    elif i == ')':
        while OP and OP[-1] != '(':
            ABC.append(OP.pop())
        #옮긴 이후 열리는 괄호도 제거해준다.
        OP.pop()
    #나머지 알파벳에 대해서는 바로 ABC로 추가한다.
    else:
        ABC.append(i)
#아직 OP에 남아있는 연산자가 있으면 ABC로 옮긴다.
while OP:
    ABC.append(OP.pop())

for i in ABC:
    print(i, end='')


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]