[백준] 1918번 - 후위 표기식 (파이썬)

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

# 후위 표기식
from collections import deque
from re import L
notAlpha = {'+': 1, '-': 1, '*': 2, '/': 2, '(': 0, ')': 0}

alpha = deque()
sign = []


def popAll():
    while alpha:
        result.append(alpha.popleft())
    x = sign.pop()
    while sign:
        temp = sign.pop()
        if x == ')' and temp == '(':
            break
        if temp == '(':
            sign.append(temp)
            break
        if notAlpha[x] <= notAlpha[temp]:
            result.append(temp)
        else:
            sign.append(temp)
            break
    if x != ')':
        sign.append(x)


arr = list(input().strip())
result = []
temp = []
isParen = 0
for x in arr:
    if x not in notAlpha:
        alpha.append(x)
    else:
        sign.append(x)
        if sign[-1] == ')':
            popAll()
        if len(sign) > 1 and sign[-1] != '(' and notAlpha[sign[-1]] <= notAlpha[sign[-2]]:
            popAll()

while alpha:
    result.append(alpha.popleft())
while sign:
    result.append(sign.pop())
print(*result, sep='')

 

자료구조(스택, 큐)

1. notAlpha 딕셔너리를 만들어서 연산자들의 우선순위를 부여한다 (괄호는 0으로 했다)

2. 문자열을 하나씩 입력받고 알파벳이면 alpha(큐)에 append

    - 연산자이면 sign(스택)에 append해주고, ')'이면 popAll, 괄호를 제외한 연산자라면 이전연산자와 우선순위를 비교

    - 이전 연산자의 우선순위가 더 크거나 같으면 popAll

3. popAll : alpha(큐)와 sign(스택)에서 아이템들을 pop해주는 함수

    - alpha(큐)는 전부 popleft해서 result에 append

    - sign(스택)은  '('가 나오면 break, 연산자의 우선순위가 현재 자신보다 낮면 break

4. 남은 모든 alpha(큐)와 sign(스택)을 popleft, pop

5. result를 출력

 

의식의 흐름대로 풀었는데 다풀고나서 디버깅할때 무슨 말인지 모르겠다.

다음부턴 가독성 좀 생각해서 체계적으로 짜자...