수식트리(Parse Tree)

Terminal node : 끝인 노드

Non-Terminal node : 끝이 아닌 노드

괄호의 식을 기준으로 operator 노드 양쪽에 operand 를 배치해 놓으면

위의 그림처럼 수식노드가 만들어지는데 이때의 이점은

순회 방법에 따라 순회 방식에 따라 전위,중위,후위의 수식구성을 만들 수 있다는 것

만약 위의 수식이 후위수식으로 표기 되어 있었다면

A B + CD - * E / F G * +

다음을 통해 Parse Tree 를 구성할 수 있다

1. Operand 는 Node를 만들어 Stack 에 Push

2. Operator 느 Node를 생서하여

1. Stack 에서 Pop 한 노드를 오른쪽 자식으로 하고

2. stack 에서 또 Pop 한 노드를 왼쪽자식으로 하고

3. Operator Node 를 Stack 에 Push

3. Stack 에 마지막으로 남은 노드가 Root 이다.

손으로 계산시

전위,중위,후위 에 대한 수식을 뽑아올때 Parse Tree 로 수식을 괄호 우선 순위에 맞게 트리로 구성 한후

순회 방식에 따라 수식을 구성하면 되다