Note
후위 표기법(RPN) 은 연산자가 피연산자 뒤에 오는 표기입니다. 스택으로 왼쪽부터 토큰을 보며 숫자는 넣고, 연산자면 스택에서 두 개 꺼내 계산한 뒤 결과를 다시 넣으면 됩니다.
후위 표기법이란?
- 중위 표기: 우리가 쓰는 형태 —
2 + 1,(2 + 1) * 3 - 후위 표기(Reverse Polish Notation): 연산자가 피연산자 뒤에 옴
2 1 +→ 2와 1을 더함2 1 + 3 *→ (2+1)을 먼저 계산한 뒤 3을 곱함 → 9
괄호가 없어도 토큰 순서만으로 계산 순서가 정해지므로, 스택 하나로从左到右 한 번만 훑으면 됩니다.
핵심 아이디어: 스택
- 숫자 토큰 → 스택에 push
- 연산자 토큰 → 스택에서 두 개 pop (먼저 나온 게 왼쪽 피연산자, 나중에 나온 게 오른쪽 피연산자)
→ 연산 적용 후 결과를 스택에 push
마지막에 스택에 한 개만 남고, 그 값이 수식의 결과입니다.
연산자별 동작
| 연산자 | 계산 | 비고 |
|---|---|---|
+ | num0 + num1 | |
- | num0 - num1 | 순서: 먼저 pop한 게 num1, 그 다음 pop한 게 num0 → num0 - num1 |
* | num0 * num1 | |
/ | num0 / num1 | 0 방향으로 버림 (truncate toward zero). Python: int(num0/num1) |
나눗셈: 0 방향 버림
- C/Java 스타일: 나눗셈 결과를 0 쪽으로 내림 (양수면 내림, 음수면 올림)
- Python에서
//는 음수에서 바닥(floor) 이라 다름
예:-1 // 2 == -1(0 방향이 아님) - 따라서
int(num0 / num1)을 쓰면 0 방향으로 버린 정수와 같아짐
알고리즘 흐름
- 빈 스택
nums tokens를 왼쪽부터 순회:- 숫자면
int(token)으로 바꿔 push - 연산자면 pop 두 번 → num1, num0 (순서 주의) → 연산 후 결과 push
- 숫자면
- 반복 끝나면
nums[0]반환
예시: [“2”,“1”,”+”,“3”,”*“]
| 토큰 | 동작 | 스택 |
|---|---|---|
| 2 | push | [2] |
| 1 | push | [2, 1] |
| + | pop 1, 2 → 2+1=3, push | [3] |
| 3 | push | [3, 3] |
| * | pop 3, 3 → 3*3=9, push | [9] |
→ 9 반환
요약
| 항목 | 내용 |
|---|---|
| 후위 표기 | 피연산자 먼저, 연산자 나중 |
| 자료구조 | 스택 (숫자 push, 연산자면 pop 2번 후 계산 결과 push) |
| 나눗셈 | 0 방향 버림 → int(num0/num1) |