알고리즘 기초 - 후위 표기식2 (백준 1935)

문제

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

입력

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

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

출력

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

예제 입력 1

5
ABC*+DE/-
1
2
3
4
5

예제 출력 1

6.20

예제 입력 2 

1
AA+A+
1

예제 출력 2

3.00

---

후위표기식은 다음과 같다. 중위 표기식을 괄호로 묶고 연산자를 괄호 뒤로 보내주면 된다.

( A + (B * C) ) - ( D / E ) = ABC*+DE/-

표기식을 쭉 순회하다가 연산자가 나오면 짝지어 계산해야한다. 스택을 떠올릴 수 있다. 스택은 원하는 짝꿍을 만날 때까지 기다리는 문제에서 자주 사용된다.

그렇다면 알파벳이 나오면 스택에 넣어주다가 연산자 문자가 나오면 가장 최근에 넣었던 알파벳 두개를 짝지어서 연산해주고 다시 스택에 넣어주면 된다.

이 때 알파벳에 매칭되는 숫자가 입력값으로 주어지므로 알파벳에 맞게 숫자들을 매칭시켜야한다.

알파벳이 같으면 같은 숫자가 매칭된다는 점에 유의하자.

 

코드

Number의 toFixed 메서드를 이용해 소수점 둘째자리까지 출력할 수 있다.

let input = require('fs').readFileSync(0).toString().trim().split('\n');
input = input.map((e) => e.trim());
let n = Number(input[0]);
let p = input[1];
let m = input.slice(2).map(Number);
let stack = [];
let map = new Map();

function solution() {
  let tmp = 0;
  for (let i = 0; i < p.length; i++) {
    if (p[i].charCodeAt() >= 65 && p[i].charCodeAt() <= 90) {
      if (!map.has(p[i])) map.set(p[i], m[tmp++]);
    }
  }
  for (let i = 0; i < p.length; i++) {
    if (p[i].charCodeAt() >= 65 && p[i].charCodeAt() <= 90) stack.push(map.get(p[i]));
    else {
      let a = stack.pop();
      let b = stack.pop();
      if (p[i] === '*') stack.push(a * b);
      if (p[i] === '/') stack.push(b / a);
      if (p[i] === '+') stack.push(a + b);
      if (p[i] === '-') stack.push(b - a);
    }
  }
  return Number(stack.at(-1)).toFixed(2);
}

console.log(solution());