== 입력파일을 "input.txt"에 넣어야 됨..ㅡㅜ ==

{{{~cpp
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct treeNode* tree_pointer;
typedef struct listNode* list_pointer;

struct listNode{
	tree_pointer child;
	list_pointer ptr;
};

struct treeNode{
	char tag[100];
	char text[100];
	list_pointer link;
};

list_pointer findNull(list_pointer temp)
{
	while(temp->ptr != NULL)
		temp = temp->ptr;
	
	return temp;   // else return temp 를 해야하나~~ -..ㅡ;;
}


tree_pointer insert(tree_pointer ptr, char* tag, char* text) // a = 태그, b = 데이터
{

	tree_pointer node = (tree_pointer)malloc(sizeof(treeNode));
	node->link = NULL;
	strcpy(node->tag, tag);
	if(text == NULL)
		node->text[0] = '\n';
	else
		strcpy(node->text, text);
	
	if(ptr != NULL)
	{	
		list_pointer link_node = (list_pointer)malloc(sizeof(listNode));
		list_pointer temp;
		link_node->child = node;
		link_node->ptr = NULL;
		if(ptr->link == NULL)
			ptr->link = link_node;
		else
		{
			temp = findNull(ptr->link);
			temp->ptr = link_node;
		}
	}

	return node;
	
}

list_pointer search_child(list_pointer list, char * tag)
{
//	list_pointer temp = list;
	char tag_temp[100];
	list_pointer return_list = NULL, temp1, temp2, temp3;
	for(; list; list = list->ptr)
	{
		for(temp1 = list->child->link; temp1; temp1 = temp1->ptr)
		{
			strcpy(tag_temp,temp1->child->tag);
			if(strcmp(tag_temp,tag) == 0 ||
				(tag_temp[strlen(tag_temp)-1] == '/' && (strlen(tag_temp) -1) == strlen(tag) && strncmp(tag_temp,tag,strlen(tag)) == 0)) 
			{
				temp2 = (list_pointer)malloc(sizeof(listNode));
				temp2->child = temp1->child;
				temp2->ptr = NULL;
				if(return_list == NULL)
					return_list = temp2;
				else
					temp3->ptr = temp2;
				temp3 = temp2;
			}
		}
	}
	
	// list 해제
	
	return return_list;	
}

list_pointer search_all(list_pointer list, char * tag)
{
	//	list_pointer temp = list;
	list_pointer return_list = NULL, temp1, temp2, temp3;
	
	if(list)
	{
		temp1 = search_child(list,tag);
		if(temp1)
		{
			if(return_list == NULL)
				return_list = temp1;
			else
			{
				temp2 = findNull(return_list);
				temp2->ptr = temp1;			
			}
		}
		for(; list; list = list->ptr)
		{			
			temp1 = search_all(list->child->link,tag);
			if(temp1)
			{
				if(return_list == NULL)
					return_list = temp1;
				else
				{
					temp2 = findNull(return_list);
					temp2->ptr = temp1;								
				}
			}
		}
	}
	
	// list 해제
	
	return return_list;	
}


void show(tree_pointer ptr, int level)
{
	if(ptr)
	{
		for(int i = 0; i < level; i++)
			printf("  ");
		printf("<%s>",ptr->tag);
		
		if(ptr->text[0] != '\n')
			printf("%s",ptr->text);
		else
		{
			printf("\n");
			for(list_pointer list = ptr->link; list; list = list->ptr)
				show(list->child, level + 1);
		}
		if(ptr->tag[strlen(ptr->tag)-1] != '/')
		{
			if(ptr->text[0] == '\n')
				for(i = 0; i < level; i++)
					printf("  ");
			printf("</%s>\n",ptr->tag);
			
		}
	}
}

void show_list(list_pointer list)
{
	for(;list;list = list->ptr)
		show(list->child,0);
}


#define stack_max 100
#define stack_empty 0

typedef struct stack * stack_pointer;
struct stack
{
	tree_pointer array[stack_max];
	int top;
};

tree_pointer stack_out(stack_pointer sta)
{
	if(sta->top <= stack_empty)
		printf("Stack Empty!!\n");
	return sta->array[--sta->top-1]; 
}

void stack_insert(stack_pointer sta, tree_pointer ptr)
{
	if(sta->top != stack_max)
		sta->array[sta->top++] = ptr;
	else
		printf("Stack Full!!\n");
}

void stack_clear(stack_pointer sta)
{
	sta->top = 0;
}

tree_pointer get_keyword(char *line, stack_pointer sta)
{
	static tree_pointer ptr = NULL;
	
	char seps[] = "<>";
	char * tag, * text = NULL, * temp;
	tag = strtok(line, seps);

	if(tag[0] == ' ')
		tag = strtok(NULL, seps);

	temp = strtok(NULL, seps);
	if(temp[0] == ' ')
	{
		// <tag>
		if(tag[0] != '/')
		{
			// <tag/>
			if(tag[strlen(tag)-1] == '/')
			{
				insert(ptr,tag,text);
			}
			// 트리에 삽입
			else
			{
				ptr = insert(ptr,tag,text);
				stack_insert(sta,ptr);
			} 
		}
		// </tag> 스택을 한칸 증가
		else
		{
			ptr = stack_out(sta);
		}
		return ptr;
	}
	// text입력 처리
	while(strtok(NULL, seps));
	text = strtok(temp, seps);
	// cout << text << endl;
	while(strtok(NULL, seps));
	insert(ptr,tag,text);
	
	return ptr;
}

tree_pointer tree_make(const char * file)
{
	char line[100];
	FILE *stream = fopen(file, "r" );
	tree_pointer root;
	stack_pointer sta = (stack_pointer)malloc(sizeof(stack));
	stack_clear(sta);
	
	fgets(line, 100, stream);
	root = get_keyword(line,sta);
	
	while(fgets(line, 100, stream))
	{
		get_keyword(line,sta);
	}
	
	fclose( stream );
	free(sta);
	
	return root; 
}

void reply_query(char * query, tree_pointer ptr)
{
	char * tag, *temp, check;
	list_pointer list = (list_pointer)malloc(sizeof(listNode));
	list->child = ptr;
	list->ptr = NULL;

	char seps1[] = "/";
	char seps2[] = "\n";
	tag = strtok(query, seps1);
	temp = strtok(NULL, seps2);
	while(temp != NULL)
	{
		check = temp[0];
		tag = strtok(temp, seps1);
		if(check == '/')
			list = search_all(list, tag);
		else
			list = search_child(list, tag);
		temp = strtok(NULL, seps2);
	}
	show_list(list);
}

int main()
{
	char query[100] = "zeropage/studies/java/participants";
	tree_pointer root;
	root = tree_make("input.txt");

	reply_query(query, root);

	// 트리 해제
	return 0;
}
}}}