[ch 08-4] 수식 트리의 구현_1(개념)

[수식 트리의 개념]

- 전위/중위/후위 표기법과 같은 하나의 수식을 표현하는 방식

■ 그림(수식 트리의 예)

※ 수식 예: 9 – 6 / 2 + 4

■ 그림(수식 트리의 연산 과정)

[수식 트리의 구현 과정]

- 중위 표기법의 수식을 입력 받음 → 수식 트리로 표현

- 연산자, 피연산자는 스택으로 관리

[수식 트리의 표현]

- 후위 표기법의 수식에서 앞쪽에 등장하는 피연산자와 연산자로 트리의 하단을 만들고, 계속해서 뒤 (피)연산자들을 그 위로 

  계속해서 구성해 나감

■ 그림(수식 트리의 구성 과정)

- 후위 표기법 수식 '8 2 - 2 /'를 스택을 활용하여 수식 트리로 구성

- 수식에서 조회된 문자가 '피연산자'이면 스택에 넣음

- 위와 동일

- 수식에서 조회된 문자가 '연산자'이면 스택에 저장된 피연산자를 꺼내어 자식 노드로 연결

- 먼저 꺼내진 피연산자 '2'는 오른쪽 자식노드로 연결

- 다음에 꺼내진 피연산자 '8'은 왼쪽 자식노드로 연결

- 완성된 수식 트리는 다시 스택에 넣음

- 다시 수식을 조회과정을 반복

- 수식에서 '연산자'가 조회되면 또 스택에서 피연산자(트리도 해당) 꺼내어 자식 노드로 연결

- 더 이상 수식에 문자가 없으면 종료

[정리]

- 수식에서 문자를 하나씩 조회할 때 피연산자는 무조건 스택으로 옮김

- 연산자가 조회되면 스택에서 2개의 피연산자를 꺼내어 자식 노드로 연결

- 이 때, 먼저 꺼낸 피연산자는 오른쪽 자식이고 나중에 꺼내진 피연산자는 왼쪽 자식으로 연결됨

- 자식 노드를 연결해서 만들어진 트리는 다시 스택으로 옮김