연산자 우선순위를 반영하는 산술식의 이진트리 설계와 구현

//BinaryTreeNode.c

#include "h.h"

/*BIANRY TREE*/
//////////////////////////////////////////////////////////////////////////////////
/*
   트리를 생성하는 함수
   => postfix 배열을 인자로 받은 뒤(postfix배열은 infix를 postfix로 바꾼 문자열)
   stack 배열에 값을 넣어주고
   연산자이면 자식노드를 생성후 오른쪽 자식노드부터 pop하여 값삽입
   피연산자이면 자식노드를 생성하지 않고 pop하여 값만 삽입
   */
/*ABOUT CREATE*/	
//============================================================================

void insertData(BinaryTreeNode* node, char value){
	node->data = value;
	//printf("insert data : %c\n", node->data);
	node->right = NULL;
	node->left = NULL;
}

BinaryTreeNode* createRight(BinaryTreeNode* parent){
	BinaryTreeNode* RightChild = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
	parent->right = RightChild;
	RightChild->right = NULL;
	RightChild->left = NULL;
	return RightChild;
}

BinaryTreeNode* createLeft(BinaryTreeNode* parent){
        BinaryTreeNode* LeftChild = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
        parent->left = LeftChild;
	LeftChild->right = NULL;
	LeftChild->left = NULL;
	return LeftChild;
 }


void createExpTree(Stack* s, BinaryTreeNode* root){
	//postfix의마지막값은 root
	//ex) a*b+c => ab*c+ 여기서 +가 루트가 됨
	int ch;
	if(s->top > -1){
		ch = peek(s);
		if((ch != '*') && (ch != '/') && (ch != '-') && (ch != '+')){
			insertData(root, pop(s));	
		}
		//연산자 일때
		//연산자노드는 무조건 두개의 자식 노드를 가지게됨
		else{
			//연산자 삽입후 
			insertData(root, pop(s));
			createExpTree(s, createRight(root));
			createExpTree(s, createLeft(root));
		}
	}
}


//==================================================================================

/*ABOUT TRAVERSE*/
//====================================================================================

void inorder(BinaryTreeNode* ROOT){
	if(ROOT != NULL){
		inorder(ROOT->left);
		printf("%c",ROOT->data);
		inorder(ROOT->right);
	}
}

void preorder(BinaryTreeNode* ROOT){
	if(ROOT != NULL){
		printf("%c", ROOT->data);
		preorder(ROOT->left);
		preorder(ROOT->right);
	}
}		

void postorder(BinaryTreeNode* ROOT){
	if(ROOT != NULL){
		postorder(ROOT->left);
		postorder(ROOT->right);
		printf("%c", ROOT->data);
	}
}

void levelorder(BinaryTreeNode* ROOT){
	QueueType q;
	init_queue(&q);
	if(ROOT == NULL)
		return ;
		
	enqueue(&q, ROOT);
	while(!isempty(&q)){
		ROOT = dequeue(&q);
		printf("%c", ROOT->data);
		if(ROOT->left)
			enqueue(&q, ROOT->left);
		if(ROOT->right)
			enqueue(&q, ROOT->right);
	}
}
	


//====================================================================================

//////////////////////////////////////////////////////////////////////////////////////////

//main.c

#include "h.h"


/*
   post스택을 사용하여 후위표기식으로 바꾸어 postfix배열에 저장한다.
   그리고 하나씩 pop하여 트리에 값을 넣는다.
   */

void main(int argc, char* argv[]){
	int i;
	int size;
	char* infix;
	char* postfix;
	Stack post;
	BinaryTreeNode* ROOT = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));

	for(i = 1; i<argc; i++){
		infix = argv[i];

		size = size_nums(infix);
		create(&post, size);
		//스택 생성
		postfix = (char*)malloc(size);

		infix_to_postfix(&post, infix, postfix);
		printf("infix to postfix\n");
		for(int j =0; j<size;j++){
			printf("%c",postfix[j]);
		}
		printf("\n");
		Stack s;
		(&s)->stack_data = postfix;
		(&s)->top = size -1;
		createExpTree(&s, ROOT);

		printf("in : ");
		inorder(ROOT);
		printf("\n");
		printf("pre : ");
		preorder(ROOT);
		printf("\n");
		printf("post : ");
		postorder(ROOT);
		printf("\n");
		printf("level : ");
		levelorder(ROOT);
		printf("\n");
		free(postfix);
	}
}

//Queue.c


#include "h.h"

// 오류 함수
void error(char* message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}
//공백 상태 검출 함수
void init_queue(QueueType* q)
{
	q->front = q->rear = 0;
}

//공백 상태 검출 함수
int isempty(QueueType* q)
{
	return (q->front == q->rear);
}

//포화 상태 검출 함수
int isfull(QueueType * q)
{
	return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}


//삽입 함수
void enqueue(QueueType * q, element item)
{
	if (isfull(q))
		error("큐가 포화상태입니다");
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}

//삭제 함수
element dequeue(QueueType * q)
{
	if (isempty(q))
		error("큐가 공백상태입니다");
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}

//삭제함수
element queue_peek(QueueType * q)
{
	if (isempty(q))
		error("큐가 공백상태입니다");
	return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}

//stack.c


#include "h.h"
//////////////////////////////////////////////////////////////////////////////////////////
/* STACK */
/*
typedef struct {
	char* stack_data;
	int top;
}Stack;
*/

//스택 생성
void create(Stack* s, int exp_size) {
	s->stack_data = (char*)malloc(exp_size);
	s->top = -1;
}

//스택이 비었는지 확인
int is_empty(Stack* s) {
	return (s->top == -1);
}

int is_full(Stack* s, int exp_size) {
	return (s->top == (exp_size - 1));
}

void push(Stack* s, char data, int exp_size) {
	int top = s->top;
	if (is_full(s, exp_size)) {
		printf("stack is full!\n");
		exit(1);
	}
	else {
		s->stack_data[++(s->top)] = data;
	}
}

char pop(Stack* s) {
	int top;
	if (is_empty(s)) {
		printf("stack is empty!\n");
		exit(1);
	}
	else {
		top = s->top;
		(s->top)--;
		return s->stack_data[top];
	}
}

char peek(Stack* s) {
	if (is_empty(s)) {
		printf("stack is empty!\n");
		exit(1);
	}
	else {
		return s->stack_data[s->top];
	}
}

void stack_free(Stack* s) {
	free(s->stack_data);
}

int size_nums(char* exp) {
	int count = 0;
	int size = strlen(exp);
	for (int i = 0; i < size; i++) {
		char data = exp[i];

		switch (data) {
		case '(': case ')':
			count++;
			break;
		}
	}

	return size = size - count;

}

int order(char op) {
	switch (op) {
	case '(': case')':
		return 0;
	case '+': case '-':
		return 1;
	case '*': case '/':
		return 2;
	default:
		return -1;
	}
}

void infix_to_postfix(Stack* s, char* infix, char* postfix) {
	char ch, op, result;
	int expSize;
	expSize = strlen(infix);
	int index = 0;
	for (int i = 0; i < expSize; i++) {
		ch = infix[i];
		switch (ch) {
		case '+': case '-': case '*': case '/': {
			//스택이 비어있지 않고 스택의 연산자보다 낮은 우선순위일때 pop
			if (!is_empty(s) && order(ch) <= order(peek(s))) {
				//printf("%c", pop(s));
				postfix[index++] = pop(s);
			}
			push(s, ch, expSize);//push ch 스택에
			break;
		}
		//왼쪽 괄호를 만나면 스택에 저장
		case '(': {
			push(s, ch, expSize);
			break;
		}
		//왼쪽 괄호가 나올때까지 출력=>to postfix array
		case ')': {
			 result = pop(s);
			while (result != '(') {
				//printf("%c", result);
				postfix[index++] = result;
				result = pop(s);
			}
			break;
		}
		default: {
			postfix[index++] = ch;
			break; }

		}
	}
	while (!is_empty(s)) {
		postfix[index++] = pop(s);
		//printf("%c", pop(s));
	}
}
//STACK
///////////////////////////////////////////////////////////////////////////////////////////////////

//h.h


//이창민
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/*tree*/
typedef struct BinaryTreeNode{
        char data;
        struct BinaryTreeNode* right;
        struct BinaryTreeNode* left;
}BinaryTreeNode;

/*stack*/
typedef struct {
        char* stack_data;
        int top;
}Stack;

/*queue*/
#define MAX_QUEUE_SIZE 20
typedef BinaryTreeNode * element;
typedef struct { //큐타입
	element data[MAX_QUEUE_SIZE];
	int front, rear;
} QueueType;

/*TREE*/
///////////////////////////////////////////////////////////
void createExpTree(Stack* s, BinaryTreeNode* root);
void insertData(BinaryTreeNode* node, char data);

BinaryTreeNode* createRight(BinaryTreeNode* parent);
BinaryTreeNode* createLeft(BinaryTreeNode* parent);

void inorder(BinaryTreeNode* ROOT);
void preorder(BinaryTreeNode* ROOT);
void postorder(BinaryTreeNode* ROOT);
void levelorder(BinaryTreeNode* ROOT);
////////////////////////////////////////////////////////////

/*STACK*/
//////////////////////////////////////////////////////////////
void create(Stack* s, int exp_size);
int is_empty(Stack* s);
int is_full(Stack* s, int exp_size);
void push(Stack* s, char data, int exp_size);
char pop(Stack* s);
char peek(Stack* s);
void stack_free(Stack* s);
int size_nums(char* exp);
int order(char op);
void infix_to_postfix(Stack* s, char* infix, char* postfix);
////////////////////////////////////////////////////////////////


/*Queue*/
////////////////////////////////////////////////////////////
void error(char* message);
void init_queue(QueueType* q);
int isempty(QueueType* q);
int isfull(QueueType* q);
void queue_print(QueueType* q);
void enqueue(QueueType* q, element item);
element dequeue(QueueType* q);
element queue_peek(QueueType* q);
////////////////////////////////////////////////////////////////