#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct TreeNode {
	char op_ch;
	struct TreeNode* left, * right;
} TreeNode;

typedef struct {
	struct TreeNode* root;
} TreeType;

typedef struct StackNode {
	TreeNode* item;
	struct StackNode* link;
} StackNode;

typedef struct {
	StackNode* top;
} LinkedStackType;


void init_t(TreeType* t) {
	t->root = NULL;
}

void init(LinkedStackType* s) {
	s->top = NULL;
}

int is_empty(LinkedStackType* s) {
	return (s->top == NULL);
}


int is_full(LinkedStackType* s) {
	return 0;
}


void push(LinkedStackType* s, TreeNode* item) {
	StackNode* temp = (StackNode*)malloc(sizeof(StackNode));

	if (temp == NULL) {
		printf("메모리 할당 에러\n");
	}
	else {
		temp->item = item;
		temp->link = s->top;
		s->top = temp;
	}
}

TreeNode* pop(LinkedStackType* s) {
	if (is_empty(s)) {
		printf("스택이 비어있음\n");
		exit(1);
	}
	else {
		StackNode* temp = s->top;
		TreeNode* item = temp->item;
		s->top = s->top->link;
		free(temp);
		return item;
	}
}

void tree_display(TreeNode* r) {
	if (r != NULL) {
		tree_display(r->left);
		printf("%c ", r->op_ch);
		tree_display(r->right);
	}
}


void make_exp_tree(TreeType* t, char str[]) {
	LinkedStackType *lst = new LinkedStackType();
	
	for(int i=0; str[i]!='\0'; ++i){
		if(str[i]==' ') continue;
		if(str[i]>='0' && str[i]<='9'){ // 숫자라면 스택에 쌓음
			StackNode *newStackNode = new StackNode();
			TreeNode *newTreeNode = new TreeNode();
			newTreeNode->op_ch = str[i];
			newStackNode->item = newTreeNode;
			if(lst->top==NULL){
				lst->top=newStackNode;
			}
			else{
				newStackNode->link=lst->top;
				lst->top=newStackNode;
			}
		}
		else{ // 연산자라면 스택에서 2개 뺀 후 결과값을 스택에 쌓음
			StackNode *rightStackNode = lst->top;
			if(lst->top->link==NULL) lst->top=NULL;
			else lst->top=lst->top->link;

			StackNode *leftStackNode = lst->top;
			if(lst->top->link==NULL) lst->top=NULL;
			else lst->top=lst->top->link;

			StackNode *newStackNode = new StackNode();
			TreeNode *newTreeNode = new TreeNode();
			newTreeNode->left = leftStackNode->item;
			newTreeNode->right = rightStackNode->item;
			newTreeNode->op_ch = str[i];
			newStackNode->item=newTreeNode;

			if(lst->top==NULL){
				lst->top=newStackNode;
			}
			else{
				newStackNode->link=lst->top;
				lst->top=newStackNode;
			}
		}
	}
	t->root=lst->top->item;
}


int exp_evaluation(TreeNode* r) {
	if(r->op_ch=='+'){
		return exp_evaluation(r->left)+exp_evaluation(r->right);
	}
	else if(r->op_ch=='-'){
		return exp_evaluation(r->left)-exp_evaluation(r->right);
	}
	else if(r->op_ch=='*'){
		return exp_evaluation(r->left)*exp_evaluation(r->right);
	}
	else if(r->op_ch=='/'){
		return exp_evaluation(r->left)/exp_evaluation(r->right);
	}
	else {
		return r->op_ch-'0';
	}
}


int descendant_node_count(TreeNode* node) { // 트리의 간선의 개수는 정점의 개수-1개. 트리의 자손의 개수는 정점의 개수-1개. 즉 간선을 세는 것과 같다.
	int ret=0;
	if(node->left!=NULL) {
		ret+=1;
		ret+=descendant_node_count(node->left);
	}
	if(node->right!=NULL) {
		ret+=1;
		ret+=descendant_node_count(node->right);
	}

	return ret;
}


int terminal_node_count(TreeNode* node) {
	if(node->op_ch>='0' && node->op_ch<='9') return 1;
	return terminal_node_count(node->left)+terminal_node_count(node->right);
}


int main() {

	TreeType rt;

	// 후위 표기식 (postfix notation) 문자열. 피연산자: 한 자릿수(0 ~ 9). 연산자: + ,- , *, /
	char str[] = "2 3 * 5 +";

	init_t(&rt);
	
	make_exp_tree(&rt, str);

	printf("\n1. Binary tree inorder traversal: ");
	tree_display(rt.root);
	printf("\n");

	printf("\n2. Evaluation result: %d \n", exp_evaluation(rt.root));
	printf("\n");

	printf("3. Number of descendant nodes: %d \n\n", descendant_node_count(rt.root));

	printf("4. Number of terminal nodes: %d \n\n", terminal_node_count(rt.root));
	printf("\n");

	return 0;
}