[JavaScript][node.js] 백준 1918 후위 표기식

문제

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

1918번: 후위 표기식

풀이과정

💡 아이디어
✅ 먼저 계산되어야 하는 부호가 앞에 나와야 한다.  A*(B+C) ➡️ ABC+* 
✅ 즉, 부호를 스택에 순서대로 담았다가,
✅ 스택의 가장 위 부호보다 나중에 계산되어야 하는 부호가 나오면 스택에 담긴 부호들을 처리한다.

✅ 이때 연산의 우선순위는, 괄호 > * / > + - > 앞에 온 부호
✅ 앞에 온 부호가 항상 스택의 밑에 깔리므로(FILO), 우선순위를 무시하면 항상 스택에 담긴 부호는 처리대상이 된다. 즉 우리는 우선순위만 고려하면 된다.

✅ 문자는 어떤 경우이든 항상 순서대로 출력되므로, 그냥 바로바로 정답 문자열에 더해준다.

1. 괄호의 처리

if (item === '(') stack.push(item);
else if (item === ')') {
    while (stack[stack.length - 1] !== '(') answer += stack.pop();
    stack.pop();
}

1. 여는 괄호 ( 가 나오면 그냥 스택에 넣어주고,

2. 닫는 괄호 ) 가 나오면, 괄호 안의 남은 부호들을 모두 처리한다.

 

2. 곱셈, 나눗셈의 처리

else if (item === '*' || item === '/') {
    while (
      stack.length &&
      stack[stack.length - 1] !== '(' &&
      stack[stack.length - 1] !== '+' &&
      stack[stack.length - 1] !== '-'
    )
      answer += stack.pop();
    stack.push(item);
}

1. 곱셉 또는 나눗셈이 등장하면, 덧셈 / 뺄셈 부호가 나오기 전까지 처리한다.

2. 위 부호들은 현재 부호보다 우선순위가 낮기 때문이다.

3. 단, 여는 괄호가 있다면 멈춰야 한다. (괄호 이전은 현재 부호보다 우선순위가 낮기 때문)

 

3. 덧셈, 뺄셈의 처리

else if (item === '+' || item === '-') {
    while (stack.length && stack[stack.length - 1] !== '(')
      answer += stack.pop();
    stack.push(item);
}

1. 덧셈 또는 뺄셈이 등장하면, 이미 스택에 담겨있는 것들을 모두 처리한다.

2. 지금 스택에 담겨있는 것들은 무조건 현재 부호보다 우선순위가 높기 때문이다.

3. 단, 여는 괄호가 있다면 멈춰야 한다. (괄호 이전은 현재 부호보다 우선순위가 낮기 때문)

 

4. 문자의 처리

else answer += item;

 

최종코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';

const input = fs.readFileSync(filePath).toString().trim();
const arr = input.split('');

const stack = [];
let answer = '';
arr.forEach((item) => {
  if (item === '(') stack.push(item);
  else if (item === ')') {
    while (stack[stack.length - 1] !== '(') answer += stack.pop();
    stack.pop();
  } else if (item === '*' || item === '/') {
    while (
      stack.length &&
      stack[stack.length - 1] !== '(' &&
      stack[stack.length - 1] !== '+' &&
      stack[stack.length - 1] !== '-'
    )
      answer += stack.pop();
    stack.push(item);
  } else if (item === '+' || item === '-') {
    while (stack.length && stack[stack.length - 1] !== '(')
      answer += stack.pop();
    stack.push(item);
  }
  else answer += item;
});

while (stack.length) answer += stack.pop();
console.log(answer);