스택_백준 #1935:후위 표기식2

문제

후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. 3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는값 , 5번째 줄에는 C ...이 주어진다, 그리고 피연산자에 대응 하는 값은 100보다 작거나 같은 자연수이다.

후위 표기식을 앞에서부터 계산했을 때, 식의 결과와 중간 결과가 -20억보다 크거나 같고, 20억보다 작거나 같은 입력만 주어진다.

출력

계산 결과를 소숫점 둘째 자리까지 출력한다.

 

 

---

풀이 과정

후위 표기식이란?

 

1. 입력할 숫자 개수 입력 : N 

2. 후위표기식 입력 : arr => string

3. 후위표기식에 대응되는 숫자 입력 : num => deque()

4. 후위표기식 숫자에 대응하는 문자와, 그 숫자를 딕셔너리 key value 형태로 생성  {A : 1}

5. arr를 for문으로 한 문자씩 돌면서 사칙연산 기호가 아니라면 stack => list()에 쌓고 

    사칙연산 기호라면 쌓인 스택에서 최상위 2개 숫자를 꺼내서 계산하고 스택에 다시 넣기

 

 

 

import sys
from collections import deque

def input():
  return sys.stdin.readline().rstrip()

N = int(input()) # 피연산자 개수 입력
arr = input() # 후위표기식 입력
oper = '+-*/'
dic = {}
stack = []
num = deque() # 피연산자 대응값 입력 숫자 저장

for i in range(N):
  num.append(int(input())) # 피연산자 대응값에 해당할 숫자 입력

for i in arr:
  if i not in dic and i not in oper: # ABC*+DE/- 의 경우 ABCDE
    dic[i] = num.popleft() # 피연산자 대응값 딕셔너리 형태 저장

for i in arr:
  if i not in oper:
    stack.append(dic[i])
  else:
    if i == '+':
      a = stack.pop()
      b = stack.pop()
      stack.append(a+b)
    elif i == '-':
      a = stack.pop()
      b = stack.pop()
      stack.append(b-a)
    elif i == '*':
      a = stack.pop()
      b = stack.pop()
      stack.append(a*b)
    else:
      a = stack.pop()
      b = stack.pop()
      stack.append(b/a)

print(f"{stack[0]:.2f}")