[백준 1918번] 후위 표기식 (Python3)

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

eq = input().strip()

N = len(eq)

stack = deque()
symbol = deque()

co = deque()

def postfix(n):
  global x
  if n == N:
    if symbol:
      stack.append(symbol.pop())
    return
  if eq[n] == "(":
    symbol.append("(")
    postfix(n+1)
    postfix(co.pop())
    return
  elif eq[n] == ")":
    s = symbol.pop()
    if s != "(":
      stack.append(s)
      symbol.pop()
    if symbol:
      if symbol[-1] == "*" or symbol[-1] == "/":
        stack.append(symbol.pop())
    co.append(n+1)
    return
  elif eq[n]=="+" or eq[n]=="-":
    if symbol:
      if symbol[-1] == "+" or symbol[-1] == "-":
        stack.append(symbol.pop())
    symbol.append(eq[n])
  elif eq[n]=="*" or eq[n]=="/":
    symbol.append(eq[n])
  else:
    stack.append(eq[n])
    if symbol:
      if symbol[-1] == "*" or symbol[-1] == "/":
        stack.append(symbol.pop())
  postfix(n+1)

postfix(0)

print("".join(stack))

 

개인적으로 너무 어려웠던 문제. 코드를 짜는게 어려웠던것도 있지만 문제를 잘못 이해해서 혼자만의 싸움을 하느라 진이 다 빠져버렸다. 문제를 잘 읽고 후위표기식 알고리즘부터 정확히 이해해야 후위표기식을 구현하는 알고리즘도 잘 짤 수가 있다.

 

구현방식은 재귀함수를 이용하였다. 괄호를 만나면 괄호에서부터 재귀함수를 실행해주고, 괄호가 닫히면 return 후 원래함수로 돌아오는 시스템으로 구현하려고 했는데, 다 만들고 나니까 굳이 재귀함수로 할 필요 없이 for문 돌려도 되겠다는 생각을 했다...

 

 

오늘의 교훈) 문제를 완벽하게 이해하고 알고리즘을 구현하자