Commit | Line | Data |
---|---|---|
2bd37ef1 MW |
1 | /* -*-c-*- |
2 | * | |
3 | * Prosaic C implementation of a `same-fringe' solver. | |
4 | */ | |
5 | ||
6 | #include <assert.h> | |
7 | #include <stdio.h> | |
8 | #include <stdlib.h> | |
9 | ||
10 | /*----- Utilities ---------------------------------------------------------*/ | |
11 | ||
12 | static const char *progname = "?"; | |
13 | ||
14 | /* Mournfully announce an error and quit. */ | |
15 | static void bail(const char *m) | |
16 | { fprintf(stderr, "%s: %s\n", progname, m); exit(EXIT_FAILURE); } | |
17 | ||
18 | /*----- Our node structure ------------------------------------------------*/ | |
19 | ||
20 | struct node { | |
21 | struct node *left; | |
22 | struct node *right; | |
23 | int data; | |
24 | }; | |
25 | ||
26 | /* Make a new node and return it. */ | |
27 | static struct node *makenode(int data, struct node *left, struct node *right) | |
28 | { | |
29 | struct node *n = malloc(sizeof(*n)); | |
30 | ||
31 | if (!n) bail("no memory"); | |
32 | n->data = data; n->left = left; n->right = right; | |
33 | return (n); | |
34 | } | |
35 | ||
36 | /* Free node N and its subtrees. */ | |
37 | static void freetree(struct node *n) | |
38 | { if (n) { freetree(n->left); freetree(n->right); free(n); } } | |
39 | ||
40 | /* Recursive parser, used by `parsetree': read from string, updating `*p' as | |
41 | * we go. | |
42 | */ | |
43 | static struct node *rparsetree(const char **p) | |
44 | { | |
45 | struct node *left, *right; | |
46 | int data; | |
47 | ||
48 | switch (**p) { | |
49 | case '(': | |
50 | (*p)++; | |
51 | left = rparsetree(p); | |
52 | data = *(*p)++; | |
53 | if (!data) bail("no data"); | |
54 | right = rparsetree(p); | |
55 | if (**p != ')') bail("missing )"); | |
56 | (*p)++; | |
57 | return (makenode(data, left, right)); | |
58 | default: | |
59 | return (0); | |
60 | } | |
61 | } | |
62 | ||
63 | /* Parse a tree description from the string `p'. | |
64 | * | |
65 | * The syntax is as follows. | |
66 | * | |
67 | * tree ::= empty | `(' tree char tree `)' | |
68 | * | |
69 | * where the ambiguity is resolved by always treating `(' as starting a tree | |
70 | * if a tree is expected. | |
71 | */ | |
72 | static struct node *parsetree(const char *p) | |
73 | { | |
74 | struct node *n = rparsetree(&p); | |
75 | ||
76 | if (*p) bail("trailing junk"); | |
77 | return (n); | |
78 | } | |
79 | ||
80 | /*----- Iteration ---------------------------------------------------------*/ | |
81 | ||
82 | struct nodeiter { | |
83 | #define MAXDEPTH 64 | |
84 | struct node *stack[MAXDEPTH]; | |
85 | int sp; | |
86 | }; | |
87 | ||
88 | /* Helper for `nextnode' and `iternodes'. If N is not null, push it onto | |
89 | * NI's stack, and then do the same for N's left child. | |
90 | */ | |
91 | static void pushnodes(struct nodeiter *ni, struct node *n) | |
92 | { | |
93 | int sp = ni->sp; | |
94 | ||
95 | while (n) { | |
96 | assert(sp < MAXDEPTH); | |
97 | ni->stack[sp++] = n; | |
98 | n = n->left; | |
99 | } | |
100 | ni->sp = sp; | |
101 | } | |
102 | ||
103 | /* Return the next node in order for the tree being traversed by NI, or null | |
104 | * if all nodes are exhausted. | |
105 | */ | |
106 | static struct node *nextnode(struct nodeiter *ni) | |
107 | { | |
108 | struct node *n; | |
109 | ||
110 | if (!ni->sp) | |
111 | return (0); | |
112 | else { | |
113 | n = ni->stack[--ni->sp]; | |
114 | pushnodes(ni, n->right); | |
115 | return (n); | |
116 | } | |
117 | } | |
118 | ||
119 | /* Initialize NI as an iterator iterating over the tree headed by N. */ | |
120 | static void iternodes(struct nodeiter *ni, struct node *n) | |
121 | { ni->sp = 0; pushnodes(ni, n); } | |
122 | ||
123 | /*------ Fringe operations ------------------------------------------------*/ | |
124 | ||
125 | /* Print the characters stored in the tree headed by N to stdout, in | |
126 | * order. */ | |
127 | static void printfringe(struct node *n) | |
128 | { | |
129 | struct nodeiter ni; | |
130 | ||
131 | for (iternodes(&ni, n); (n = nextnode(&ni)) != 0; ) | |
132 | putchar(n->data); | |
133 | putchar('\n'); | |
134 | } | |
135 | ||
136 | /* Return nonzero if traversing the trees headed by N and NN respectively | |
137 | * yields the same items in the same order. | |
138 | */ | |
139 | static int samefringep(struct node *n, struct node *nn) | |
140 | { | |
141 | struct nodeiter ni, nni; | |
142 | ||
143 | iternodes(&ni, n); iternodes(&nni, nn); | |
144 | for (;;) { | |
145 | n = nextnode(&ni); nn = nextnode(&nni); | |
146 | if (!n) return (!nn); | |
147 | else if (!nn) return (0); | |
148 | else if (n->data != nn->data) return (0); | |
149 | } | |
150 | } | |
151 | ||
152 | /*----- Main program ------------------------------------------------------*/ | |
153 | ||
154 | int main(int argc, char *argv[]) | |
155 | { | |
156 | struct node *n, *nn; | |
157 | ||
158 | progname = argv[0]; | |
159 | switch (argc) { | |
160 | case 2: | |
161 | n = parsetree(argv[1]); | |
162 | printfringe(n); | |
163 | freetree(n); | |
164 | break; | |
165 | case 3: | |
166 | n = parsetree(argv[1]); nn = parsetree(argv[2]); | |
167 | printf("%s\n", samefringep(n, nn) ? "match" : "no match"); | |
168 | freetree(n); freetree(nn); | |
169 | break; | |
170 | default: | |
171 | bail("bad args"); | |
172 | break; | |
173 | } | |
174 | return (0); | |
175 | } | |
176 | ||
177 | /*----- That's all, folks -------------------------------------------------*/ |