[백준] #1918 Python

백준 1918 파이썬
https://www.acmicpc.net/problem/1918

아이디어

stack에 쌓을 때 연산자에 따른 우선순위를 정해서 쌓는다.

• $\times$/$\div$ 와 같은 연산자는 더 높은 우선순위가 없기에 먼저 들어온 $\times$/$\div$를 먼저 결괏값에 배치한다
• +/- 와 같은 연산자는 가장 우선순위가 낮기에 괄호가 아닌 이상 전부 결괏값에 배치한다.
• ) 는 ( 가 나오기 전까지의 모든 연산자를 결괏값에 배치한다.

전체코드

import sys
input = sys.stdin.readline

letters = input()
stack = []
ans = ''
for i in letters:
    if i.isalpha():
        ans += i
    else:
        if i == '(': 
            stack.append(i)
        elif i == '*' or i == '/': # 먼저 들어오고 같은 우선순위에 있는 */는 ans에 넣어줌
            while stack and (stack[-1] == '*' or stack[-1] == '/'):
                ans += stack.pop()
            stack.append(i)
        elif i == '+' or i == '-': #이보다 낮은 우선 순위가 없어서 연산자이면 전부 ans에 넣어줌
            while stack and stack[-1] != '(':
                ans += stack.pop()
            stack.append(i)
        elif i == ')': # 닫음 괄호와 열음 괄호 사이에 있는 연산자들 전부 반환
            while stack and stack[-1] != '(':
                ans += stack.pop()
            stack.pop()

while stack:
    ans += stack.pop()
print(ans)
        

느낀점

처음엔 계산식 안의 가장 괄호 안쪽에 있는 식부터 순서대로 후위식 표기로 반환해야 한다고 생각해서 재귀함수로 구현하려고 했다.
시간 초과도 초과지만 제대로 구현하기가 어려웠고,,, 풀이를 확인해보니 stack을 활용하는 문제였다,,,
후위표기식 변환 문제는 자료구조에서 빈번히 다루는 문제라고 한다! 나중에 자료구조 강의 들을 때 남들보다 하나는 더 아는게 있겠지,,,