[백준1918_자바스크립트(javascript)] - 후위 표기식

🔴 문제

후위 표기식

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let exp = fs.readFileSync(path).toString().trim();
const stack = [];

let ans = '';

const getPriority = (op) => {
  if (op === '+' || op === '-') return 1;
  if (op === '*' || op === '/') return 2;
  return 0;
};

for (const e of exp) {
  if (/[A-Z]/.test(e)) ans += e;
  else if (e === '(') stack.push(e);
  else if (e === ')') {
    while (stack.length && stack.at(-1) !== '(') {
      ans += stack.pop();
    }
    if (stack.at(-1) === '(') stack.pop();
  } else {
    while (stack.length && getPriority(stack.at(-1)) >= getPriority(e)) {
      ans += stack.pop();
    }
    stack.push(e);
  }
}
while (stack.length) {
  ans += stack.pop();
}
console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

영 감이 안잡혀서 풀이를 봤다.
후위 표기식의 핵심은 알파벳을 push하지 않는 것이다.
연산자간의 우선순위만 따져주면 되므로 중위표기식 문자열을 순회하면서 알파벳은 바로 정답 문자열에 더해준다.
시작하는 괄호는 그냥 배열에 푸시, 끝나는 괄호는 시작괄호를 만날때까지 pop해서 정답 문자열에 더해준다.
이 때 조건을 보면 스택의 길이가 0보다 크고, 마지막요소가 (가 아닐때까지만 pop한다.
이 반복을 끝내주면 스택 내부의 (를 없애주기 위해 한번 pop해준다.
알파벳, 괄호가 아니면 남은 요소는 연산자다. 이때 연산자별로 우선순위를 따져주는 함수 getPriority를 만들어준다.
그래서 연선자를 처리할 때는 스택의 길이가 0보다 크고, 지금 스택에 집어넣을요소의 우선순위가 스택 마지막 요소의 우선순위보다 작을때만 스택에 연산자를 push할 수 있으므로 이 조건을 만족할 때까지 스택에서 pop해서 ans 문자열에 더해주면 된다.

마지막으로 스택이 비어있지 않다면 남은 연산자까지 다 빼서 처리해준다.

이해가 안되면 외우면 된다. 코테는 많이 풀수록 유리하므로 포기하지말고 하자!!

🔵 Ref

GPT가 알려줌