역폴란드 표기법
위키백과 ― 우리 모두의 백과사전.
역폴란드 표기법, RPN(reverse Polish notation)은 연산자를 연산 대상의 뒤에 쓰는 연산 표기법이다. 후위 표기법(後位 -)으로도 부른다.
예를 들어, 중위 표기법에서 "1 + 2"와 같은 의미를 지니는 식은 역폴란드 표기법으로는
1 2 +
가 된다. 또한, (2 + 3) * 4을 역폴란드 표기법으로 쓰면 다음과 같다.
2 3 + 4 *
[편집] 특징
이와 같은 방식은 수식을 계산할 때 특별한 변환이 필요없이, 수식을 앞에서부터 읽어 나가면서 스택에 저장하면 된다는 장점이 있다. 또한, 중위 표기법에서는 연산자의 순서가 혼동될 수 있는 반면에 역폴란드 표기법에서는 그러한 문제점이 발생하지 않는다.
[편집] 예제
(3 + 5) * (4 + 2)를 역폴란드 표기법으로 쓰면 다음과 같다.
3 5 + 4 2 + *
이 식은 다음과 같이 계산된다.
| 실행 | 스택 |
|---|---|
| 먼저 3이 스택에 들어간다. |
3 |
| 5가 스택에 들어간다. |
5 3 |
| +가 입력되면 스택에서 두 수를 꺼내 더한 후 스택에 넣는다. |
8 |
| 4 |
4 8 |
| 2 |
2 4 8 |
| + |
6 8 |
| *. 두 수를 꺼내 곱한 값을 스택에 넣는다. |
48 |
[편집] 관련 항목
- 폴란드 표기법
- 중위 표기법
