LinkedList를 이용한 Tree 계산

<LinkedList를 이용하여 Tree 계산 하기>

계산식을 LinkedList로 만들고, List의 순위를 결정하여 Tree 형식으로 전환하고

전환한 Tree 식을 계산하여 계산식을 만든다.

재코딩으로 주석처리 된 것은 내가 만든 코드에서 재코딩하여 실무적으로

변환한 코딩이다.

---

#inlcude <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX 20

​

typedef struct Node //노드 구조

{

int data, level;

char oper;

struct Node *link;

struct Node *left, *right;

} Node;

​

Node* firstnode = NULL;

Node* lastnode = NULL;

Node* root = NULL;

Node* node[MAX] = {0x00, };

​

void resettmpData(char Exp[], int len)

{

int i;

for(i=0 ; i<len ; i++)

Exp[i] = '\0';

}

​

int level(char data) //노드 순위 결정 함수

{

switch(data)

{

case '+': case '-':

return 3;

break;

case '*': case '/':

return 2;

break;

default:

return 1;

break;

}

}

​

/*Node* SetNewNode() //재코딩 새 노드 생성 및 초기화 함수

{

Node *NewNode = (Node*)malloc(sizeof(Node));

NewNode->data = 0;

NewNode->oper = '\0';

NewNode->level = 0;

​

NewNode->left = NULL;

NewNode->right = NULL;

​

return NewNode;

}

​

void SetFirstNode(Node* NewNode);

{

if(firstnode == NULL)

{

firstnode = NewNode;

lastnode = NewNode;

}

else

{

lastnode->link = NewNode;

lastnode = NewNode;

}

}*/

​

/*Node* MakeNode(char data[]) //재코딩한 노드 생성 함수

{

char tmpData[MAX]= {0,};

char ch;

int i, tmpCnt = 0;

​

Node* NewNode = NULL;

​

for(i=0 ; i<data[i] ; i++)

{

if(ch == ' ')

continue;

else if(ch >= '0' && ch <= '9')

{

tmpData[tmpCnt++] = ch;

}

else if(ch == '+' || ch == '-' || ch == '*' || ch == '/')

{

if(tmpCnt > 0)

{

NewNode = SetNewNode();

NewNode->data = atoi(tmpData);

resettmpData(tmpData, tmpCnt);

tmpCnt = 0;

SetFirstNode(NewNode);

}

​

NewNode = SetNewNode();

NewNode->oper = ch;

NewNode->level = level(ch);

SetFirstNode(NewNode);

}

}

}*/

​

Node* CreateNode(char data[[]) //노드 생성

{

char tmpData[MAX] = {0,};

char ch;

int i, tmpCnt = 0;

​

for(i=0 ; i<data[i] ; i++)

{

Node* NewNode = (Node*)malloc(sizeof(Node));

NewNode->link = NULL;

​

ch = data[i];

​

if(ch == ' ')

continue;

else if(ch >= '0' && ch <= '9')

{

tmpData[tmpCnt++] = ch;

​

if(data[i+1] == '+' || data[i+1] == '-' ||

data[i+1] == '*' || data[i+1] == '/')

{

NewNode->level = level(ch);

}

else

{

while(ch >= '0' && ch <= '9')

{

tmpData[tmpCnt] = data[i+1];

tmpCnt++;

i++;

}

NewNode->level = level(ch);

}

​

NewNode->data = atoi(tmpData);

NewNode->oper = '\0';

resttmpData(tmpData, tmpCnt);

tmpCnt = 0;

}

else if(ch == '+' || ch == '-' || ch == '*' || ch == '/')

{

NewNode->data = 0;

NewNode->oper = ch;

NewNode->level = level(ch);

}

​

NewNode->left = NULL;

NewNode->right = NULL;

​

if(firstnode == NULL)

{

firstnode = NewNode;

lastnode = NewNode;

}

else

{

lastnode->link = NewNode;

lastnode = NewNode;

}

​

}

}

​

int calc(Node* root) //트리 계산식

{

int op1, op2, result;

​

if(root->left == NULL && root->right == NULL)

{

return root->data;

}

​

op1 = calc(root->left);

op2 = calc(root->right);

​

switch(root->oper)

{

case '+':

root->data = op1 + op2;

break;

case '-':

root->data = op1 - op2;

break;

case '*':

root->data = op1 * op2;

break;

case '/':

root->data = op1 / op2;

break;

}

​

return root->data;

}

​

Node* makeTree(Node *node[], int start, int end) //트리 구조로 전환하는 함수

{

int i = 0, top = -1, level = -1;

Node* tmp = NULL;

​

if(start >= end)

{

return NULL;

}

​

for(i=start ; i<end ; i++)

{

if(node[i] == NULL)

{

break;

}

else if(level < node[i]->level)

{

level = node[i]->level;

top = i;

tmp = node[top];

}

}

​

tmp->left = makeTree(node, start, top);

tmp->right = makeTree(node, top+1, end);

​

return tmp;

}

​

void main()

{

int i, nodenum = 0;

char input[MAX] = {0x00, };

printf("계산식 입력 : ");

scanf("%s", input);

CreateNode(input);

​

Node* temp = firstnode;

​

while(temp != NULL)

{

node[nodenum] = temp;

nodenum++;

temp = temp->link;

}

​

root = makeTree(node, 0, nodenum);

​

calc(root);

​

printf("결과 값은 : %d 입니다.\n", root->data);

}