백준/ Gold 2 문제 , 백준 Node.js 자바스크립트 1918 , 후위 표기식[자료구조, 스택]

백준/ Gold 2 문제 , 백준 Node.js 자바스크립트 1918 , 후위 표기식[자료구조, 스택]

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?
-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
반례가 너무 많아서 체감 난이도가 높았음.

 

 

 

문제 출처

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

1918번: 후위 표기식

 

 

 

 

 

요구사항 📋

1. 중위 표현식이 주어지면 후위 표현식으로 바꾸어라.

2. 괄호와 연산자의 우선순위를 잘 고려하기.

 

 

 

 

해결 전략 📝

 

처음에 접근 법은 +,- 가중치를 1 , *,/ 가중치를 2로 잡고 괄호내로 들어갈때마다 가중치 +=3  씩 해주는 로직으로 짰었다.

 

하지만, 이렇게 되다보니 괄호 내에 들어갈때 각 연산자가 가지고 있는 우선순위를 고려하기가 만만치 않았음.

 

또한 2차원 배열을 선언해서 가중치값을 저장해둬야한다고 판단하여 이 풀이로 푸는 것을 멈췄다.

 

 

이후, 풀이법의 힌트를 얻어 각 연산자에 맞춰서 스택에 저장해두었다가 빼서 더하는 식으로 풀었다.

 

 

 

1. 식을 하나씩 확인하여 스택을 사용한다.

2. 알파벳이 나오면 바로 결과값에 더해준다.

3. 여는 괄호가 나오면 store 에 저장해둔다.

4. 닫는 괄호가 나오면 store의 오른쪽 값들 부터 시작해서

   여는 괄호가 나올때까지 결과값에 더해준다.

   이때, 여는 괄호가 나오면 while문을 종료하고 store에서 여는 괄호 삭제.

5. +,- 연산자는 우선 순위가 낮으므로 괄호내에 있는 상황까지 고려해서

   여는 괄호가 나올때까지 앞에 먼저 나온 연산자들을 모두 결과값에 더해준다.

6. *,/ 연산자는 우선 순위가 높다. 따라서, 앞 쪽에 먼저 나온 *,/ 연산자를 먼저 계산해줘야하므로

   store에 *,/ 연산자가 저장되어있는지 확인하고 그값들은 결과값에 우선 더해준 뒤에 store에 추가시킨다.

 

 

연산 방법은 위와 같다.

 

이 문제에서 가장 처리하기 힘든 부분은 괄호내에서 우선순위가 높은 연산자가 먼저 나오고 후에 우선순위가 낮은 연산자가 나오는 경우이다.

 

예를 들면, 

 

A+(B*(C/D+E)-F) 

 

와 같은 경우이다.

 

 

내가 처음 푼 가중치를 가지고 푼 풀이도 이 방법을 처리하는데서 막혔고 이걸 해결하려면 코드도 길어지고 메모리 낭비도 컸다.

 

 

따라서, 스택에 저장해두고 바로바로 처리를하는 풀이를 해준다면 훨씬 효율적인 풀이가 가능했다.

 

 

여는 괄호는 그냥 여는괄호를 스택에 넣어주고

닫는 괄호는 여는 괄호가 나올때까지 스택에서 빼주면 되기때문에 어려운것은 없다.

 

핵심은 연산자 처리이다.

 

위와 같이 연산자 우선순위에 따라 나눠서 처리를 해줘서 스택에 담아주고 빼는것이 핵심이다.

 

+,- 연산자는 앞에+,-,*,/  연산자 무엇이 나오든 앞의 연산자보다 먼저 계산하는 일은 없다.

 

하지만, 괄호 내로 들어가면 괄호 밖의 연산자들보단 우선순위가 높아지기 때문에 여는 괄호가 나올때까지 앞서 나왔던 연산자들을 모두 결과값에 더해주면된다.

 

 

앞에서 + * 이 나왔다면  +* 연산자를 먼저 결과값에 더해준뒤에 자기 자신 + 나 - 를 store에 저장시키면된다.

 

 

 

그다음 *, / 연산자는 우선순위가 높다.

 

앞에 +* 연산자가 나왔다면 *연산자만 우선 연산을 해야하기때문에 *을 결과 값에 더해준다.

 

이후 자기 자신인 * 혹은 / 연산자를 + 만 남은 store에 저장해준다.

 

 

 

모든 연산을 처리하고 난 뒤에

 

store에 값이 담겨있을 수 있다. 먼저 들어간 값일 수록 나중에 연산해야하기때문에

 

reverse() 메서드를 사용해서 돌려준 뒤에 store 값과 합해주자.

 

 

 

 

 

 

반례 ⚠️

 

입력: A+B+C+D*E

 

정답

AB+C+DE*+

 

 

 

 

입력 : G*(B*(C/D+E)-F)

 

정답 

GBCD/E+*F-*

 

 

 

입력 : J*(G*(H-B*(C/D+E)-F)-K)

 

정답

 

JGHBCD/E+*-F-*K-*

 

 

정답 💯

 

/* 
<요구사항>
1. 우선순위를 구분하는게 핵심일듯하다.
2. 괄호 내 연산자 구분하기
3. *,/ 연산이 +.- 연산보다 우선순위이므로 잘 처리
4. 괄호내 괄호 처리가 까다로워 보임

<해결법>
1. 식을 하나씩 확인하여 스택을 사용한다.
2. 알파벳이 나오면 바로 결과값에 더해준다.
3. 여는 괄호가 나오면 store 에 저장해둔다.
4. 닫는 괄호가 나오면 store의 오른쪽 값들 부터 시작해서 
   여는 괄호가 나올때까지 결과값에 더해준다.
   이때, 여는 괄호가 나오면 while문을 종료하고 store에서 여는 괄호 삭제.
5. +,- 연산자는 우선 순위가 낮으므로 괄호내에 있는 상황까지 고려해서 
   여는 괄호가 나올때까지 앞에 먼저 나온 연산자들을 모두 결과값에 더해준다.
6. *,/ 연산자는 우선 순위가 높다. 따라서, 앞 쪽에 먼저 나온 *,/ 연산자를 먼저 계산해줘야하므로
   store에 *,/ 연산자가 저장되어있는지 확인하고 그값들은 결과값에 우선 더해준 뒤에 store에 추가시킨다.
*/

const input = require("fs").readFileSync("/dev/stdin").toString().trim();

function solution(exp) {
  let [result, store] = ["", []];
  exp.split("").map((v) => {
    if (/[A-Z]/.test(v)) result += v;
    else {
      if (v === "(") store.push(v);
      else {
        while (store.length) {
          let storeEndV = store[store.length - 1];
          if (storeEndV === "(") break;
          else if (v === "+" || v === "-") {
            if (storeEndV === "(") break;
          } else if (v === "*" || v === "/") {
            if (storeEndV !== "*" && storeEndV !== "/") break;
          }
          result += store.pop();
        }
        if (v === ")") store.pop();
        else store.push(v);
      }
    }
  });
  result = [...result, ...store.reverse()];
  return result.join("");
}

console.log(solution(input));