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 -------------------------------------------------*/