[자료구조] 10. 수식트리

공부한 날짜: 2021. 10. 20

 

수식트리: 수식을 표현하는 이진트리. 수식이진트리라고도 불림

 

규칙 (하나의 연산자가 두개의 피연산자를 가진다는 가정 하에)

1.  피연산자는 잎 노드이다.

2.연산자는 루트노드 또는 가지노드이다. 

 

수식트리는 가장 아래에 있는 하위수식트리(잎노드)부터 계산 결과를 병합해 올라가는 과정을 반복하여 계산을 수행.

 

-후위 표기식에 기반한 수식 트리 구축 알고리즘 

토큰은 하나씩만 읽어들여서 먼저 연산자인지 숫자인지 확인해야한다. 

 

1. 수식을 뒤에서부터 앞쪽으로 읽어나간다.

2. 수식에서 제일 마지막에 있는 토큰은 루트노드가 된다. 후위 표기식에서 가장 마지막에 있는 토큰은 항상 연산자이다.

(루트노드=연산자)

3. 수식에서 읽어낸 토큰이 연산자인 경우는 가지노드, 이 다음 토큰은 하나씩 왼쪽 자식 노드, 오른쪽 자식노드가 됨.

4. 수식에서 읽어낸 토큰이 숫자이면 잎노드이다.