CH 8 - 4 수식 트리의 구현

이 게시글은 윤성우 선생님의 자료구조 강의를 수강 후 나름대로의 내용 정리를 한 것임을 미리 밝힙니다.
스스로의 복습을 위해 작성한 글이므로 심층있는 학습을 위해서는 책의 구매 및 강의수강을 권장합니다.

(1) 수식 트리의 이해

지금까지 본 수식을 표기하는 법 - 중위 표기법(infix notation), 후위 표기법(postfix notation) 등
수식 트리도 수식을 표기하는 하나의 방법
즉, 수식트리가 중위 표기, 후위 표기, 전위 표기 등에 종속되는 것은 아니다.

중위 표기법의 수식은 사람이 인식하기 좋은 수식이다.
컴퓨터의 인식에는 어려움이 있다.
그래서 컴파일러에는 중위 표기법의 수식을 수식 트리로 재구성한다.
-> 연산의 우선순위가 높은 연산을 높은 레벨에 두면 되겠다.

(2) 수식 트리의 계산 과정

(3) 수식 트리를 만드는 절차

스택은 앞서 만들어놓은 걸 쓰면 되며 이진트리를 구성하는 도구도 약간의 수정만 거쳐 사용하면 된다.

(4) 수식 트리의 구현과 관련된 헤더파일

#include "BinaryTree2.h"

BTreeNode* MakeExpTree(char exp[]); // 수식트리의 노드 구성이자 수식 트리 구성 (나는 노드가 하나하나 트리를 나타낸다는 것은 알겠으나 그래도 결국 하나하나는 노드이니 수식트리의 노드 구성이란 표현이 더 알맞을 갓 같아서 수식트리의 노드 구성이라고 우선적으로 서술하였다.)

위 함수는 수식 트리의 루트 노드를 만들고 루트 노드의 주소값을 반환한다.
int EvaluateExpTree(BTreeNode* bt); // 수식트리 계산
void ShowPrefixTypeExp(BTreeNode* bt); // 전위 표기법 기반 출력
void ShowInfixTypeExp(BTreeNode* bt); // 중위 표기법 기반 출력
void ShowPostfixTypeExp(BTreeNode* bt); // 후위 표기법 기반 출력

**전위, 중위, 후위 순회하여 출력 시** 각각 전위, 중위, 후위 표기법의 수식이 출력된다
또한 MakeExpTree함수가 제대로 만들어졌는지 확인도 가능하다.

(5) 후위 표기법의 수식을 기반으로 수식 트리 구성하기

1) 고민의 흔적

2) 강의

1. 피연산자 2개는 스텍에 저장
2. 연산자가 등장하면 연산자를 부모 노드, 피연산자 2개를 자식 노드로 하여 트리 하나 만들기
   3. 이 하나의 서브 트리는 하나의 피연산자가 되므로 서브트리의 <루트 노드의 주소>를 스텍에 저장
3. 위의 과정 반복

(6) 구현

내가 구현한 소스파일

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "BinaryTree2.h"
#include "ExpressionTree.h"
#include "ListBaseStack.h"

BTreeNode* MakeExpTree(char* exp)
{
	Stack stack;
	Stack* pstack = &stack;
	StackInit(pstack);
	int length = strlen(exp);
	int i;
	BTreeNode* temp;
	for (i = 0; i < length; i++)
	{
		temp = MakeBTreeNode();
		if (temp == NULL)
		{
			printf("트리를 만들 수 가 없어");
			exit(-1);
		}
		SetData(temp, exp[i]);
		if (exp[i] > 47)
		{
			SPush(pstack, temp);
		}
		else
		{
			MakeRightSubTree(temp, SPop(pstack));
			MakeLeftSubTree(temp, SPop(pstack));
			SPush(pstack, temp);
		}
	}
	return SPop(pstack);
}

int Evaluate(BTreeNode* bt)
{
	if (bt == NULL) return 0;
	else
	{
		if (bt->data > 47) return bt->data - 48;
		else if (bt->data == '+') return Evaluate(bt->left) + Evaluate(bt->right);
		else if (bt->data == '-') return Evaluate(bt->left) - Evaluate(bt->right);
		else if (bt->data == '*') return Evaluate(bt->left) * Evaluate(bt->right);
		else return Evaluate(bt->left) / Evaluate(bt->right);
	}
}

변수가 필요없는
MakeBTreeNode를 괄호를 치지 않아서
temp = 함수 포인터가 되어 함수포인터에든 data라는 구조체 변수가 없으니
당연히 data를 쓸 수가 없어서 쓰기엑세스 위반 에러가 뜬다.

이걸로 40분을 고민했다 후... 좋은 공부가 되었다고 생각한다....

(7) 실행한 메인함수의 코드와 실행결과