- 작성자 : 이승철
역 폴란드 기법(reverse polish notation)은 이 기법을 고안해낸 폴란드의 수학자.. 루카..(아, 갑자기 이름이 생각 안 나네요..--;). 암튼 폴란드의 수학자가 고안했다고 해서 역 폴란드 기법이라고 합니다.
전에 트리구조를 공부할 때 트리를 순행하는 방법에는 preorder, inorder, postorder 가 있다고 했습니다. 이 역 폴란드 기법은 postorder를 이용하게 됩니다. 그래서 역 폴란드 기법을 후위 기법(postfix notation)이라고도 합니다.
일반적으로 우리는 식을 쓸 때,
3 + 1 + 2 * 4 - 3 / 5
이런 식으로 식을 씹니다. 이것은 inorder로 순행을 한 경웁니다. 만약 이걸 역 폴란드 기법으로 하면,
3 1 + 2 4 * + 3 5 / -
이렇게 됩니다. 우리가 보기에는 알아보기 힘들죠? 그러나 컴퓨터한테 계산을 시킬 때는 이렇게 변환시키는게 훨씬 편해집니다. 왜냐하면 이것은 다음과 같은 말로 표현할 수 있기 때문에 "3과 1을 더한 것에 2와 4를 곱한 것을 더하고 3을 5로 나눈 것을 뺀다." 즉, 그냥 순서대로 쭈~욱 읽어 나가면 되어서 프로그램을 짤 때는 그냥 순서대로 받으면서 처리해 나가면 됩니다.
그 방법은 다음과 같습니다.
일단 각 요소에 다음의 표같이 우선순위를 설정합니다.
|
우선순위(priority) |
요소(factor) |
|
1 |
+, - |
|
2 |
*, / |
|
3 |
피연산자(operand) |
Stack1, Stack2를 만들고 다음과 같이 한다.
왼쪽에서부터 한 개의 요소씩 읽으면서 다음을 반복한다.
begin
while 읽은 요소의 우선순위 <= Stack1 가장 위에 있는 요소의 우선순위
begin
Stack1 가장 위에 있는 요소를 Pop해서 Stack2에 Push한다.
읽은 요소를 Stack1에 Push한다.
end;
end;
Stack1에 남아있는 요소들을 Pop해서 Stack2에 Push한다.
이 알고리즘을 실행하게 되면 다음과 그림과 같이 됩니다.
이제 Stack2에 있는 것을 빼내면
3 1 + 2 4 * + 3 5 / -
이렇게 됐습니다. 이제는 이것을 이용해서 계산을 해야겠죠? 이걸 계산할 때는 파싱(Parsing)이란 방법을 씁니다. Parsing은 '분석'이란 뜻입니다. 그러니까 주어진 문자열을 분석해서 계산을 한다는 것이죠. 위에서도 언급되었지만 후위기법을 쓰면 그냥 읽으면서 계산을 해 나갈 수 있습니다. '3과 1을 +해서 2와 4를 *한 것을 +하고 3과 5를 /한 것을 -한다.' 이런식으로 표현할 수 있기 때문이죠. 읽어들인 요소가 피연산자(operand)이면 저장해 뒀다가 연산자(ope)가 나오면 그 저장해둔 피연산자(operand)를 가지고 연산을 하면 되는 것이죠. 그 저장해두는 곳을 t라는 스택으로 하죠. 그 순서는 다음과 같습니다.
Stack2이 완전 빌때까지 다음을 반복한다.
begin
Stack2에서 요소하나를 끄집어 낸다.
if 끄집어낸 요소가 피연산자 then
t에 그 요소를 집어 넣는다.
if 연산자 then
t에 최상위 요소(t[p])와 그 바로 아래 있는 요소(t[p-1])를 계산하여 t[p-1]에 넣는다.
end;
그런데 이렇게만 해서는 괄호가 있는 식은 계산 할 수 없습니다. 괄호까지 처리해내는 프로그램은 직접 짜보시길
바랍니다. 힌트를 드리자면 '('의 우선순위를 가장 높은 수로 놓고 ')'의 우선순위를 가장 낮은 수로 놓으면 상당히
쉬워집니다. 또 괄호는 후위기법으로 표현할때 나올 필요 없습니다. 그러니까 예를 들어,
3 + (1 + 2) * (4 - 3) / 5
이런게 있다면
3 1 2 + 4 3 - * 5 / +
이렇게 되는 것입니다. "3에 1과 2를 더한 것을 4에서 3을 뺀 것을 곱하고 5로 나눈 것을 더한다." 이렇게 됩니다. 그럼 직접 코딩해 보시길 바랍니다. 그럼 이만.