3 * Prosaic C implementation of a `same-fringe' solver.
10 /*----- Utilities ---------------------------------------------------------*/
12 static const char *progname = "?";
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); }
18 /*----- Our node structure ------------------------------------------------*/
26 /* Make a new node and return it. */
27 static struct node *makenode(int data, struct node *left, struct node *right)
29 struct node *n = malloc(sizeof(*n));
31 if (!n) bail("no memory");
32 n->data = data; n->left = left; n->right = right;
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); } }
40 /* Recursive parser, used by `parsetree': read from string, updating `*p' as
43 static struct node *rparsetree(const char **p)
45 struct node *left, *right;
53 if (!data) bail("no data");
54 right = rparsetree(p);
55 if (**p != ')') bail("missing )");
57 return (makenode(data, left, right));
63 /* Parse a tree description from the string `p'.
65 * The syntax is as follows.
67 * tree ::= empty | `(' tree char tree `)'
69 * where the ambiguity is resolved by always treating `(' as starting a tree
70 * if a tree is expected.
72 static struct node *parsetree(const char *p)
74 struct node *n = rparsetree(&p);
76 if (*p) bail("trailing junk");
80 /*----- Iteration ---------------------------------------------------------*/
84 struct node *stack[MAXDEPTH];
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.
91 static void pushnodes(struct nodeiter *ni, struct node *n)
96 assert(sp < MAXDEPTH);
103 /* Return the next node in order for the tree being traversed by NI, or null
104 * if all nodes are exhausted.
106 static struct node *nextnode(struct nodeiter *ni)
113 n = ni->stack[--ni->sp];
114 pushnodes(ni, n->right);
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); }
123 /*------ Fringe operations ------------------------------------------------*/
125 /* Print the characters stored in the tree headed by N to stdout, in
127 static void printfringe(struct node *n)
131 for (iternodes(&ni, n); (n = nextnode(&ni)) != 0; )
136 /* Return nonzero if traversing the trees headed by N and NN respectively
137 * yields the same items in the same order.
139 static int samefringep(struct node *n, struct node *nn)
141 struct nodeiter ni, nni;
143 iternodes(&ni, n); iternodes(&nni, nn);
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);
152 /*----- Main program ------------------------------------------------------*/
154 int main(int argc, char *argv[])
161 n = parsetree(argv[1]);
166 n = parsetree(argv[1]); nn = parsetree(argv[2]);
167 printf("%s\n", samefringep(n, nn) ? "match" : "no match");
168 freetree(n); freetree(nn);
177 /*----- That's all, folks -------------------------------------------------*/