[자료구조] 수식트리의 구현

 

수식트리를 구현하기 위해서는 배열에 있는 데이터를 뽑아내서 이진트리로 표현해야한다.

이때 활용할 것이 앞서 배운 STACK이다.

활용할 스택은 BTreeNode를 저장할 스택이다.
즉 우리는 배열에서 뽑아낸 데이터를(수 / 연산자 구별 없이)
모두 BTreeNode 로 만든다음 스택에 저장할 것이다.

이 부분이 가장 중요하다고 생각한다.

그냥 숫자 연산자로 스택에 저장했다가 PUSH POP할때마다 BTreeNode로 바꿔서 넣는 것보다
처음부터 BTreeNode로 보고 진행하는 것이 훨씬 깔끔하고 진행과정이 직관적이다.

 

위의 쟁반이 바로 BTreeNode 스택이다.

여기다 모든 데이터를 BTreeNode로 만들어 PUSH 연산을 수행한다.

만약 데이터가 연산자면 POP을 통해 STACK에서 두 개의 BTreeNode를 빼내고
해당 연산자 노드의 LeftSubTree와 RightSubTree로 만든다.
그리고 해당 연산자 노드를 다시 STACK에 PUSH연산으로 넣는다!

그럼 최종적으로 STACK에는 한 개의 BTreeNode만 있을 것이다!

과정은 아래와 같다!

 

실제로 최종 스택에는 한 개의 BTreeNode만 남아있지만, 실상 이 노드는 기존 수식 그 자체인 것이다!!!

---

[ 수식트리 구현 ]

BTreeNode* MakeExpTree(char exp[]) {
	Stack stack;
	BTreeNode* pnode;

	int expLen = strlen(exp);
	
	for (int i = 0; i < expLen; i++) {

		pnode = (BTreeNode*)malloc(sizeof(BTreeNode));

		if (isdigit(exp[i])) {
			SetData(pnode, (int)exp[i]);
		}
		else {
			MakeRightSubTree(pnode, stack.pop());
			MakeLeftSubTree(pnode, stack.pop());
			SetData(pnode, exp[i]);
		}
		stack.push(pnode);
	}
	return stack.pop();
}

 

---

[ 수식트리 계산 ]

int EvaluateExpTree(BTreeNode* bt) {
	if (bt == NULL) return 0;

	if (isdigit(GetData(bt))) { return GetData(bt); }
	else {
		int op1 = EvaluateExpTree(GetLeftSubTree(bt));
		int op2 = EvaluateExpTree(GetRightSubTree(bt));

		if (GetData(bt) == '+') { return op1 + op2; }
		else if (GetData(bt) == '-') return op1 - op2;
		else if (GetData(bt) == '*') return op1 * op2;
		else if (GetData(bt) == '/') return op1 / op2;
	}
}

 

구현과 계산 모두 이진트리의 재귀적 특징을 활용하고 있다.

이진트리는 무슨 귀? 재귀 ㅇㅇ