앞 서 만든 이진트리를 만드는 도구를 활용하여 이진트리 구조 중 하나인 수식트리를 만들어보자
1. 수식트리란?
출처: 열혈자료구조
중위,후위,전위 표기법과 같은 여러가지 표기법 중 하나로 메모리에 수식을 표기하는 방식이다.
루트 노드에 연산자를, 두 개의 자식노드에 피연산자를 두어 연산이 진행된다. 이를 그림으로 표기하면 위와 같다.
이러한 수식트리의 장점은 한번 트리를 완성해두면, 중위,후위,전위 표기법으로 쉽게 전환할 수 있다.
2. 구현
중위표기법을 바로 수식트리로 나타내는 것보다 중위표기법을 후위표기법으로 전환한 뒤에 수식트리로 나타내는 것이 간편하므로, 여기서는 후위표기법을 수식트리로 변환하는 과정만 보일 것이다.
수식트리를 표현하기 위한 도구 : 1. Stack, 2 BTree
헤더
#ifndef __EXPRESSTION_H
#define __EXPRESSTION_H
#include "BTree.h"
BTreeNode* MakeExpTree(char exp[]);
int EvaluateExpTree(BTreeNode* btn);
void ShowPrefixType(BTreeNode* btn);
void ShowInfixType(BTreeNode* btn);
void ShowPostfixType(BTreeNode* btn);
#endif
소스
#include "CStack.h"
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include"ExpresstionTree.h"
BTreeNode* MakeExpTree(char exp[]){
Stack st;
int len = strlen(exp);
StackInit(&st);
BTreeNode* node;
for(int i=0; i<len ;i++){
node = MakeBTreeNode();
if(isdigit(exp[i])){
SetData(node,exp[i]-'0');
}else{
MakeRightSubTree(node,pop(&st));
MakeLeftSubTree(node,pop(&st));
SetData(node,exp[i]);
}
push(&st,node);
}
return pop(&st);
}
int EvaluateExpTree(BTreeNode* btn){
int op1,op2;
if(btn->left == NULL && btn->right == NULL){
return btn->data;
}
op1 = EvaluateExpTree(GetLeftSubTree(btn));
op2 = EvaluateExpTree(GetRightSubTree(btn));
switch (btn->data)
{
case '+': return op1+op2;
case '-': return op1-op2;
case '*': return op1*op2;
case '/': return op1/op2;
}
return 0;
}
void ShowPrefixType(BTreeNode* btn){
PreorderTraverse(btn,showdata);
}
void ShowInfixType(BTreeNode* btn){
InorderTraverse(btn,showdata);
}
void ShowPostfixType(BTreeNode* btn){
PostorderTraverse(btn,showdata);
}
void showdata(int data){
if(0<=data && data>=9){
printf("%d ",data);
}else {
printf("%c ",data);
}
}
void ShowInfix1(BTreeNode* btn){
if(btn == NULL) return;
if(btn->left != NULL || btn->right !=NULL)
printf("( ");
ShowInfix1(GetLeftSubTree(btn));
showdata(btn->data);
ShowInfix1(GetRightSubTree(btn));
if(btn->left != NULL || btn->right !=NULL)
printf(" )");
}
BTreeNode* MakeExpTree(char exp[])
수식트리를 구성하기 위한 함수로 후위 표기식을 입력받아 내부적으로 수식트리를 완성해도 return한다.
int EvaluateExpTree(BTreeNode* btn); 수식트리를 계산하는 함수이다.
void ShowPrefixType(BTreeNode* btn); - 수식트리 -> 전위표기
void ShowInfixType(BTreeNode* btn); - 수식트리 -> 중위표기
void ShowPostfixType(BTreeNode* btn); - 수식트리 -> 후위표기
2.1 전개과정
1 2 + 7 * 의 후위표기식이 있다고 가정해보자. 이를 수식트리로 변환하기 위해서
-> 연산자 순서대로 왼쪽에서 오른쪽으로 연산자가 나열됨
-> 해당 연산자의 두 피연산자는 연산자 앞에 나열됨
트리 아래쪽에 위치한 연산자들 부터 연산이 진행되므로 트리의 구성은 위에서 아래로 구성하는 것이아니라 아래에서 위로 구성하는 형태가 될 것이다.
*마치 재귀적 함수를 계산하는 듯한 형태로 구성하는 것 처럼 보일 수 있다.
1 2 + 7 * --> 1과 2는 피연산자이므로 각각의 BTreeNode를 구성해 stack에 담는다.
+7* / stack : 1,2 --> 연산자를 만났다 연산자를 루트노드로 왼쪽과 오른쪽에 피연산자 노드를 연결하고, 다시 스택에 담는다
* 이때 연산자 BTreeNode포인터만 스택에 넣어두어도 이미 연결되어 있음으로 괜찮다!
--> 위 과정을 계속 반복한 뒤 마지막에 스택에 담긴 포인터를 반환한다.
2.2 수식 트리 계산
int EvaluateExpTree(BTreeNode* btn) 이 함수를 통해 수식트리를 계산하고자 한다.
모든 노드에 접근하여 계산해야 하므로, 재귀적으로 함수를 구성해야한다.
종료조건 :
if(btn->left == NULL && btn->right == NULL) return btn->data;
리프노드부터 시작해서 루트노드의 연산자를 통해 연산해야하므로, 후위 순회의 조건으로 재귀함수를 구성해야한다.
또한 재귀함수의 호출이 리프노드에 도달했을 때 더이상 함수를 호출하지 않고, 리프노드의 값을 리턴해야하므로, 종료조건은 리프노드인지 아닌지를 검사하는 위와 같은 식으로 구성할 수 있을 것이다.
출처: 윤성우 - 열혈자료구조