Menu

문서정보

Reverse Polish notation

역폴란드 표기법(Reverse Polish notation - RPN) 혹은 후위 표기법은 연산자(operator)를 연산대상(operands)의 뒤에 쓰는 연산 표기법이다. 예를 들어 "3 + 4"의 경우 "3 4 +"로 표기한다. 연산자가 두 개 이상이라면 연산자 바로 뒤에 다음번 연산대상을 표기한다. "3 - 4 + 5"가 있다면 "3 4 - 5 +"가 된다.

곱하기와 나누기 같이 연산자의 위치에 따라 달라지는 계산이 있다고 가정해보자. 예컨데 "3 - 4 * 5"는 "3 - (4 * 5)"로 표기 할 수 있지만 계산 결과는 전혀 다르다. RPN에서 전자는 "3 4 - 5 *"로 후자는 "3 4 5 * -"로 표기 할 수 있다.

이처럼 역폴란드 표기법을 사용하면, 우선순위 쓸 필요 없이 연산자와 연산대상만으로 수식을 만들 수 있다. 특히 역폴란드 표기법은 스택머신을 이용하면 되기 때문에, 컴퓨터를 이용한 계산에 유리한 측면이 있다. 다만 사람이 읽기에는 불편하기 때문에 일상생활에서는 접할 기회가 으며, 컴퓨터 프로그램 내부에서 주로 사용한다.

(3 + 5) * (4 + 2)를 역폴란드 표기법으로 쓰면 "3 5 + 4 2 + *"이다. 눈으로 봐서는 이해하기가 쉽지 않을 거다. 이해를 돕기 위해서 스택머신을 만들어봤다.

입력 액션 스택 설명
3 연산대상 3 스택에 밀어 넣는다.
5 연산대상 3 5 스택에 밀어 넣는다.
+ 연산자 8 연산대상 3,5를 꺼낸다음 + 연산을 하고 그 결과를 스택에 밀어 넣는다.
4 연산대상 8 4 스택에 밀어 넣는다.
2 연산대상 8 4 2 스택에 밀어 넣는다.
+ 연산자 8 6 연산대상 4,2를 꺼내서 + 연산을 하고 그 결과를 스택에 밀어 넣는다.
* 연산대상 48 연산대상 8,6을 꺼내서 * 연산을 하고 그 결과를 스택에 밀어 넣는다.
실제 작동하는 코드는 항목을 참고.