틀린 예제 분석

    // 10,6,9,3,+,-11,*,/,*,17,+,5,+
    // operator: []
    // operand: []
    // formula: []  
    
    // (10),6,9,3,+,-11,*,/,*,17,+,5,+
    // operator: []
    // operand: [10]
    // formula: []  

    // 10,(6),9,3,+,-11,*,/,*,17,+,5,+
    // operator: []
    // operand: [10,6]
    // formula: []  

    // 10,6,(9),3,+,-11,*,/,*,17,+,5,+
    // operator: []
    // operand: [10,6,9]
    // formula: []

    // 10,6,9,(3),+,-11,*,/,*,17,+,5,+
    // operator: []
    // operand: [10,6,9,3]
    // formula: []  

    // 10,6,9,3,(+),-11,*,/,*,17,+,5,+
    // operator: [+]
    // operand: [10,6,9,3]
    // formula: []

    // operator가 빈 stack이 아닌데 operand와 길이가 2 이상 차이가 난다면
    // formula가 빈 배열이라면
    // operand pop => operator pop => operand pop

    // operator: []
    // operand: [10,6]
    // formula: [9,+,3] => [12]

    // 10,6,9,3,+,(-11),*,/,*,17,+,5,+
    // operator: []
    // operand: [10,6,-11]
    // formula: [12]

    // 10,6,9,3,+,-11,(*),/,*,17,+,5,+
    // operator: [*]
    // operand: [10,6,-11]
    // formula: [12]

    // operator가 빈 stack이 아닌데 operand와 길이가 2 이상 차이가 난다면
    // formula가 빈 배열이 아니라면
    // operator pop => operand pop

    // operator: []
    // operand: [10,6]
    // formula: [12,*,-11] => [-132]

    // 10,6,9,3,+,-11,*,(/),*,17,+,5,+
    // operator: [/]
    // operand: [10,6]
    // formula: [-132]

    // 10,6,9,3,+,-11,*,/,(*),17,+,5,+
    // operator: [/,*]
    // operand: [10,6]
    // formula: [-132]

    // operator의 길이가 1을 넘으려고 한다면 우위 비교
    // 같다면 stack에 있는 것을 formula로 빼고, 들어오려던 것을 stack에 넣어줌.
    // 그리고 operand 가장 위에 있는 것을 formula로 이동

    // operator: [*]
    // operand: [10]
    // formula: [-132,/,6] => [0]

    // operator에 있는 값이 * or / 라면 최고 우위 연산자이므로
    // operator pop => operand pop

    // operator: []
    // operand: []
    // formula: [0,*,10] => [0]
    

    // 10,6,9,3,+,-11,*,/,*,(17),+,5,+
    // operator: []
    // operand: [17]
    // formula: [0]

    // 10,6,9,3,+,-11,*,/,*,17,(+),5,+
    // operator: [+]
    // operand: [17]
    // formula: [0]

    // operator, operand, formula가 모두 비어있지 않으면 연산 진행
    // operator pop => operand pop
    // operator: []
    // operand: []
    // formula: [0,+,17] => [17]

    // 10,6,9,3,+,-11,*,/,*,17,+,(5),+
    // operator: []
    // operand: [5]
    // formula: [17]

    // 10,6,9,3,+,-11,*,/,*,17,+,5,(+)
    // operator: [+]
    // operand: [5]
    // formula: [17]

    // 10,6,9,3,+,-11,*,/,*,17,+,5,+  순회 끝!
    // operator: []
    // operand: []
    // formula: [17,+,5] => [22]

필자의 틀린 풀이

/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function(tokens) {
    if(tokens.length === 1){
        return tokens;
    }

    let operator = [];
    let operand = [];
    let formula = [];
    let result = 0;

    for(let i = 0; i < tokens.length; i++){
        const token = tokens[i];
        console.log("token", token);

        // token이 연산자가 아니라면
        if(!Number.isNaN(Number(token))){
            if(operator.length !== 0 && operand.length - operator.length >= 1){
                formula.push(operand.pop());
                formula.push(operator.pop());
                formula.push(operand.pop());

                console.log("formula ",formula);
                result = calcFormula(formula);
                console.log(result);
                formula = [result];
            }

            operand.push(token);
        } else {
            // 이미 연산자가 있는 상황이라면 우위 비교를 한다.
            if(operator.length >= 1){
                // operator에 있는 연산자가 더 큰 경우
                // 같거나 커야지 operator에 있는걸 빼는거 아니야?
                if(getOperatorPriority(operator[operator.length - 1]) > getOperatorPriority(token)){
                    
                    formula.push(operand.pop());
                    formula.push(operator.pop());
                    formula.push(operand.pop());

                    console.log("formula ",formula);
                    result = calcFormula(formula);
                    console.log(result);

                    formula = [result];


                } else {
                    // 여기서 꼬인듯?
                    // 아래에서 if문 나가고 push를 하는데
                    // /, * 순으로 오는 경우 
                    formula.push(operator.pop());
                    formula.push(operand.pop());
                    // operator.push(token);

                    console.log("formula ",formula);
                    result = calcFormula(formula);
                    console.log(result);

                    formula = [result];
                }

                // 추가
                operator.push(token);

                // if(getOperatorPriority(operator[operator.length - 1]) === 2){
                //     formula.push(operator.pop());
                //     formula.push(operand.pop());

                //     console.log("formula ",formula);
                //     result = calcFormula(formula);
                //     console.log(result);

                //     formula = [result];
                // }
            } else {
                operator.push(token);    

                if(getOperatorPriority(operator[operator.length - 1]) === 2 && formula.length !== 0){
                    formula.push(operator.pop());
                    formula.push(operand.pop());

                    console.log("formula ",formula);
                    result = calcFormula(formula);
                    console.log(result);

                    formula = [result];
                }
            }

            // 여기 else 처리해줘야하나?
            // 애초에 이 연산은 필요한가..?
            // operator.push(token);
        }

        console.log('operator', operator);
        console.log('operand', operand);
        console.log('formula', formula);
    }

    console.log('out of the loop');

    console.log('operator', operator);
    console.log('operand', operand);
    console.log('formula', formula);

    // 마지막 연산도 해줘야함.
    if(formula.length !== 0 && operator.length !== 0 && operand.length !== 0){
        formula.push(operator.pop());
        formula.push(operand.pop());

        console.log('formula', formula);

        result = calcFormula(formula);
    } else if(operator.length !== 0 && operand.length !== 0) {
        // formula가 비어있는 경우도 있다.
        formula.push(operand.pop());
        formula.push(operator.pop());
        formula.push(operand.pop());
        
        result = calcFormula(formula);
    }

    

    console.log('operator', operator);
    console.log('operand', operand);
    console.log('formula', formula);

    return result;
};

function getOperatorPriority(operator){
    switch(operator){
        case "+":
        case "-":
            return 1;

        case "*":
        case "/":
            return 2;
    }
}

function calcFormula(formula){
    const forwardOperand = parseInt(formula.pop());
    const operator = formula.pop();
    const backwardOperand = parseInt(formula.pop());

    if(operator === "+"){
        return forwardOperand + backwardOperand;
    }
    
    if(operator === "-"){
        return forwardOperand - backwardOperand;
    }

    if(operator === "*"){
        return forwardOperand * backwardOperand;
    }

    if(operator === "/"){
        // 주의! 음수 연산인 경우 floor 처리를 하면 소수점만 사라지는게 아니라 숫자가 변경됨.
        const result = forwardOperand / backwardOperand;

        // 연산 결과가 양수인 경우
        if(result >= 0){
            return Math.floor(result);
        } else {
            return Math.ceil(result);
        }
    }
}

예제로 주어진 3개만 분석을 하고 진행했는데 너무나도 잘못된 접근이었다.
주어진 테스트 케이스 3개를 통과하는데만 이정도의 코드가 나왔고,
아무리 처음엔 알고리즘 생각하지말고 손수 풀어보라지만,
각 케이스에 최적화된 코드를 에러를 마주할 때마다 수정할 뿐이었다.

예제 분석에서도 알 수 있지만, 케이스를 분석하면 할 수록 이전 케이스를 통과한 방법이 실패해버려
결과적으로 너무나도 이상한 결과가 나왔다.

올바른 예제 분석

틀려도 너무 틀려버린 필자의 분석력을 바로 잡기 위해 모든 생각을 리셋하고
후위 표현법에 대해서 알아보고자 한다.

후위 표현법은 두 숫자의 연산자를 뒤로 보내버린다.

1+2가 있다면 후위 표현법으로는 12+가 된다.
(1+2)*3-4가 있다면 12+3*4-가 된다.

두 표현식 사이의 관계는 연산자를 기준으로 한다.
연산자는 앞의 두 개의 숫자를 이용하여 연산을 진행한다.
+는 1과 2를 사용하여 연산하고,
*는 1과 2를 +로 연산한 결과값과 3을 연산한다.

이를 잘 기억하고 다시 예제를 분석해보자.

case 1)
["2","1","+","3","*"]

stack:
[2]
[2,1]
[2,1] <== (+) 연산자 발생! 2와 1을 +로 연산한다. 3이 된다.
[3]
[3,3] <== 3번 인덱스에 있는 3이 stack에 들어간 것이다. 헷갈리지 말자.
[3,3] <== (*) 연산자 발생! 3과 3을 *로 연산한다. 9가 된다.
[9] <== 모든 tokens를 순회했으므로 해당 값이 정답!

case 2)
["4","13","5","/","+"]

stack:
[4]
[4,13]
[4,13,5]
[4,13,5] <== (/) 연산자 발생! 13과 5를 /로 연산한다. 소수점 아래 자리는 버린다. 2가 된다.
[4,2]
[4,2] <== (+) 연산자 발생! 4와 2를 +로 연산한다. 6이 된다.
[6] <== 모든 tokens를 순회했으므로 해당 값이 정답!

case 3)
["10","6","9","3","+","-11","*","/","*","17","+","5","+"]

stack:
[10]
[10,6]
[10,6,9]
[10,6,9,3]
[10,6,9,3] <== (+) 연산자 발생! 9와 3을 +로 연산한다. 12가 된다.
[10,6,12]
[10,6,12,-11]
[10,6,12,-11] <== (*) 연산자 발생! 12와 -11을 *로 연산한다. -132가 된다.
[10,6,-132]
[10,6,-132] <== (/) 연산자 발생! 6과 -132를 /로 연산한다. -0이 된다.(0과 동일)
[10,-0]
[10,-0] <== (*) 연산자 발생! 10과 -0을 *로 연산한다. 0이 된다.
[0]
[0,17]
[0,17] <== (+) 연산자 발생! 0과 17을 +로 연산한다. 17이 된다.
[17]
[17,5]
[17,5] <== (+) 연산자 발생! 17과 5를 +로 연산한다. 22가 된다.
[22] <== 모든 tokens를 순회했으므로 해당 값이 정답!

다른 분의 solution

function evalRPN(tokens) {
  let stack = [];
  let ops = {
    '+': (a, b) => a + b,
    '-': (a, b) => a - b,
    '*': (a, b) => a * b,
    '/': (a, b) => a / b >= 0 ? Math.floor(a / b) : Math.ceil(a / b),
  };
  for (let t of tokens) {
    if (ops[t]) {
      let top = stack.pop();
      let second = stack.pop();
      stack.push(ops[t](second, top));
    } else {
      stack.push(Number(t));
    }
  }
  return stack.pop();
};

연산자를 담고 있는 ops를 활용하여 피연산자와 연산자 입력값을 구분하셨다.

피연산자라면 number 타입으로 변경한 뒤, stack에 저장한다.

연산자라면 stack에 저장된 피연산자들을 꺼낸다.
이 때, 후위 연산이므로 두 개의 숫자가 필요하여 pop()을 2회 진행한다.
또한, /의 경우 연산 순서도 매우 중요하기 때문에 후위 연산 규칙에 따라
먼저 stack에서 꺼내진 숫자를 연산자의 뒤 쪽에 배치한다.
즉, ops에서 b라는 파라미터에 활용하겠다는 뜻이다.
그 뒤에 이어서 꺼내진 숫자는 파라미터 a에 해당하겠다.
숫자를 꺼낸 뒤에는 두 숫자를 연산하여 그 결과를 stack에 다시 저장한다.

이후 연산자가 들어오게 되면, 앞서 한 번 연산된 숫자와 새롭게 입력된 숫자를 활용하여 연산을 진행한다.
이 과정을 계속해서 반복하는 것이다.

이렇게 연산을 마무리하면 하나의 숫자가 남게되는데 이 값이 최종 연산 값이 된다.

막상 다른 분들의 풀이를 보니 엄청 간단했던 문제였는데,
필자는 본인의 생각에 빠져서 다른 방법을 고안하지 못했다.
후위 표현법부터 제대로 이해하고 시작했어야했는데, 테스트 케이스를 보면서 동시에 이해하려고 한 것이
실패의 원인인 것 같다.