역폴란드 표기법
역폴란드 표기법(RPN, reverse Polish notation) 또는 후위 표기법(후치 표기법)(後位 -, postfix 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 |