수식트리의 구현 #1

공부한 이진트리로 수식트린을 구현해보자

 

앞서 공부했던 계산기에서 후위변환법을 가지고 온 다음 그 식을 가지고 TREE로 구현한다.

 

책에서는 다시 스택을 활용해서 만드는데

 

그냥 다 트리에 넣어서 만들어보았다.

 

트리로 변환 할 식 

->51-8/(3*4-4)-20

 

우선 위 식을 후위변환표현으로 변경한다.

->51 8 3 4 * 4 - / - 20 -

 

여기서 포인터는 마지막 연산자인 -를 가리키고 있다.

 

이제 트리에 다 집어 넣는다

 

트리에 집어 넣을 때  다음과 같은 규칙을 지키며 집어 넣는다.

 

1. 연산자가 나오면 왼쪽에 피 연산자가 나오면 오른쪽에 넣는다.

 

2. 피 연산자노드는 자식 노드를 생성 할 수 없다.

 

위 규칙을 지키며 트리를 만들면 다음과 같은 트리가 만들어진다.

 

 

51 8 3 4 * 4 - / - 20 -

 

빨간색은 모두 트리에 들어갔으나 51, 8은 아직 트리에 들어가지 않았다. 

 

51과 8은 tree가 다시 root 노드로 올라가면서 자식 노드가 NULL인지 확인후 확인 되었으면 넣어주면 된다. 

 

연산은 왼쪽에서 오른쪽으로 계산 되므로 10번과 11번을 채울 때는 Left <-> right를 바꿔 줘야 한다.

(RightNode Operator LeftNode 로 연산된다.)

 

8을 채울 때

 

 

51을 채운 후 최종 수식 이진 트리

 

 

위 트리에서 아래에서 부터 연산자에 맞게 계산하면서 올라오면 된다.