프로그래밍/자료구조
자료구조 - [Tree]수식 트리
윈우
2016. 5. 16. 22:45
수식 트리
1. 수식 트리의 이해
- 중위 표기법은 사람이 보기에는 좋으나 컴퓨터가 인식하기 어려운 표기법이다.
- 후위 표기법을 이용한 수식 트리를 이용하면 쉽게 수식 연산을 할 수 있다.
(중위 표기법 -> 후위 표기법 -> 수식 트리 순)
*후위 표기법 이란 7+4*2-1 -> 74+2*1- 처럼 연산자를 숫자 뒤에 표현하는 것을 말한다.
2. 수식 트리 구성 방법
- root노드는 연산자로 구성한다.
- 피연산자는 연산자 노드의 하단 부터 구성한다.
- 수식 트리를 구성하기 위해선 스택을 이용해야 된다.
(이때 후위 연산자 표기법으로 반드시 변경해야 한다.)
1. 후위 표기법 순서대로 피연산자 노드를 스택에 Push한다.
2. 연산자 Node를 만나면 연산자 Node의 서브 Node로 스택의 들어있는 피연산자 Node를 오른쪽부터 연결시킨다.
3. 연결된 수식 트리를 다시 스택에 Push시킨다.
4. 이 후 다시 1번부터 같은 로직으로 진행한다.
2. 수식 트리 구현