fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. typedef struct node {
  6. 	char data;
  7. 	struct node *next;
  8. } Node;
  9.  
  10. typedef struct {
  11. 	Node *head;
  12. 	Node *crnt;
  13. } List;
  14.  
  15. typedef struct {
  16. 	int max;
  17. 	int num;
  18. 	List stk;
  19. } Stack;
  20.  
  21. void List_initialize(List *obj)
  22. {
  23. 	obj->head = NULL;
  24. 	obj->crnt = NULL;
  25. }
  26.  
  27. void List_finalize(List *obj)
  28. {
  29. 	// free all nodes
  30. 	Node *p = obj->head;
  31. 	while (p) {
  32. 		Node *next = p->next;
  33. 		free(p);
  34. 		p = next;
  35. 	}
  36. 	obj->head = NULL;
  37. 	obj->crnt = NULL;
  38. }
  39.  
  40. void List_pushBack(List *obj, char data)
  41. {
  42. 	// create new node
  43. 	Node *newNode = (Node *)malloc(sizeof(Node));
  44. 	newNode->data = data;
  45. 	newNode->next = NULL;
  46.  
  47. 	if (obj->crnt == NULL) {
  48. 		// list is empty
  49. 		obj->head = newNode;
  50. 	} else {
  51. 		// list has at least 1 element(s)
  52. 		obj->crnt->next = newNode;
  53. 	}
  54. 	obj->crnt = newNode;
  55. }
  56.  
  57. void List_popBack(List *obj)
  58. {
  59. 	if (obj->crnt == NULL) {
  60. 		// list is empty
  61. 		return;
  62. 	} else if (obj->head == obj->crnt) {
  63. 		// list has only 1 element
  64. 		free(obj->crnt);
  65. 		obj->head = NULL;
  66. 		obj->crnt = NULL;
  67. 	} else {
  68. 		// list has at least 2 elements
  69. 		Node *p = obj->head;
  70. 		while (p->next != obj->crnt) {
  71. 			p = p->next;
  72. 		}
  73. 		free(obj->crnt);
  74. 		p->next = NULL;
  75. 		obj->crnt = p;
  76. 	}
  77. }
  78.  
  79. void Stack_initialize(Stack *obj, int max)
  80. {
  81. 	obj->max = max;
  82. 	obj->num = 0;
  83. 	List_initialize(&obj->stk);
  84. }
  85.  
  86. void Stack_finalize(Stack *obj)
  87. {
  88. 	List_finalize(&obj->stk);
  89. 	obj->max = 0;
  90. 	obj->num = 0;
  91. }
  92.  
  93. void Stack_push(Stack *obj, char data)
  94. {
  95. 	if (obj->num < obj->max) {
  96. 		List_pushBack(&obj->stk, data);
  97. 		++obj->num;
  98. 	} else {
  99. 		fprintf(stderr, "stack is full.");
  100. 	}
  101. }
  102.  
  103. void Stack_pop(Stack *obj)
  104. {
  105. 	if (obj->num != 0) {
  106. 		List_popBack(&obj->stk);
  107. 		--obj->num;
  108. 	} else {
  109. 		fprintf(stderr, "stack is empty.");
  110. 	}
  111. }
  112.  
  113. char Stack_top(const Stack *obj)
  114. {
  115. 	if (obj->num != 0) {
  116. 		return obj->stk.crnt->data;
  117. 	} else {
  118. 		fprintf(stderr, "stack is empty.");
  119. 		return '\0';
  120. 	}
  121. }
  122.  
  123. int Stack_isEmpty(const Stack *obj)
  124. {
  125. 	return obj->num == 0;
  126. }
  127.  
  128. int isConsistent(const char *s)
  129. {
  130. 	const char * const L_SET = "([{";
  131. 	const char * const R_SET = ")]}";
  132.  
  133. 	int result = 1;
  134. 	Stack stk;
  135. 	Stack_initialize(&stk, 100);
  136.  
  137. 	for ( ; *s; ++s) {
  138. 		if (strchr(L_SET, *s)) {
  139. 			Stack_push(&stk, *s);
  140. 		} else {
  141. 			char *p = strchr(R_SET, *s);
  142. 			if (p) {
  143. 				if (Stack_isEmpty(&stk)) {
  144. 					result = 0;
  145. 					goto cleanup;
  146. 				} else if (Stack_top(&stk) != L_SET[p - R_SET]) {
  147. 					result = 0;
  148. 					goto cleanup;
  149. 				}
  150. 				Stack_pop(&stk);
  151. 			}
  152. 		}
  153. 	}
  154. 	result = Stack_isEmpty(&stk);
  155.  
  156. cleanup:
  157. 	Stack_finalize(&stk);
  158.  
  159. 	return result;
  160. }
  161.  
  162. void runTestCase(const char *s)
  163. {
  164. 	if (isConsistent(s)) {
  165. 		printf("  整合: %s\n", s);
  166. 	} else {
  167. 		printf("不整合: %s\n", s);
  168. 	}
  169. }
  170.  
  171. int main(void)
  172. {
  173. 	runTestCase("(a), [a(b)c], {a(b)cd}{e}");
  174. 	runTestCase("(a}, [a(bc], {a(b)cd}[e}");
  175. 	runTestCase("({}[()])");
  176. 	runTestCase("({])");
  177. 	runTestCase("({})])");
  178. 	runTestCase("({}[()");
  179. 	runTestCase("ab{cd[e(f){g}(h)]i}(j)");
  180. 	runTestCase("ab{cd[e(f){g}(h)}i](j)");
  181.  
  182. 	return 0;
  183. }
  184.  
Success #stdin #stdout 0s 2380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
  整合: (a), [a(b)c], {a(b)cd}{e}
不整合: (a}, [a(bc], {a(b)cd}[e}
  整合: ({}[()])
不整合: ({])
不整合: ({})])
不整合: ({}[()
  整合: ab{cd[e(f){g}(h)]i}(j)
不整合: ab{cd[e(f){g}(h)}i](j)
https://ideone.com/01PdZo
language:
C (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!