[알고리즘] 백준 1918 - 후위 표기식

문제

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

1918번: 후위 표기식

 

풀이

내가 스스로 못 푼 문제 ^ ___ ^ 사실 이런 연산식과 관련된 문제 나오면 얼어버리는 습관(...)이 있다. 내가 잘 못 풀기 때문. 스택 문제라는건 알았는데 어떻게 구현을 해야할지 떠올리지를 못했다. 쩝 ㅠ . ㅠ

 

앞에서부터 요소를 탐색하는데 피연산자가 나오면 바로 answer에 더해주고, 연산자가 나오면 stack에 넣어주는 방식이다. stack에 넣어주기 전에 이전에 나온 연산자들(stack에 쌓여있는) 중에서 우선순위를 따지고 answer에 추가해준다. 마지막 else문은 닫는 괄호가 나왔을 경우로, 이 때는 스택에 쌓인 모든 연산자 + 괄호들을 소진해줘야 한다. (왜냐하면 괄호보다 높은 우선순위를 가진 연산자는 없으니까)

 

풀이를 보고 대강 이해하긴 했는데 이걸 어떻게 혼자 스스로 생각하지...

 

코드

input_str = input()

answer = ""
stack = []

for a in input_str:
    if a.isalpha():
        answer+=a
    elif a == "(":
        stack.append(a)
    elif a=="*" or a=="/":
        while stack and (stack[-1] == "*" or stack[-1] == "/"):
            answer+=stack.pop()
        stack.append(a)
    elif a=="+" or a=="-":
        while stack and stack[-1] != "(":
            answer+=stack.pop()
        stack.append(a)
    else:
        while stack and stack[-1] != "(":
            answer+=stack.pop()
        stack.pop()

while stack: # 남아 있는 문자 정답으로 추가하기
    answer += stack.pop()
print(answer)