본문 바로가기
C/알고리즘

[C]수식 트리 - Evaluate Tree

by 덤더리덤떰 2023. 9. 22.

1. 수식트리

: 산술식을 트리형태로 표현
: 컴파일러가 수식을 처리하는 방식
: 단말노드 => 피연산자, 비단말노드 => 연산자

출처 : 윤성우의 열혈 자료구조

2. 수식 트리 계산

중위 표기법 수식 -> 후위 표기법 수식 -> 수식 트리 -> 수식 트리 계산
  • 중위 표기법 수식 -> 후위 표기법 수식 : 스택 이용
  • 후위 표기법 수식 -> 수식 트리 : 스택 이용
  • 수식 트리 -> 수식 트리 계산 : 후위순회 이용

2-1. 후위 표기법 수식

: 스택 이용 
https://growingupis.tistory.com/32?category=1186559

 

스택 응용(수식 계산)

1. 수식표기법 (1) 중위표기법(infix notation) : 연산자를 피연산자의 가운데 표기하는 방법 => 우리가 사용하는 방식 ex) A+B (2) 후위표기법(postfix notation) : 연산자를 피연산자 뒤에 표기하는 방법 => 컴

growingupis.tistory.com

 

2-2. 수식 트리 구성 

: 스택을 이용하여 후위 표기법 수식을 수식 트리로 구성

  1. 피연산자는 스택에 push
  2. 연산자를 만나면 스택에서 피연산자 두개를 pop하여 트리 구성(트리도 피연산자 취급)
  3. 생성된 트리는 다시 스택에 push(부모 노드의 포인터만 스택에 push하여 저장

 

출처 : 윤성우의 열혈 자료구조
출처 : 윤성우의 열혈 자료구조

2-3. 수식트리 이용하여 수식 계산

: 스택 이용하여 수식트리 생성하였기에 수식은 하위에서부터 연산되어야함
: 재귀호출을 이용

 

4. c언어로 구현 

"total.h" 헤더파일
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

typedef char element;
"stack_node.h" 헤더파일
#include "total.h"

#define tSTACK_SIZE 100
#include <memory.h>
#define max(a,b) ((a>b)?(a):(b))

typedef struct _TREE_NODE_ {
	element data;
	struct _TREE_NODE_* left;
	struct _TREE_NODE_* right;
}TREE_NODE;

TREE_NODE* root;

TREE_NODE* t_stack[tSTACK_SIZE];
int t_top;

void INIT();
int ISEMPTY();
int ISFULL();
void PUSH(TREE_NODE* item);
TREE_NODE* POP();
TREE_NODE* PEEK();
TREE_NODE* MakeNode(element item);
TREE_NODE* Merge(element item, TREE_NODE* left, TREE_NODE* right);
void LVR(TREE_NODE * node);
int HEIGHT(TREE_NODE* node);
int CountNode(TREE_NODE* node);
"stack.h" 헤더파일
#include "total.h"
#define STACK_SIZE 100

typedef struct _STACK_ {
	element stack[STACK_SIZE];
	int top;
}STACK;


int IsFull(STACK* st);
int IsEmpty(STACK* st);
void push(STACK* st, element item);
int peek(STACK* st);
int pop(STACK* st);
void init(STACK* st);
stack_node.c
#include "stack_node.h"

void INIT() {
	memset(t_stack, 0, tSTACK_SIZE);
	t_top = -1;
}

int ISEMPTY() {
	return t_top == -1;
}

int ISFULL() {
	return t_top == tSTACK_SIZE - 1;
}

void PUSH(TREE_NODE* item) {
	if (ISFULL(t_stack)) {
		printf("스택이 꽉찼습니다\n");
		return;
	}
	else {
		t_top++;
		t_stack[t_top] = item;
	}
}

TREE_NODE* POP() {
	if (ISEMPTY(t_stack)) {
		printf("스택이 비어있습니다\n");
		return;
	}
	else {
		TREE_NODE *popnode = t_stack[t_top];
		t_top--;
		return popnode;
	}
}

TREE_NODE* PEEK() {
	if (ISEMPTY(t_stack)) {
		printf("스택이 비어있습니다\n");
		return;
	}
	else {
		return t_stack[t_top];
	}
}

//후위표기에서 숫자인 경우 
TREE_NODE * MakeNode(element item) {
	TREE_NODE* newNode = (TREE_NODE*)calloc(1, sizeof(TREE_NODE));
	assert(newNode != NULL);
	newNode->data = item;
	newNode->left = NULL;
	newNode->right = NULL;

	return newNode;
}

//후위표기에서 연산자일때 숫자가아닌 트리를 연결하는 경우
TREE_NODE* Merge(element item, TREE_NODE* left, TREE_NODE* right) {
	TREE_NODE* root = (TREE_NODE*)calloc(1, sizeof(TREE_NODE));
	assert(root != NULL);
	root->data = item;
	root->left = left;
	root->right = right;
}

void LVR(TREE_NODE * node) {
	if (node == NULL) {
		return;
	}
	LVR(node->left);
	printf("%c ", node->data);
	LVR(node->right);
}

int HEIGHT(TREE_NODE* node)
{
	if (node == NULL) {
		return 0;
	}
	else {
		return 1 + max(HEIGHT(node->left), HEIGHT(node->right));
	}
	
}

int CountNode(TREE_NODE* node)
{
	if (node == NULL) {
		return 0;
	}
	else {
		return 1 + CountNode(node->left)+CountNode(node->right);
	}
	
}​
stack.c
#include "stack.h"


void init(STACK* st) {
	st->top = -1;
	memset(st->stack, 0, sizeof(st->stack));
}

int IsFull(STACK* st) {
	return st->top == STACK_SIZE - 1;
}

int IsEmpty(STACK* st) {
	return st->top == -1;
}


void push(STACK* st, element item) {
	if (IsFull(st)) {
		printf("스택이 꽉차있습니다\n");
		return;
	}
	else {
		st->top++;
		st->stack[st->top] = item;
	}
}

int peek(STACK* st) {
	if (IsEmpty(st)) {
		printf("스택이 비어있습니다\n");
		return;
	}
	else {
		return st->stack[st->top];
	}
}

int pop(STACK* st) {
	if (IsEmpty(st)) {
		printf("스택이 비어있습니다\n");
		return;
	}
	else {
		element data = st->stack[st->top];
		st->top--;
		return data;
	}
}
main.c
#include "stack.h"
#include "stack_node.h"
#include <stdbool.h>
#include <ctype.h>
#define STRING_SIZE 50

int IsTest(STACK *st, char * exp, int len) {
	//괄호검사
	for (int i = 0; i < len; i++) {
		if (exp[i] == '(') {
			push(st, exp[i]);
		}
		else if (exp[i] == ')') {
			element data = pop(st);
		}
	}

	if (!IsEmpty(st)) {
		return false;
	}
	else {
		return true;
	}
}

int precedence(element item) {
	switch (item) {
	case '(':
	case ')':
		return 0;
	case '+':
	case '-':
		return 1;
	case '*':
	case '/':
	case '%':
		return 2;
	}
}

void infix_to_postfix(STACK* st, char* exp, char* res, int len) {
	//중위표기를 후위표기로 (일반화)
	int k = 0;
	for (int i = 0; i < len; i++) {
		if (exp[i] == '(') {
			push(st, exp[i]);
		}
		else if (exp[i] == ')') {
			while (!IsEmpty(st)) {
				element popdata = pop(st);
				if (popdata == '(') {
					break;
				}
				else {
					res[k++] = popdata;
					res[k++] = ' ';
				}
			}
		}
		else if (exp[i] >= '0' && exp[i] <= '9') {
			res[k++] = exp[i];
			res[k++] = ' ';
		}
		else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/' || exp[i] == '%') {
			while (!IsEmpty(st)) {
				element peekdata = peek(st);
				if (precedence(peekdata)<precedence(exp[i])) {
					break;
				}
				else {
					res[k++] = pop(st);
					res[k++] = ' ';
				}
			}
			push(st, exp[i]);
		}
	}
	while (!IsEmpty(st)) {
		res[k++] = pop(st);
		res[k++] = ' ';
	}
	res[k] = '\0';
}

// 4 2 + 4 / 3 7 7 5 * / + -
TREE_NODE * MakeEvaluateTree(char* res, int len) {
	TREE_NODE* left;
	TREE_NODE* right;
	for (int i = 0; i < len; i++) {
		if (isdigit(res[i])) {
			//숫자이면 숫자노드 생성한다
			TREE_NODE * node =MakeNode(res[i]);
			PUSH(node);
		
		}
		else if (res[i] == ' ') {
			//공백이면 넘어간다
			continue;
		}
		else {

			//만약 4%2계산해야한다면 나중에 후위순회할거이기에 4 2 순서로 트리 생성되어야함
			right = POP();
			left = POP();

			TREE_NODE * newNode=Merge(res[i], left, right);
			PUSH(newNode);

		}
	}

	return POP();
}

int Evaluate(TREE_NODE * node) {
	if (node->left == NULL && node->right == NULL) {
		return (node->data)-'0';
	}

	int op1 = Evaluate(node->left);
	int op2 = Evaluate(node->right);

	switch (node->data) {
	case '+':
		return op1 + op2;
		break;
	case '-':
		return op1 - op2;
		break;
	case '/':
		return op1 / op2;
		break;
	case '%':
		return op1 % op2;
		break;
	case '*':
		return op1 * op2;
		break;
	}

	
	
}

int main() {
	
	char expression[] = "(((4+2)/4)-(3+(7/(7*5))))";
	STACK* st;
	int len = strlen(expression);
	st = (STACK*)calloc(1, sizeof(STACK));
	assert(st != NULL);
	st->top = -1;

	if(IsTest(st,expression,len)) {
		printf("1. 괄호검사 통과\n\n");
		init(st);
		char res[STRING_SIZE] = { 0 };
		infix_to_postfix(st, expression, res, len);
		printf("2. 중위표기 -> 후위표기 결과 : %s\n\n", res);
		printf("3. 수식트리 생성\n\n ");
		INIT();
		root=MakeEvaluateTree(res, strlen(res));
		
		printf("-> 이때, LVR로 트리 출력 :");
		LVR(root);
		printf("\n\n");

		printf("4. 수식계산 결과 : %d\n\n", Evaluate(root));
		printf("5. 노드의 갯수 : %d\n\n", CountNode(root));
		printf("6. 트리의 높이 : %d\n\n", HEIGHT(root));
	
	}
	else {
		printf("괄호검사를 통과하지 못하였으므로 수식계산을 수행할 수 없습니다\n");
		return;
	}






	getchar();
	return 0;
}

 
cf> 공부하면서 알게된 것
: 트리의 높이를 코드로 구현하면서 node가 NULL인 경우엔 return 0;이 아닌 그냥 return;로 했을때 실제 트리높이+1의 값이 나와서 디버깅하면서 살펴보니 return;을 할 경우에는 max 함수를 구현하기 위해서는 값이 들어가있어야하는데 아무것도 반환하지 않으므로 값을 찾아내기 위해 한 번 더 HEIGHT 함수를 수행하게 되어서 +1이 되어 최종 결과도 실제 트리높이 +1이 된다. 따라서 return 0;을 꼭 해주자! ( 이와 마찬가지로 트리의 총 노드 갯수 구하는 코드를 구현하는 것도 동일)

int HEIGHT(TREE_NODE* node) {
    if (node == NULL) {
        return 0;
    } else {
        return 1 + max(HEIGHT(node->left), HEIGHT(node->right)); }
    }

 

 

ver2)

stack.h
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <stdbool.h>
#define TRUE 1
#define FALSE 0

typedef struct _STACK_NODE_ {
	int data;
	struct _STACK_NODE_* link;
}STACK_NODE;

typedef struct _STACK_HEAD_ {
	STACK_NODE* head;
}STACK;

STACK* makeStack();
void push(STACK * st, int item);
int pop(STACK* st);
int peek(STACK* st);
int isEmpty(STACK* st);
bool bracketTest(char* express);
void infix_to_postfix(char* infix, char* post);​
stack.c
#include "stack.h"

STACK* makeStack() {
	STACK* st = (STACK*)calloc(1, sizeof(STACK));
	assert(st != NULL);
	return st;
}
void push(STACK* st, int item) {
	STACK_NODE* newNode = (STACK_NODE*)calloc(1, sizeof(STACK_NODE));
	assert(newNode != NULL);
	newNode->data = item;
	if (isEmpty(st)) {
		st->head = newNode;
	}
	else {
		newNode->link = st->head;
		st->head = newNode;
	}
}
int pop(STACK* st) {
	if (isEmpty(st)) {
		fprintf(stderr, "Stack is empty");
	}
	else {
		int data = st->head->data;
		STACK_NODE* delNode = st->head;
		st->head = st->head->link;
		free(delNode);
		delNode = NULL;
		return data;
	}
}
int peek(STACK* st) {
	if (isEmpty(st)) {
		fprintf(stderr, "Stack is empty");
	}
	else {
		return st->head->data;
	}
}
int isEmpty(STACK* st) {
	return st->head == NULL;
}

bool bracketTest(char* express) {
	STACK* st = makeStack();
	int len = strlen(express);
	for (int i = 0; i < len; i++) {
		if (express[i] == '(') {
			push(st, express[i]);
		}
		else if (express[i] == ')') {
			if (isEmpty(st)) {
				return false;
			}
			else {
				pop(st);
			}
		}
	}
	if (isEmpty(st)) {
		return true;
	}
	else {
		return false;
	}
}

int precedence(char item) {
	switch (item) {
	case '(':
	case ')':
		return 0;
	case '+':
	case '-':
		return 1;
	case '*':
	case '/':
	case '%':
		return 2;
	}
}


void infix_to_postfix(char* infix, char* postfix) {
	STACK* st = (STACK*)calloc(1, sizeof(STACK));
	assert(st != NULL);
	int len = strlen(infix);
	int k = 0;
	for (int i = 0; i < len; i++) {
		char data = infix[i];
		if (data >= '0' && data <= '9') {
			int j = i;
			while (infix[j] >= '0' && infix[j] <= '9') {
				postfix[k++] = infix[j++];
			}
			postfix[k++] = ' ';
			i = j - 1;
		}
		else if (data == '(') {
			push(st, data);
		}
		else if (data == ')') {
			while (!isEmpty(st)) {
				char item = pop(st);
				if (item == '(') {
					break;
				}
				else {
					postfix[k++] = item;
					postfix[k++] = ' ';
				}
			}
		}
		else if (data == '+' || data == '-' || data == '%' || data == '/' || data == '*') {
			while (!isEmpty(st)) {
				char peekdata = peek(st);
				if (precedence(peekdata) < precedence(data)) {
					break;
				}
				else {
					postfix[k++] = pop(st);
					postfix[k++] = ' ';
				}
			}
			push(st, data);
		}
	}
	while (!isEmpty(st)) {
		postfix[k++] = pop(st);
		postfix[k++] = ' ';
	}
	postfix[k] = '\0';
}​
main.c
#define _CRT_SECURE_NO_WARNINGS
#include "stack.h"
#define MAX_STRING_SIZE 100

#define MAX_TREE_STACK_SIZE 100
typedef struct _TREE_NODE_ {
	int t_data;
	struct _TREE_NODE_* left;
	struct _TREE_NODE_* right;
	bool isdigit;
}TREE_NODE;

TREE_NODE* t_stack[MAX_TREE_STACK_SIZE] = { 0, };
int t_top = -1;

int t_isEmpty();
int t_isFull();
void t_push(TREE_NODE* item);
TREE_NODE* t_pop();
TREE_NODE* t_peek();
TREE_NODE* makeEvalTree(char* exp);
TREE_NODE* makeNode(int item);
void LVR();
int Eval(TREE_NODE* root);

#include <memory.h>

#define TRUE	1
#define FALSE	0

//#define TRAVERSE_DEBUG

typedef int NodeData;

typedef struct _TREENODE_ {
	NodeData data;
	struct _TREENODE_* left;
	struct _TREENODE_* right;
}TREENODE;

typedef struct _NODEMAP_ {
	int flag;
	NodeData data;
}NODEMAP;

int getMax(int a, int b)
{
	return ((a > b) ? a : b);
}

int countNode(TREENODE* node) {
	if (node == NULL) return 0;
	return 1 + countNode(node->left) + countNode(node->right);
}

int getHeight(TREENODE* node) {
	if (node == NULL) {
		return 0;
	}
	else {
		return 1 + max(getHeight(node->left), getHeight(node->right));
	}
}

void printGivenLevel(TREENODE* root, int level, NODEMAP* map, int pos)
{
	if (root == NULL)
	{
		return;
	}
	if (level == 1) {
		map[pos].data = root->data;
		map[pos].flag = TRUE;
	}
	else if (level > 1)
	{
		printGivenLevel(root->left, level - 1, map, pos * 2);
		printGivenLevel(root->right, level - 1, map, pos * 2 + 1);
	}
}

void showTree(TREENODE* node)
{
	int height = 0;
	int numOfNodes = 0;
	NODEMAP* treeArray = NULL;
	char** square = NULL;
	static int pos = 0;
	int cnt_i;
	int cnt_j;
	int position;
	int start, term, index;

	height = getHeight(node);
	if (height != 0) {
		numOfNodes = (1 << height);
	}
	treeArray = (NODEMAP*)calloc(numOfNodes, sizeof(NODEMAP));
	assert(treeArray != NULL);

	square = (char**)calloc(height, sizeof(char*));
	for (cnt_i = 0; cnt_i < height; cnt_i++)
	{
		square[cnt_i] = (char*)calloc(numOfNodes, sizeof(char));
		memset(square[cnt_i], '.', numOfNodes);
	}


	pos = 1;
	for (cnt_i = 1; cnt_i <= height; cnt_i++) {
		printGivenLevel(node, cnt_i, treeArray, pos);
	}

	
	for (cnt_i = 1; cnt_i <= numOfNodes; cnt_i++)
	{
		treeArray[cnt_i - 1] = treeArray[cnt_i];
	}

	pos = 0;
	start = (1 << (height - 1)) - 1;
	term = (1 << (height));
	index = (1 << (height - 2));
	for (cnt_i = 0; cnt_i < height; cnt_i++)
	{
		for (cnt_j = start; cnt_j < numOfNodes; cnt_j += term)
		{
			if (treeArray[pos].flag == TRUE) {
				if (treeArray[pos].data >= 0 && treeArray[pos].data <= 9) {
					square[cnt_i][cnt_j] = (treeArray[pos].data + '0');
				}
				else {
					square[cnt_i][cnt_j] = (treeArray[pos].data);
				}
			}
			else {
				square[cnt_i][cnt_j] = '.';
			}
			pos += 1;
		}
		term >>= 1;
		start -= index;
		index >>= 1;
	}

	printf("\n");
	for (cnt_i = 0; cnt_i < height; cnt_i++)
	{
		for (cnt_j = 0; cnt_j < numOfNodes; cnt_j++)
		{
			printf("%c", square[cnt_i][cnt_j]);
		}
		printf("\n");
	}

	if (treeArray != NULL) {
		free(treeArray);
	}
	if (square != NULL)
	{
		for (cnt_i = 0; cnt_i < height; cnt_i++)
		{
			if (square[cnt_i] != NULL)
			{
				free(square[cnt_i]);
			}
		}
		free(square);
	}
}


int main() {

	char infix_expr[] = "7+4*2-1";
	//(((4+2)/4)-(3+(7/(7*5))))
	

	if (bracketTest(infix_expr)) {

		printf("1. 괄호검사 통과\n\n");
		
		char postfix_expr[MAX_STRING_SIZE] = { 0 };
		infix_to_postfix(infix_expr, postfix_expr);
		printf("2. 중위표기 -> 후위표기 결과 : %s -> %s\n\n", infix_expr,postfix_expr);
		printf("3. 수식트리 생성\n\n ");
		
		TREE_NODE * root =  makeEvalTree(postfix_expr);
		showTree(root);
		printf("\n");
		LVR(root);

		printf("\n\n");
		printf("4. 수식계산 결과 : %d\n\n", Eval(root));
		printf("5. 노드의 갯수 : %d\n\n", countNode(root));
		printf("6. 트리의 높이 : %d\n\n",getHeight(root));

	}
	else {
		printf("괄호검사를 통과하지 못하였으므로 수식계산을 수행할 수 없습니다\n");
		return;
	}


	getchar();
	return 0;
}

int t_isEmpty() {
	return t_top == -1;
}
int t_isFull() {
	return t_top == MAX_TREE_STACK_SIZE - 1;
}
void t_push(TREE_NODE* item) {
	if (t_isFull()) {
		fprintf(stderr, "Stack is full");
	}
	else {
		t_stack[++t_top] = item;
	}
}
TREE_NODE* t_pop() {
	if (t_isEmpty()) {
		fprintf(stderr, "Stack is empty");
	}
	else {
		return t_stack[t_top--];
	}
}
TREE_NODE* t_peek() {
	if (t_isEmpty()) {
		fprintf(stderr, "Stack is empty");
	}
	else {
		return t_stack[t_top];
	}
}



TREE_NODE* makeNode(int item) {
	TREE_NODE* newNode = (TREE_NODE*)calloc(1, sizeof(TREE_NODE));
	assert(newNode != NULL);
	newNode->t_data = item;
	return newNode;
}

TREE_NODE* makeEvalTree(char* exp) {

	int len = strlen(exp);
	for (int i = 0; i < len; i++) {
		char data = exp[i];
		if (data >= '0' && data <= '9') {
			int j = i + 1;
			int push_val = data - '0';
			while (exp[j] >= '0' && exp[j] <= '9') {
				push_val *= 10;
				push_val += (exp[j] - '0');
			}
			i = j;
			TREE_NODE* node = makeNode(push_val);
			node->isdigit = true;
			t_push(node);
		}
		else if (data == '+' || data == '-' || data == '*' || data == '/' || data == '%') {
			TREE_NODE* right = t_pop();
			TREE_NODE* left = t_pop();
			TREE_NODE* root = makeNode(data);
			root->left = left;
			root->right = right;
			
			t_push(root);
		}
	}

	return t_pop();
}

void LVR(TREE_NODE* root) {
	if (root == NULL) {
		return;
	}
	else {
		LVR(root->left);
		LVR(root->right);
		if (root->isdigit) {
			printf("%d ", root->t_data);
		}
		else {
			printf("%c ", root->t_data);
		}
		
	}
}



int Eval(TREE_NODE* root) {
	if (root->left == NULL && root->right == NULL) {
		return root->t_data;
	}
	else {
		int x = Eval(root->left);
		int y = Eval(root->right);

		char op = (char)(root->t_data);
		switch (op) {
		case '+':
			return x + y;
		case '-':
			return x - y;
		case '*':
			return x * y;
		case '/':
			return x / y;
		case '%':
			return x % y;
		}
	}
}​

'C > 알고리즘' 카테고리의 다른 글

[C] AVL TREE  (0) 2023.12.10
[C] Prim Alogrithm  (0) 2023.10.06
[C]트리 레벨 순회 - Level Order Traverse  (0) 2023.09.22
원형 연결 리스트  (0) 2023.09.20
큐 응용 : 미로문제(Maze problem)  (0) 2023.09.19

관련글

티스토리툴바