150. Evaluate Reverse Polish Notation

난이도: 중간 (Medium)

링크: LeetCode 150

풀이 날짜: 2025/10/22

 

1. 문제 이해

이 문제는 후위 표기식(Reverse Polish Notation, RPN) 을 계산하는 문제다. RPN에서는 연산자가 피연산자(숫자) 뒤에 위치한다.

 

예를 들어

• ["2", "1", "+", "3", "*"] → (2 + 1) * 3
• ["4", "13", "5", "/", "+"] → 4 + (13 / 5)
• ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] → 결과는 22

 

2. 접근 방식 — Stack 기반 후위 표기식 계산

후위 표기식은 괄호 없이도 계산 순서가 명확하다. 이를 스택으로 쉽게 처리할 수 있다.

 

핵심 아이디어:

1. 숫자는 스택에 push한다.
2. 연산자가 나오면 스택에서 두 개의 숫자를 pop한다. 첫번째 pop -> 두번째 피연산자, 두번째 pop ->첫번째 피연산자.
3. 첫번째, 두번째 피연산자와 연산자를 이용하여 연산을 수행하고, 그 결과를 다시 스택에 push한다.
4. 모든 토큰을 처리한 후, 스택의 유일한 값이 최종 결과가 된다.

 

3. 풀이 코드

/**
 * @param {string[]} tokens
 * @return {number}
 */

function calculate(a, b, token) {
  switch (token) {
    case '+': return a + b;      
    case '-': return a - b;
    case '*': return a * b;
    case '/': return Math.trunc(a / b); // 소수점 버림 (0 쪽으로)
  }  
}

var evalRPN = function(tokens) {
  const stack = [];

  for (const token of tokens) {
    if (['+', '-', '*', '/'].includes(token)) {
      const second = stack.pop();
      const first = stack.pop();
      const result = calculate(first, second, token);
      stack.push(result);
    } else {
      // 문자열 타입의 숫자이기 때문에 추후 연산을 위해 숫자 타입으로 변환하여 stack 에 넣는다.
      stack.push(Number(token)); 
    }
  }

  return stack[0];
};

Math.trunc 메소스가 존재한다는 걸 알고 있는 것이 중요하다. 소수점이 있을때, 음수든 양수든 0 방향으로 소수점을 버린다.

실행 예시

단계	토큰	스택 상태	설명
1	“2”	[2]	숫자 push
2	“1”	[2, 1]	숫자 push
3	“+”	[3]	2 + 1 = 3
4	“3”	[3, 3]	숫자 push
5	“*”	[9]	3 × 3 = 9
결과		9	최종 결과

복잡도 분석

구분	복잡도	설명
시간 복잡도	O(N)	모든 토큰을 한 번씩만 처리
공간 복잡도	O(N)	스택에 최대 N개의 숫자 저장 가능

 

4. 핵심 요약 및 정리

개념	설명
문제 유형	Stack, Expression Evaluation
핵심 아이디어	숫자는 push, 연산자는 pop 두 개 → 계산 후 push
시간 복잡도	O(N)
공간 복잡도	O(N)
포인트	연산 순서가 명확하기 때문에 괄호 없이 계산 가능

이 문제는 스택의 가장 대표적인 응용 중 하나로, 실제 컴파일러나 계산기 프로그램의 내부 로직에서도 이 방식이 사용된다. 연산의 순서가 복잡한 중위 표기식을 다루는 문제에서도, RPN 변환 → 스택 계산은 핵심 패턴으로 자주 등장한다.