기초 알고리즘 1/2. 203 - 자료 구조 1(참고)
1918번. 후위 표기식

문제

1918번 문제 링크

soltuion

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

// 연산 우선 순위
// 1위. 괄호
// 2위. 곱셈, 나눗셈
// 3위. 덧셈. 뺄셈

let stack = [];

let ans = "";

for(let i = 0; i < input.length; i++){
    let value = input[i];
    
    // 괄호가 열리면 닫힐 때까지 스택에 넣는다
    if(value === "("){
        stack.push(value);
    } else if(value === ")"){
        // 괄호가 닫히면
        // 스택에서 "("를 만나기 전까지
        // pop해서 ans에 연결한다.
        while(stack.length > 0 && stack[stack.length - 1] !== "("){
            ans += stack.pop();
        }
        
        // "("를 만나서 while문이 끝나면 pop을 한 번 더 해줘서 "("를 제거한다.
        stack.pop();
    } else if(value === "*" || value === "/"){
        // 곱셈, 나눗셈이 나오면
        // 스택에 연산자가 들어있고, 가장 위가 곱셈 or 나눗셈 연산자라면
        while(stack.length > 0 && (stack[stack.length - 1] === "*" || stack[stack.length - 1] === "/")){
            // pop해서 ans에 넣어준다.
            ans += stack.pop();
        }
        
        // 스택에 연산자가 없다면, 현재 연산자를 스택에 넣는다.
        stack.push(value);
    } else if(value === "+" || value === "-"){
        // 스택에 연산자가 있고, 맨 위가 "("가 아닐 경우
        while(stack.length > 0 && stack[stack.length - 1] !== "("){
		    // pop해서 ans에 넣어준다.
            ans += stack.pop();
        }
        
        // 스택에 연산자가 없거나, 스택 맨 위에 "("가 있다면
        // 현재 연산자를 스택에 넣는다.
        stack.push(value);
    } else {
        // 알파벳이 나오면 그대로 ans에 추가한다.
        ans += value;
    }
}

while(stack.length > 0){
    // 스택에 남아있는 연산자들을 pop해서 ans에 이어준다.
    ans += stack.pop();
}

console.log(ans);

이번 문제도 이해하기가 어렵다. 스택을 이용하는 것은 알겠는데, 감이 안왔다.
핵심은 연산자의 우선 순위를 잘 따지는 것이다.

1. 괄호 내부
2. 곱셈, 나눗셈
3. 덧셈, 뺄셈

또한, 연산자의 우선 순위를 따지느라, 알파벳은 나오는 순서 그대로 ans에 들어가야하는 것을 까먹으면 안된다.
스택에는 연산자만 들어간다.

참고 자료

참고 자료 1
참고 자료 2