역폴란드 표기법

위키백과 ― 우리 모두의 백과사전.

역폴란드 표기법, 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

[편집] 관련 항목

  • 폴란드 표기법
  • 중위 표기법