백준 후위 표기식 1918번 javascript

1918번: 후위 표기식

문제의 예제는 통과했었지만 

아래 반례처럼 b+c*d 의 경우 틀려서 찾느라 고생했다.

 

원리는

1. for문을 돌며 하나씩 stack 에 넣으며,

2. stack에서 소괄호가 완성되면

3. 해당 부분을 change 함수에 넣어 계산 후

4. 다시 stack에 넣어주는 방식이다.

// https://www.acmicpc.net/problem/1918
const fs = require("fs");
const stdin = (
  process.platform === "linux"
    ? fs.readFileSync("/dev/stdin").toString()
    : `(A+((B+C*D)+E))`
).split("\n");

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

const data = input().split("");
// console.log(data);

const change = (stack) => {
  const stack2 = [];
  for (let i = 0; i < stack.length; i++) {
    stack2.push(stack[i]);
    if (stack.length > 2 && (stack[i - 1] === "*" || stack[i - 1] === "/")) {
      const right = stack2.pop();
      const op = stack2.pop();
      const left = stack2.pop();
      stack2.push([left, right, op].join(""));
    }
  }
  const stack3 = [];
  for (let i = 0; i < stack2.length; i++) {
    stack3.push(stack2[i]);
    if (stack2.length > 2 && (stack2[i - 1] === "+" || stack2[i - 1] === "-")) {
      const right = stack3.pop();
      const op = stack3.pop();
      const left = stack3.pop();
      stack3.push([left, right, op].join(""));
    }
  }
  return stack3.join("");
};

const stack = [];
for (let i = 0; i < data.length; i++) {
  if (data[i] === ")") {
    const temp = [];
    while (true) {
      const left = stack.pop();
      if (left === "(") break;
      else temp.push(left);
    }
    stack.push(change(temp.reverse()));
  } else {
    stack.push(data[i]);
  }
  // console.log(stack.join(" "));
}

// console.log(stack);
// console.log(stack2);
const res = change(stack);
console.log(res);

과정
1. `(B+C*D)` => `BCD*+`
2. (`BCD*+`+E) => `BCD*+E+`
3. (A+`BCD*+E+`) => ABCD*+E++

// input
// (A+((B+C*D)+E))

// output
// ABCD*+E++

(
( A
( A +
( A + ( (
( A + ( ( B
( A + ( ( B +
( A + ( ( B + C
( A + ( ( B + C *
( A + ( ( B + C * D
( A + ( BCD*+
( A + ( BCD*+ +
( A + ( BCD*+ + E
( A + BCD*+E+
ABCD*+E++