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문 돌려도 되겠다는 생각을 했다...
오늘의 교훈) 문제를 완벽하게 이해하고 알고리즘을 구현하자