백준 1918번 후위표기식 - 파이썬

 

1918번: 후위 표기식

이 문제는 stack의 LIFO 특징을 이용해서 중위 표기식을 후위 표기식으로 변환시키는 문제이다. 입력 받은 문자열을 하나씩 읽어들여 연산자들만 stack에 넣고 각 연산자들의 우선순위 규칙에 맞게 pop, append를 한다. 나머지 피연산자들은 최종적으로 답이 될 빈 문자열에 더해준다.

올 수 있는 모든 연산자: +, -, *, /, (, )

우선순위 설정:

priority = {"*": 1, '/':1, '+':0, '-':0,'(':-1}

나는 문제를 풀기 위해서 문자열을 읽어들일 때, 경우를 나누고 우선순위를 부여했다.

1. '(' 인 경우 : 여괄호는 우선순위가 높기 때문에 항상 append를 시켜준다. 하지만 여괄호 다음으로 오는 다른 연산자들은 항상 append되어야 한다. ex) (+) 우선순위가 높긴 하지만 그 안의 연산자를 담아야하기 때문에 우선순위를 낮게 잡았다.

2. ')': 닫는 괄호가 오면 여괄호를 만날 때까지 stack.pop을 해주어 정답이 될 문자열에 더해줌. ex) ans += stack.pop()

3. 나머지 연산자들: stack[-1]의 우선순위가 다음으로 올 연산자보다 크거나 같다면 pop! -> stack[-1]의 우선순위가 다음 연산자보다 작을 때 까지 pop

** while문에서 조건을 쓸 때 index out of range 에러가 날 수 있는 위험성을 체크해야한다.

while stack[-1] ,,,, 보다는 while stack: 안에 조건문을 하나 더쓰자.

 

내 코드

from collections import deque
arr = deque(list(input()))

ans = ""
priority = {"*": 1, '/':1, '+':0, '-':0,'(':-1}
stack = []

while arr:
    val = arr.popleft()
    if ord(val) >= 65:
        ans += val
    else:
        if stack:
            if val == '(':
                stack.append(val)
            elif val == ')':
                while stack[-1] != '(':
                    ans += stack.pop()
                stack.pop()
            else:
                while stack:
                    if priority[val] <= priority[stack[-1]]:
                        ans += stack.pop()
                    else:
                        break                
                stack.append(val)
        else:
            stack.append(val)

while stack:
    ans += stack.pop()
for val in ans:
    print(val,end='')