열혈 자료구조 - 8-4 수식 트리의 구현

수식 트리의 이해

- 수식을 트리로 표현한 것

- 중위 표기법은 사람이 인식하기 좋지만 컴파일러는 그렇지 않음(우선 순위 때문)

- 컴파일러는 중위 표기법의 수식을 수식 트리로 재구성

int main()
{
	int result = 7 + 4 * 2 - 1;
}

- 수식 트리의 계산 과정

    -> 서브 트리를 계산하여 대체하고 이 과정을 반복

수식 트리를 만드는 순서

- 중위 표기법의 수식 => 후위 표기법의 수식 => 수식 트리

- 중위 표기법 => 후위 표기법으로 바꾸는 방법은 열혈 자료구조 - 6-4. 스택을 활용한 계산기 프로그램 구현(1) 에서 확인

- 수식 트리를 구현하기 위해서는 이진 트리와 스택의 개념이 필요

 

수식 트리를 만드는 개념

- 앞에서부터 순차적으로 진행

- 우선 피연산자를 저장할 스택을 하나 만듬

- 피연산자들은 그 스택에 push하여 저장

- 연산자를 만나면 스택에 저장된 피연산자를 pop하여 트리를 구성

- 이렇게 만든 트리를 스택에 저장하여 피연산자로 간주 => 루트 노드는 트리의 주소라는 개념을 이용하여 루트 노드의 주소 값을 저장

- 위 과정을 반복하여 트리를 구성

- 최종적으로 만들어진 트리도 다시 스택에 저장되어 있기 때문에 마지막에 꺼내서 연산해야 함

BTreeNode * MakeExpTree(char exp[])
{
	Stack stack;			// 피연산자를 담을 스택
	BTreeNode * pnode;

	int expLen = strlen(exp);
	int i;

	StackInit(&stack);		// 스택 초기화

	for(i=0; i<expLen; i++)
	{
		pnode = MakeBTreeNode();		// 노드를 생성

		if(isdigit(exp[i]))		// 피연산자라면...
		{
			SetData(pnode, exp[i]-'0');		// 아스키 값을 뺀 순수 숫자 값을 대입
		}
		else					// 연산자라면...
		{
			MakeRightSubTree(pnode, SPop(&stack));		// 먼저 오른쪽 자식 노드에 대입
			MakeLeftSubTree(pnode, SPop(&stack));
			SetData(pnode, exp[i]);				// 루트 노드를 연산자로 설정
		}

		SPush(&stack, pnode);			// 다시 스택에 넣음
	}

	return SPop(&stack);		// 마지막으로 만들어진 트리를 스택에서 꺼내서 반환
}

- 트리 계산

    -> 계산 함수를 재귀적으로 타게 함

int EvaluateExpTree(BTreeNode * bt)
{
	int op1, op2;

	if(GetLeftSubTree(bt)==NULL && GetRightSubTree(bt)==NULL)		// 단말노드인 경우(탈출조건)
		return GetData(bt);

	op1 = EvaluateExpTree(GetLeftSubTree(bt));
	op2 = EvaluateExpTree(GetRightSubTree(bt));

	switch(GetData(bt))
	{
	case '+':
		return op1+op2;
	case '-':
		return op1-op2;
	case '*':
		return op1*op2;
	case '/':
		return op1/op2;
	}

	return 0;
}

- 최종으로 저장된 트리를 전위 순회하면 전위 표기법을, 중위 순회는 중위 표기법을 그리고 후위 순회를 하면 후위 표기법을 얻을 수 있음

void ShowNodeData(int data)
{
	if(0<=data && data<=9)		printf("%d ", data);		// 피연산자면 숫자
	else				printf("%c ", data);		// 연산자면 문자
}

void ShowPrefixTypeExp(BTreeNode * bt)
{
	PreorderTraverse(bt, ShowNodeData);
}

void ShowInfixTypeExp(BTreeNode * bt)
{
	InorderTraverse(bt, ShowNodeData);
} 

void ShowPostfixTypeExp(BTreeNode * bt)
{
	PostorderTraverse(bt, ShowNodeData);
}