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

typedef struct node {
	char data;
	struct node *next;
} Node;

typedef struct {
	Node *head;
	Node *crnt;
} List;

typedef struct {
	int max;
	int num;
	List stk;
} Stack;

void List_initialize(List *obj)
{
	obj->head = NULL;
	obj->crnt = NULL;
}

void List_finalize(List *obj)
{
	// free all nodes
	Node *p = obj->head;
	while (p) {
		Node *next = p->next;
		free(p);
		p = next;
	}
	obj->head = NULL;
	obj->crnt = NULL;
}

void List_pushBack(List *obj, char data)
{
	// create new node
	Node *newNode = (Node *)malloc(sizeof(Node));
	newNode->data = data;
	newNode->next = NULL;

	if (obj->crnt == NULL) {
		// list is empty
		obj->head = newNode;
	} else {
		// list has at least 1 element(s)
		obj->crnt->next = newNode;
	}
	obj->crnt = newNode;
}

void List_popBack(List *obj)
{
	if (obj->crnt == NULL) {
		// list is empty
		return;
	} else if (obj->head == obj->crnt) {
		// list has only 1 element
		free(obj->crnt);
		obj->head = NULL;
		obj->crnt = NULL;
	} else {
		// list has at least 2 elements
		Node *p = obj->head;
		while (p->next != obj->crnt) {
			p = p->next;
		}
		free(obj->crnt);
		p->next = NULL;
		obj->crnt = p;
	}
}

void Stack_initialize(Stack *obj, int max)
{
	obj->max = max;
	obj->num = 0;
	List_initialize(&obj->stk);
}

void Stack_finalize(Stack *obj)
{
	List_finalize(&obj->stk);
	obj->max = 0;
	obj->num = 0;
}

void Stack_push(Stack *obj, char data)
{
	if (obj->num < obj->max) {
		List_pushBack(&obj->stk, data);
		++obj->num;
	} else {
		fprintf(stderr, "stack is full.");
	}
}

void Stack_pop(Stack *obj)
{
	if (obj->num != 0) {
		List_popBack(&obj->stk);
		--obj->num;
	} else {
		fprintf(stderr, "stack is empty.");
	}
}

char Stack_top(const Stack *obj)
{
	if (obj->num != 0) {
		return obj->stk.crnt->data;
	} else {
		fprintf(stderr, "stack is empty.");
		return '\0';
	}
}

int Stack_isEmpty(const Stack *obj)
{
	return obj->num == 0;
}

int isConsistent(const char *s)
{
	const char * const L_SET = "([{";
	const char * const R_SET = ")]}";

	int result = 1;
	Stack stk;
	Stack_initialize(&stk, 100);

	for ( ; *s; ++s) {
		if (strchr(L_SET, *s)) {
			Stack_push(&stk, *s);
		} else {
			char *p = strchr(R_SET, *s);
			if (p) {
				if (Stack_isEmpty(&stk)) {
					result = 0;
					goto cleanup;
				} else if (Stack_top(&stk) != L_SET[p - R_SET]) {
					result = 0;
					goto cleanup;
				}
				Stack_pop(&stk);
			}
		}
	}
	result = Stack_isEmpty(&stk);

cleanup:
	Stack_finalize(&stk);

	return result;
}

void runTestCase(const char *s)
{
	if (isConsistent(s)) {
		printf("  整合: %s\n", s);
	} else {
		printf("不整合: %s\n", s);
	}
}

int main(void)
{
	runTestCase("(a), [a(b)c], {a(b)cd}{e}");
	runTestCase("(a}, [a(bc], {a(b)cd}[e}");
	runTestCase("({}[()])");
	runTestCase("({])");
	runTestCase("({})])");
	runTestCase("({}[()");
	runTestCase("ab{cd[e(f){g}(h)]i}(j)");
	runTestCase("ab{cd[e(f){g}(h)}i](j)");
	
	return 0;
}