[백준/Python3] 1935 후위 표기식2

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

(본 글은 라이트 모드로 읽는 걸 권장합니다.)

---

풀이

문제 이름에서도 확인할 수 있듯이 이번 문제는 후위 표기식에 대한 문제다. 후위 표기식은 스택을 통해 해결할 수 있다. 일단, 알파벳을 숫자로 치환하지 않고 중위 표기식으로 바꾼다고 생각을 해보자.

위 그림은 백준 문제 사이트에 있는 입력 1을 표시한 것이다. 이 그림에서 왼쪽부터 차례대로 탐색한다. 표 안에 들어있는 문자는 크게 두 가지인 A~Z까지의 문자(피연산자)와 연산자로 분류할 수 있다. 처음부터 탐색할 때 현재 문자가 A~Z라면 스택에 push한다.

C까지 탐색했을 경우 전부 피연산자였으므로 모두 스택에 들어있는 모습이다.

탐색했을 시 현재 문자가 연산자일 경우 스택에 넣지 않고 피연산자 2개를 스택에서 가져와야한다. 때문에 2번에 pop으로 피연산자를 가져오고 연산자를 통해 계산한다. 계산 결과는 피연산자가 되므로 다시 스택에 push한다.

이와 같은 방법으로 끝까지 진행하면 중위표기식을 얻을 수 있다.

코드

N = int(input())
post = list(input())
stack = list()
nums = list()

for _ in range(N):
    nums.append(int(input()))

# postfix -> infix
for p in post:
    if 'A' <= p <= 'Z':
        stack.append(nums[ord(p) - ord('A')])
    else:
        operand_2 = stack.pop()
        operand_1 = stack.pop()

        if p == '+':
            stack.append(operand_1 + operand_2)
        elif p == '-':
            stack.append(operand_1 - operand_2)
        elif p == '*':
            stack.append(operand_1 * operand_2)
        elif p == '/':
            stack.append(operand_1 / operand_2)

ans = stack.pop()
# 소수점 둘째 자리까지
print(f"{ans:0.2f}")

실제 코드에서는 스택에 피연산자를 넣을 때 대응하는 값으로 바로 변환 후 push했다. 따라서 마지막으로 스택에 계산 결과가 남게된다.