[BOJ]1918 후위 표기식

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

1918번: 후위 표기식

풀이

자료구조 문제는 오랜만이라 약간의 도움을 받아서 풀이하였다. 오랜만의 스택을 이용한 문제였는데, 연산자들의 우선 순위를 가지고 스택을 처리해야할 것 같았다. 먼저 연산을 생각하면 괄호가 최우선 값을 갖고, 그 다음이 곱셈, 나눗셈, 그 다음이 덧셈, 뺄셈이겠다. 이제 탐색을 하면서 만약 알파벳이라면 정답 리스트에 넣어주고, 만약 연산자라면 몇 가지 조건 처리를 해준다. 먼저 '('이면 일단 연산자 스택에 넣어준다. 만약 곱셈, 나눗셈이면 일단 스택이 비어있지 않은지 확인하고, 곱셈 혹은 나눗셈이 아닌 이상 우선순위가 높기 때문에 만약 스택의 마지막 원소가 곱셈 혹은 나눗셈이면 연산자 스택에서 pop해줘서 정답에 넣어준다. 그 다음 덧셈 혹은 뺄셈이면 먼저 온 덧셈 뺼셈과 모든 곱셈과 나눗셈에 우선순위가 밀리기 때문에 스택이 비어있지 않은지 확인하고 '('가 나올때까지 pop해줘서 정답 리스트에 넣어준다. 여기서 '('가 나올때까지인 이유는 괄호 안에 있는 식이 우선순위를 가지기 때문이다. 만약 ')'이면 '('가 나올때까지 모든 요소를 다 pop해주고, 마지막에 연산자 스택에서 '('를 뺴주기 위해 pop해준다. 모든 과정이 끝나고 스택에 아직 요소가 남아있을 수 있기 때문에 스택이 빌때까지 pop해줘서 정답 리스트에 넣어준다.

import sys
input = lambda: sys.stdin.readline().rstrip()
operation = input()
op_stack = []
ans = []
for o in operation:
    if 65 <= ord(o) <= 90:
        ans.append(o)
    else:
        if o == "(":
            op_stack.append(o)
        elif o == '*' or o == '/':
            while op_stack  and (op_stack[-1] == '*' or op_stack[-1] == '/'):
                ans.append(op_stack.pop())
            op_stack.append(o)
        elif o == '+' or o == '-':
            while op_stack and op_stack[-1] != '(':
                ans.append(op_stack.pop())
            op_stack.append(o)
        elif o == ')':
            while op_stack and op_stack[-1] != '(':
                ans.append(op_stack.pop())
            op_stack.pop()
while op_stack:
    ans.append(op_stack.pop())
print(*ans, sep='')