[백준] 1918 후위 표기식 - javascript

📌 문제

https://www.acmicpc.net/problem/1918

📌 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

let str = input[0];
let stack = [];
let ans = "";
for (let i = 0; i < str.length; i++) {
  if (str[i] >= "A" && str[i] <= "Z") {
    ans += str[i];
  } else if (str[i] === "(") {
    stack.push(str[i]);
  } else if (str[i] === ")") {
    while (stack.length && stack[stack.length - 1] !== "(") {
      ans += stack.pop();
    }
    stack.pop(); // ( 지워주기
  } else if (str[i] === "+" || str[i] === "-") {
    while (stack.length && stack[stack.length - 1] !== "(") {
      ans += stack.pop();
    }
    stack.push(str[i]);
  } else if (str[i] === "*" || str[i] === "/") {
    while (
      (stack.length && stack[stack.length - 1] === "*") ||
      stack[stack.length - 1] === "/"
    ) {
      ans += stack.pop();
    }
    stack.push(str[i]);
  }
}
while (stack.length) {
  ans += stack.pop();
}
console.log(ans);

✔ 알고리즘 : 자료구조(stack)

✔ 괄호와 연산자에 대한 우선순위를 생각하면서 풀어야하는 문제

✔ 괄호를 열고 닫을때, 연산자가 들어올때만 스택에서 원소를 넣고 빼는 작업을 해야 한다.

✔ 대문자가 들어오는 경우는 바로 ans에 더해준다.

✔ ( 가 들어왔을 때 : 그대로 stack에 push

✔ ) 가 들어왔을 때 : stack이 비어있지 않고 스택의 상단이 ( 일때까지 pop하여 ans에 push 한 후 괄호시작부분인 ( pop 한다.

✔ +,- 가 들어왔을 때 : 연산자 우선순위가 제일 낮으므로 )가 들어왔을때랑 같이 처리하되 마지막에 pop하지 않고 현재 연산자를 push한다.

✔ *, / 가 들어왔을 때 : 연산자 우선순위가 높으므로 스택이 비어있지 않고 스택의 상단이 곱하기나 나누기 연산자이면 계속 pop하여 ans에 push한다. 마지막에 현재 연산자를 push해준다

✔ 문자열길이 만큼 for문을 돌고 스택의 나머지를 모두 ans에 push한다.

✔ 난이도 : 백준 기준 골드 3