백준 node.js 1918번 후위 표기식JavaScript JS

 

1918번: 후위 표기식

😉문제 설명

이번 문제는 stack을 이용하는 문제입니다.

1. 주어진 input을 배열로 만들고 차례대로 순회합니다.
2. 순회 중인 값이 연산자 혹은 괄호 일 경우, stack에 넣고, 그렇지 않고 문자일 경우 정답 배열에 넣습니다.

---

• 연산자의 값이 +, -일 때는 스택에 넣고, 그 다음 스택으로 들어오는 연산자가 +, - 일 경우, 먼저 스택에 들어가 있는 연산자를 꺼내고 정답 배열에 넣습니다. 이후 들어온 연산자를 stack에 넣습니다.

//A+B-C의 예시
1. 순회중인 문자 A
정답 배열 = [A]
스택 = []
2. 순회중인 문자 +
정답 배열 = [A]
스택 = [+]
3. 순회중인 문자 B
정답 배열 = [AB]
스택 = [+]
4. 순회중인 문자 -
정답 배열 = [AB+]
스택 = [-]
5. 순회중인 문자 C
정답 배열 = [AB+C]
스택 = [-]
6. 순회가 끝난 후
정답 배열 = [AB+C-]
스택 = []

 

• 연산자의 값이 +, -일 때는 스택에 넣고, 그 다음 스택으로 들어오는 연산자가 *, / 일 경우 다음 연산자인 *, /을 stack에 넣고, 그 다음 문자가 정답 배열에 들어갔을 경우 stack에서 pop하여 정답 배열에 넣습니다.

//A+B*C의 예시
1. 순회중인 문자 A
정답 배열 = [A]
스택 = []
2. 순회중인 문자 +
정답 배열 = [A]
스택 = [+]
3. 순회중인 문자 B
정답 배열 = [AB]
스택 = [+]
4. 순회중인 문자 *
정답 배열 = [AB]
스택 = [+*]
5. 순회중인 문자 C
정답 배열 = [ABC*]
스택 = [+]
6. 순회가 끝난 후
정답 배열 = [ABC*+]
스택 = []

• 위의 과정을 괄호를 기준으로 반복합니다.

---

🤨주의 사항

입력 값에 trim 메서드를 적용하지 않으니 틀린 답으로 채점 됩니다. 이것 때문에 시간을 많이 잡아먹어서 적습니다..!

틀린 코드

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split("");

맞는 코드

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("");

---

😎문제 풀이

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("");

let string = [];
let stack = [];
for (let i = 0; i < input.length; i++) {
  const cur = input[i];
  if (["*", "/", "+", "-", "("].includes(cur)) {
		// 1. 순회중인 연산자가 +,- 일 때 바로 뒤에 오는 연산자가 +, - 일 경우, stack의 앞쪽에 위치한 연산자를 먼저 pop하고 배열에 푸쉬하여야 한다. *,/ 이 오는 경우는 3번에서 처리함으로 경우의 수가 존재하지 않는다. 따라서 "("배열일 경우만 신경쓰면 된다.
    if (stack.length > 0 && (cur === "+" || cur === "-")) {
      if (stack[stack.length - 1] !== "(") string.push(stack.pop());
    }
    stack.push(cur);
  } else {
		// 2. 괄호가 닫히면 괄호가 열려있는 곳 까지 비워주어야 한다.
    if (cur !== ")") {
      string.push(cur);
    } else {
      while (stack[stack.length - 1] !== "(") {
        string.push(stack.pop());
      }
      stack.pop();
    }
		// 3. *,/ 연산자는 우선순위가 높기 때문에 바로 pop하여 정답 배열에 push한다.
    if (stack[stack.length - 1] === "*" || stack[stack.length - 1] === "/") {
      string.push(stack.pop());
    }
  }
}
while (stack.length !== 0) {
  string.push(stack.pop());
}
console.log(string.join(""));