난이도: 중간 (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 기반 후위 표기식 계산
후위 표기식은 괄호 없이도 계산 순서가 명확하다. 이를 스택으로 쉽게 처리할 수 있다.
핵심 아이디어:
- 숫자는 스택에 push한다.
- 연산자가 나오면 스택에서 두 개의 숫자를 pop한다. 첫번째 pop -> 두번째 피연산자, 두번째 pop ->첫번째 피연산자.
- 첫번째, 두번째 피연산자와 연산자를 이용하여 연산을 수행하고, 그 결과를 다시 스택에 push한다.
- 모든 토큰을 처리한 후, 스택의 유일한 값이 최종 결과가 된다.
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 변환 → 스택 계산은 핵심 패턴으로 자주 등장한다.