연습 문제 2.3: RPN 계산기

이 연습 문제에서는 역폴란드 표기법(Reverse Polish Notation, RPN) 계산기를 작성해보자. RPN은 연산자가 피연산자 뒤에 오는 수학 표기법으로, 연산자를 두 피연산자의 중간에 배치하고 우선 순위 표기를 위해 괄호를 사용하는 대신 피연산자 뒤에 연산자를 배치하는 수학적 표기법이다. 역폴란드 표기법은 프리드리히 L. 바우어(Friedrich L. Bauer)와 에츠허르 W. 데이크스트라(Edsger Wybe Dijkstra)가 1960년대 초에 식의 평가에 필요한 컴퓨터 메모리의 양을 줄이기 위해 각각 독자적으로 개발한 식이다. 몇 가지 예를 살펴보자.

val res = calc("4 5 +") // 9.0
val res = calc("6 2 /") // 3.0
val res = calc("5 6 2 1 + / *") // 10.0
val res = calc("2 5 * 4 + 3 2 * 1 + /") // 2.0

알고리즘은 다음과 같이 작동한다. 계산은 숫자 목록(피연산자)으로 시작하는 연산식과 빈 스택으로 시작한다. 연산식의 맨 왼쪽에서 원소를 찾는 것으로 계산을 시작한다. 원소가 숫자인 경우 이를 스택에 넣는다. 원소가 연산이면 스택에서 피연산자 두 개를 꺼내서 연산을 적용한 다음, 결과를 다시 스택에 넣는다. 이 연습 문제를 풀려면 이전 연습 문제에서 작성한 함수형 스택 코드에서 시작하는 것이 가장 좋다.