2012.01.27 15:44

수식을 입력하면 계산해주는 프로그램들을 보면서 수식을 어떻게 처리하는 것인지 궁금했는데 알고리즘 책[1]에서 그 방법을 찾았다.

우리가 평소에 사용하는

1 + 2 / 33 - 9 * 13

같은 수식 표기법은 중위 표기법 (Infix Notation)이라고 한다.

이와는 달리

1 2 33 / + 9 13 * - 

같은 형식의 수식 표기법도 있는데 이를 후위 표기법 (Postfix Notation)라고 한다.

위 수식에서 중위 표기법에서 후위 표기법으로 변하는 규칙을 보면 후위 표기법이 스택 알고리즘으로 이루어져 있음을 확인할 수 있다.

피연산자를 스택에 쌓다가 연산자가 나오면 피연산자 스택에서 두 개를 꺼내서 연산을 처리하고, 다시 스택에 집어넣는 규칙이 보이는가?

간단한 알고리즘이므로 후위 표기법의 계산은 프로그래밍을 통해 구현하기 쉽다.

따라서 중위 표기법을 입력 받았을 때 이를 처리하는 프로그램을 만들기 위해서는 중위 표기법에서 후위 표기법으로 변환하고, 이렇게 얻은 후위 표기법을 계산하도록 작성하면 된다.


이걸 구현하기 위해 참 먼길을 돌아왔다.

일단 위에 레퍼런스로 달아놓은 저 책의 설명과 인터넷에서 찾은 설명들이 모두 대체로 부실했다.

그런데 거기에 사용된 예시들 또한 모든 상황을 표현하지 못하고 있어서 예시들로부터 제대로 된 규칙을 다시 추정하기도 힘들었다.

심지어 잘못된 예시를 달아놓은 글이 버젓이 1순위로 검색되는 문제도 있었다.
(현재 구글에 infix postfix로 검색하면 가장 처음 뜨는글  http://makebob.tistory.com/18 은 8번에서 잘못된 예시를 들고 있다.)


이 알고리즘을 다시 정리한 것은 다음과 같다.
0. 우선순위는 '(' < '+' = '-' < '*' = '/' 순이다.
1. 입력받은 중위 표기식에서 한 글자씩 읽어들인다.
2. 읽어들인 글자가 피연산자이면 후위 표기식에 적는다.
3. 읽어들인 글자가 연산자이면
3-1. 왼쪽 괄호일 경우 스택에 넣는다.
3-2. 오른쪽 괄호일 경우 왼쪽 괄호를 꺼낼 때까지 스택에서 하나씩 꺼내 후위 표기식에 적고 왼쪽 괄호를 뽑으면 버리고 끝낸다.
3-3. 나머지 사칙 연산자의 경우 그 연산자가 스택의 최상위 노드보다 우선순위가 높을 때까지 스택의 최상위 노드를 꺼내 후위 표기식에 적는다. 현재 연산자가 스택의 최상위 노드보다 우선순위가 높아졌다면 스택에 넣고 끝낸다. 
예 ) 스택 : * + * /, 읽어들인 연산자 : * 일 경우 스택에서 / * 를 차례로 꺼내 후위 표기식에 적고 *를 스택에 넣는다.
      최종 스택 : * + *, 후위 표기 : / *
4. 1~3 을 반복해서 중위 표기식을 모두 읽어들였다면 스택에 있는 연산자를 최상위 노드부터 꺼내 후위 표기식에 적는다.

예 ) 3+7/2*4-2/5+((2+3/4)/(2+1))
-> 3 7 2 / 4 * + 2 5 / - 2 3 4 / + 2 1 + / +


소스코드

Calculator.zip



[1] 박상현, '뇌를 자극하는 알고리즘', 한빛미디어, pp.89-103, 2009.



Posted by MayTree