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

• Problem Link : https://www.acmicpc.net/problem/1935

문제

• 피연산자의 개수와 후위 표기식이 주어질 때 이를 계산하자.
• 중위 표현식으로 바꾸는 문제가 아니다, 후위 표기식을 계산하면 된다.
• 괄호는 없고 사칙 연산만 제공된다.

입력

• 첫째 줄, 피연산자의 개수 N이 주어진다.
• 둘째 줄, 피연산자를 영대문자로 표현한 후위 표기식이 주어진다.
• 셋째 줄, 그 다음 N+2줄까지 각 영대문자에 대응되는 값이 주어진다.

출력

• 계산 결과를 소수점 둘째 자리까지 출력

풀이에 앞서

전위, 중위, 후위 표기식이란?

쉽게 말해 연산자의 위치라고 보면 된다. 전위는 말그대로 피연산자의 앞에 연산자를 위치, 중위는 피연산자 사이에 연산자를 위치, 후위는 피연산자 뒤에 연산자를 위치시킨다는 뜻이다.

우리가 흔히 1+2와 같이 표기하는 방식은 중위 표기식으로 1, 2와 같은 피연산자 사이에 '+' 연산자가 위치한 모습니다. 이 때 중위 표현식을 전위, 후위 표현식을 쉽게 바꾸는 방법은 연산 우선순위에 괄호를 모두 친후 괄호의 왼쪽에 연산자들을 모두 옮기거나, 오른쪽에 연산자들을 옮긴후 괄호를 지워주기만 하면 각각 전위, 후위 표기식으로 변환된다.

전위, 중위, 후위 표기식은 스택 자료 구조를 이용한 문제로 자주 출제된다.

더 자세한 개념이나 예시, 변환 방법은 이 문서를 참고하자.

풀이

후위 표기식은 스택을 이용해 간단하게 구현할 수 있다. 피연산자를 스택에 넣고 연산자가 들어오면 기존 스택에 push되어 있는 피연산자 2개를 pop해서 연산자에 해당하는 연산을 진행한 후 해당 결과를 다시 스택에 push해주면 끝이다.

후위 표기식이 간단한 이유는 중위 표기식의 경우 사칙연산 사이에서도 우선순위가 존재해 이를 고려해서 계산해야하지만 후위 표기식은 이미 우선순위에 맞게 연산자가 위치해있는 것이기 때문에 단순히 스택에 피연산자를 유지시켜주기만 한다면 곧바로 구현 가능하다.

코드

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())

s = input().strip()

m = []
for _ in range(n) :
    m.append(int(input()))

q = deque()
ans = 0
for c in s :
    if c in ['+','-','*','/'] :
        n2 = q.pop()
        n1 = q.pop()
        ans = n1 + n2 if c=='+' else n1-n2 if c=='-' else n1*n2 if c=='*' else n1/n2
        q.append(ans)
    else :
         q.append(m[ord(c)-ord('A')])   

print("%.2f"%q.pop())