Reverse Polish notation

Recommanded Free YOUTUBE Lecture: <% selectedImage[1] %>

yundream
2016-12-07
2016-12-07
159740

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을 꺼내서 * 연산을 하고 그 결과를 스택에 밀어 넣는다.

실제 작동하는 코드는 항목을 참고.

Search For:

BY TAGS