fork download
copy 
  1. #include <ctype.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5.  
  6. struct lst {
  7. 	void *data;
  8. 	struct lst *next;
  9. };
  10.  
  11. struct lst *lst_cons(struct lst *elem, struct lst *lst);
  12.  
  13. struct lst *lst_append(struct lst *a, struct lst *b);
  14.  
  15. struct lst *lst_reverse(struct lst *lst);
  16.  
  17. void *alloc(size_t n);
  18.  
  19. int add(const char *s, struct lst *translation);
  20.  
  21. struct lst *translate(const char *s);
  22.  
  23. // --- main -------------------------------------------------------------------
  24.  
  25. void *alloc(size_t n)
  26. {
  27. 	void *r;
  28.  
  29. 	if (!(r = malloc(n))) {
  30. 		fputs("malloc() failed\n", stderr);
  31. 		exit(EXIT_FAILURE);
  32. 	}
  33. 	return r;
  34. }
  35.  
  36. void print(struct lst *tp, FILE *iop)
  37. {
  38. 	while (tp) {
  39. 		fputs(tp->data, iop);
  40. 		fputs(tp->next ? ", " : "\n", iop);
  41. 		tp = tp->next;
  42. 	}
  43. }
  44.  
  45. struct lst *new_translation(const char *s)
  46. {
  47. 	struct lst *tp = alloc(sizeof *tp);
  48.  
  49. 	strcpy(tp->data = alloc(strlen(s) + 1), s);
  50. 	return tp;
  51. }
  52.  
  53. struct lst *tokenise(char *s, int n, FILE *iop)
  54. {
  55. 	const char *delim = " \t\r\n";
  56. 	struct lst *lst = 0;
  57.  
  58. 	while (fgets(s, n, iop)) {
  59. 		for (char *sp = strtok(s, delim); sp; sp = strtok(0, delim))
  60. 			lst = lst_cons(new_translation(sp), lst);
  61. 		if (lst)
  62. 			return lst_reverse(lst);
  63. 	}
  64. 	return 0;
  65. }
  66.  
  67. int main(int argc, char *argv[])
  68. {
  69. 	struct lst *lst;
  70. 	char buf[8192];
  71. 	FILE *iop;
  72.  
  73. 	if (argc != 2 || !(iop = fopen(argv[1], "r"))) {
  74. 		fprintf(stderr, "usage: %s dictionary\n",
  75. 			argv[0] && argv[0][0] ? argv[0] : "translate");
  76. 		return EXIT_FAILURE;
  77. 	}
  78. 	while ((lst = tokenise(buf, sizeof buf, iop))) {
  79. 		if (!lst->next)
  80. 			fprintf(stderr, "%s: missing translation\n",
  81. 				(char *) lst->data);
  82. 		else if (add(lst->data, lst->next))
  83. 			fprintf(stderr, "%s: invalid word\n",
  84. 				(char *) lst->data);
  85. 		free(lst);
  86. 	}
  87. 	fclose(iop);
  88. 	while (scanf("%8191s", buf) == 1)
  89. 		print(translate(buf), stdout);
  90. 	return 0;
  91. }
  92.  
  93. // -- trie --------------------------------------------------------------------
  94.  
  95. struct letter {
  96. 	struct lst *translation;
  97. 	struct letter *link[26];
  98. };
  99.  
  100. static int chartoindex(char c)	// Assumes a sensible charset.
  101. {
  102. 	return isalpha((unsigned char) c) ?
  103. 		tolower((unsigned char) c) - 'a' : -1;
  104. }
  105.  
  106. static struct letter trie;
  107.  
  108. static struct letter *new_letter(void)
  109. {
  110. 	struct letter *lp = alloc(sizeof *lp);
  111.  
  112. 	for (int i = 0; i < sizeof lp->link / sizeof lp->link[0]; i++)
  113. 		lp->link[i] = 0;
  114. 	lp->translation = 0;
  115. 	return lp;
  116. }
  117.  
  118. int add(const char *s, struct lst *translation)
  119. {
  120. 	struct letter *tp = &trie;
  121. 	int i;
  122.  
  123. 	while (*s) {
  124. 		if ((i = chartoindex(*s++)) < 0)
  125. 			return -1;
  126. 		if (!tp->link[i])
  127. 			tp->link[i] = new_letter();
  128. 		tp = tp->link[i];
  129. 	}
  130. 	tp->translation = lst_append(translation, tp->translation);
  131. 	return 0;
  132. }
  133.  
  134. struct lst *translate(const char *s)
  135. {
  136. 	struct letter *tp;
  137. 	int i;
  138.  
  139. 	for (tp = &trie; *s && tp; tp = tp->link[i])
  140. 		if ((i = chartoindex(*s++)) < 0)
  141. 			return 0;
  142. 	return tp ? tp->translation : 0;
  143. }
  144.  
  145. // --- list -------------------------------------------------------------------
  146.  
  147. struct lst *lst_cons(struct lst *elem, struct lst *lst)
  148. {
  149. 	return elem->next = lst, elem;
  150. }
  151.  
  152. struct lst *lst_append(struct lst *a, struct lst *b)
  153. {
  154. 	struct lst *r;
  155.  
  156. 	if (!a)
  157. 		return b;
  158. 	for (r = a; a->next; a = a->next)
  159. 		;
  160. 	a->next = b;
  161. 	return r;
  162. }
  163.  
  164. struct lst *lst_reverse(struct lst *lst)
  165. {
  166. 	struct lst *r, *next;
  167.  
  168. 	for (r = 0; lst; lst = next) {
  169. 		next = lst->next;
  170. 		r = lst_cons(lst, r);
  171. 	}
  172. 	return r;
  173. }
  174.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vGf1qR
language:
C (gcc 8.3)
created:
12 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!