#include <stdio.h>
#include <string.h>
#include <stdlib.h>


struct node {
    char text[100];  /* if leaf: animal; if internal: the question */
    struct node *ifyes, *ifno;  /* NULL if it's a leaf node */
};

struct node frog = { "frog", NULL, NULL };
struct node squirrel = { "squirrel", NULL, NULL };
struct node top = { "Is your animal green?", &frog, &squirrel };

extern int yesno();
extern void dumptree(int level, struct node *p);


int main()
{
    extern void guessanimal();
    while (1)
	guessanimal();
}


void guessanimal()
{
    struct node *p = &top;
    char animal[100], question[100], *nl;

    printf("Think of an animal.\n\n");

    while (p->ifyes) { /* (internal node) */
	printf("%s\n", p->text);
	if (yesno())
	    p = p->ifyes;
	else
	    p = p->ifno;
    }

    /* leaf node */

    printf("Is your animal a %s?\n", p->text);
    if (yesno()) {
	printf("I *knew* I could figure it out!\n\n");
	return;
    }

    p->ifyes = (struct node *)malloc(sizeof(struct node));
    p->ifno = (struct node *)malloc(sizeof(struct node));
    if (p->ifyes == NULL || p->ifno == NULL) {
	printf("out of memory!\n");
	exit(1);
    }
    p->ifyes->ifyes = p->ifyes->ifno = NULL;
    p->ifno->ifyes = p->ifno->ifno = NULL;

    printf("What animal were you thinking of?\n");
    fgets(animal, sizeof animal, stdin);
    if ((nl = strchr(animal, '\n')))
	*nl = '\0';  /* to be discussed */
    printf("Tell me a question which would distinguish a %s from a %s.\n",
	    p->text, animal);
    fgets(question, sizeof question, stdin);
    if ((nl = strchr(question, '\n')))
	*nl = '\0';
    printf("Which would be the answer for a %s?\n", animal);
    if (yesno()) {
	strcpy(p->ifyes->text, animal);
	strcpy(p->ifno->text, p->text);
    } else {
	strcpy(p->ifyes->text, p->text);
	strcpy(p->ifno->text, animal);
    }
    strcpy(p->text, question);
    printf("Something nice goes here.\n\n");
}


int yesno()
{
    char line[80];
    while (fgets(line, sizeof line, stdin)) {
	if (strcmp(line, "yes\n") == 0)
	    return 1;
	if (strcmp(line, "no\n") == 0)
	    return 0;
	if (strcmp(line, "DUMP\n") == 0)
	    dumptree(0, &top);
	else
	    printf("Can't you tell that I'm asking you a question??\n");
    }
    exit(0);
}


void dumptree(int level, struct node *p)
{
    printf("%*s", level * 4, "");
    if (p->ifyes) {
	printf("Question: %s\n", p->text);
	printf("%*sIf yes:\n", level * 4, "");
	dumptree(level + 1, p->ifyes);
	printf("%*sIf no:\n", level * 4, "");
	dumptree(level + 1, p->ifno);
    } else {
	printf("It is a %s.\n", p->text);
    }
}