mdw@git.distorted.org.uk Git - fringe/blob - c-fringe.c

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