[백준] 1935. 후위 표기식2 풀이 / Python, JavaScript

1935번: 후위 표기식2

 

작성 코드 (.py)

import sys
input = sys.stdin.readline

n = int(input())
formula = list(input())
s = []
table = {}
for v in formula:
    if v.isalpha() and v not in table:
        table[v] = int(input())
for i, v in enumerate(formula):
    if v.isalpha():
        formula[i] = table[v]
for i in range(len(formula) - 1):
    if type(formula[i]) is int:
        s.append(formula[i])
    else:
        a, b = s.pop(), s.pop()
        s.append(eval(f"{b} {formula[i]} {a}"))
print(f"{s[0]:.2f}")

작성 코드 (.js)

function solution(n, formula, numbers) {
  formula = formula.split("");
  const s = [];
  const table = {};
  const isAlpha = /[A-Z]/;
  formula.forEach((v) => {
    if (isAlpha.test(v) && !table[v]) table[v] = numbers.shift();
  });
  formula.forEach((v, i) => {
    if (isAlpha.test(v)) formula[i] = table[v];
  });
  for (let i = 0; i < formula.length; i += 1) {
    if (!isNaN(formula[i])) s.push(formula[i]);
    else {
      const [a, b] = [s.pop(), s.pop()];
      s.push(eval("" + b + formula[i] + a));
    }
  }
  return s[0].toFixed(2);
}
console.log(solution(5, "ABC*+DE/-", [1, 2, 3, 4, 5]));

 

구현 로직 (스택)

일반적인 수식이 2 + 3처럼 중위표기를 사용한다면 후위표기는 연산자를 2 3 + 처럼 뒤쪽에 놓는 방식입니다.

문제 예제에서 123*+45/- 를 풀이하면 1+(2*3)-(4/5) = 6.2 순으로 풀이됩니다. 예제에서는 연산자 순서상 곱하기와 나누기가 먼저 계산되었지만 +나 -가 먼저나온다고 해서 중위식처럼 곱하기와 나누기를 먼저 계산하지는 않고 먼저 마주치는 연산자부터 계산합니다. 예를 들면 123+*45-/ 는 1*(2+3)/(3-4) = -5 로 계산됩니다. 

 

스택을 활용할 수 있는 대표적인 유형이고 위와 같은 후위식을 짤 수 있습니다. 먼저 식(formula)에 들어있는 각 제네릭에 해당하는 값을 테이블에 등록해두고 입력값을 받아 숫자로 변경합니다.

 

식의 요소들을 순회하면서 숫자인 경우에는 스택에 집어넣고 연산자인 경우에는 스택에서 상단의 수 2개를 꺼내 연산의 결과를 다시 스택에 집어넣습니다. 계산이 모두 끝나면 스택에는 마지막 결괏값 하나가 남아있게되고 이 값을 소수점 둘째자리까지 표시하면 됩니다.