수식 트리의 구현(3)

08-4. 수식 트리(Expression Tree)의 구현 ③

앞에서 우리가 한 부분의 상당부분 유사하다.

후위표기법의 수식을 보자.

수식트리를 보면 루트노드로 갈수록 나중에 연산이 이루어지고, 후위표기법 같은 경우 가장 뒤의 있는 연산이 마지막에 이루어진다.

즉 후위표기법 뒤에 등장하는 연산을 트리의 하부구조로 만들면 된다.

계산이 어떤식으로 이루어지냐? 스택에 왼쪽노드, 오른쪽노드(피연산자)담고, 연산자 만나면 스택에서 꺼내서 계산하면 된다. 그런데 서브트리가 있으면, 그 서브트리 자체를 피연산자로 간주해서 스택에 넣는다. 스택에 어떻게 넣느냐? 루트노드의 주소값만 스택에 넣으면 된다.

한가지만 더 이야기하면, 스택에서 작은 서브트리과 다른 피연산자 하나를 꺼내서 연산자와 연결지을때, 그렇게 만들어진 트리의 서브트리일 수 있다. 따라서 그 루트노드(연산자)도 다시 스택에 넣어준다.

다음과 같은 룰을 따른다.

피연산자는 무조건 스택으로 보낸다. 그리고 연산자를 마주치면 그걸로 서브트리를 하나 만들고 스택에 쌓는다. (이때 루트노드의 주소만 담는다.)

이런식으로 수식트리를 다 만들면 그것도 스택에 담고, 따라서 최종 트리는 스택에 담김. 그리고 우리가 원하는 결과도 스택에서 나온다.

수식트리의 구현(4)

08-4. 수식 트리(Expression Tree)의 구현 ④

BTreeNode* MakeExpTree(char exp[])
{
	LLStack stack;
	BTreeNode* pnode;
	int expLen = strlen(exp);

	LLSInit(&stack);

	for (int i = 0; i < expLen; i++) 
	{
		if (isdigit(exp[i]))
		{
			LLSPush(&stack, exp[i]); //피연산자면 스택에 올림
		}
		else
		{
			pnode = MakeBTreeNode(); //피연산자가 아니라면 트리만들준비
			SetData(&pnode, exp[i]-'0');
			if (exp[i] == '-' || exp[i] == '/')
			{
				MakeRightSubTree(pnode, LLSPop(&stack));
				MakeLeftSubTree(pnode, LLSPop(&stack));
			}
			else
			{
				MakeLeftSubTree(pnode, LLSPop(&stack));
				MakeRightSubTree(pnode, LLSPop(&stack));
			}
			LLSPush(&stack, pnode);
		}
		
	}

	return LLSPop(&stack);
}