가. 평가하는 함수:

우선 다른것을 제외하고

((5 + 3) * 7) 과 같은 이러한 수식이

트리로 만들어졌다고 생각하자


이는 최상위 루트 '*' 와 양갈래 가지로 뻗어나간 작은 수식들로 이루어진다.

"1. 트리계산기 (concept)" 글의 그림을 잘 보면

'*' 또는 '+' 같은 "루트" 들은 양옆 가지가 차있다.

'숫자' 들은 양옆 가지가 비어있다.

트리가 정확하게 만들어졌다고 가정하면


작성하려는 평가함수는

만일 숫자를 만나면 양가지로 뻗어나갈수 없으므로(비어있으니까)

그냥 숫자 자체를 반환한다.

 만일 문자를 만나면 양가지 각각을 이용하여 그 문자에 해당하는 연산을 한다.


의사코드로 작성해보면

EVAL (input ROOT)
        if (숫자?)
             then return 숫자
        else
             if('+' ?)
                  then return EVAL(left) + EVAL(right)
             if('*' ?)
                  then return EVAL(left) * EVAL(right)
             등등등...


이러한 식으로 하면 최상위루트를 입력으로 넣으면 

이 잘 만들어진 트리를 어떻게든 돌고 돌아서 결국은 값을 반환하게 되는것이다.


여기서 중요한점은

숫자인 경우  (NULL, 숫자, NULL) 이러한 형태이고

함수인 경우 (수식1, 함수, 수식2) 이러한 형태로 된다는 점이다.


나. 수식의 표현방법


이진트리를 순회하는 방법에는 3가지 방법이 있다

preorder, inorder, postorder 

그리고 연산자의 위치에 따라서 

prefix, infix, postfix 라는 말도 있다.

위 두개는 일맥상통 한다. 왜냐면

수식을 이진트리로 뽑아냈기 때문이다.

하지만

수식을 평가할때 하는 순회방법은 어떻게 되든 상관없다.

수식이 트리구조로 만들어지기만 한다면 

재귀순환한 다음에는 값이 얻어지기 때문이다.

트리구조에서 inorder로 순회하며 찍어보면  infix 방식으로 수식이 표현된다.

preorder로 돌면 prefix 방식으로 표현된다.

postorder로 돌면 postfix 방식으로 표현되는 것일 뿐이다. (2스택 알고리즘에서 쓰이는)


단지 입력값으로 넣어야 할 수식의 표현방법에 차이가 생긴다.

(pre, in, post) 이렇게 세 요소가 있을때

트리를 만들때 세가지요소중 pre를 루트로 읽고 나머지로 양가지를 만든다면 

prefix로 수식을 작성하여 입력해야 한다  (lisp, scheme 과 같은)

예)  * + 5 3 7 , (* (+ 5 3) 7)

in을 읽고 루트로 잡고 나머지를 가지로 만들면 흔히 쓰는

예) ((5 + 3) * 7)

post인 경우는 

예) 3 5 + 7 *

perfix 나 postfix같은 경우 잘 쓰면 괄호가 굳이 필요하지는 않다.

하지만 infix같은경우 괄호가 꼭 필요하게 된다.

복잡한 수식을 만들게 되면 나중엔 괄호지옥이 펼쳐질 것이다.



많은 예제들이 postfix를 이용하여 중첩된 수식을 평가하는

방법을 보여주는데

나는 그냥 infix 수식을 입력하도록 선택하였다.


어차피 트리 차원에서 계산이 이루어지기도 하고

남들이 안해본? 방법,, 무식하더라도 나만의 프로그램을 짜고 싶은 마음에


infix를 선택하였고 

계산기 이름이

infix only calculator 이다.





Posted by 멍충한아싸

댓글을 달아 주세요