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

typedef struct Node {
    char *text;
    int is_answer;
    struct Node *yes;
    struct Node *no;
} Node;

char *read_line(void) {
    size_t size = 100;
    char *buffer = malloc(size);
    if (!buffer) return NULL;

    int c;
    size_t len = 0;
    while ((c = getchar()) != EOF && c != '\n') {
        if (len == size - 1) {
            size *= 2;
            char *new_buffer = realloc(buffer, size);
            if (!new_buffer) {
                free(buffer);
                return NULL;
            }
            buffer = new_buffer;
        }
        buffer[len++] = c;
    }
    if (len == 0 && c == EOF) {
        free(buffer);
        return NULL;
    }
    buffer[len] = '\0';
    return buffer;
}

int read_knowledge_base(char ***lines_ptr, int *num_lines) {
    int capacity = 100;
    char **lines = malloc(capacity * sizeof(char *));
    if (!lines) return -1;

    int count = 0;
    while (1) {
        char *line = read_line();
        if (!line || line[0] == '\0') break;

        if (count == capacity) {
            capacity *= 2;
            char **new_lines = realloc(lines, capacity * sizeof(char *));
            if (!new_lines) {
                for (int i = 0; i < count; i++) free(lines[i]);
                free(lines);
                return -1;
            }
            lines = new_lines;
        }
        lines[count++] = line;
    }
    *lines_ptr = lines;
    *num_lines = count;
    return 0;
}

Node *build_tree(char **lines, int *index, int num_lines, int *count, int *error) {
    if (*index >= num_lines) {
        *error = 1;
        return NULL;
    }

    Node *node = malloc(sizeof(Node));
    if (!node) {
        *error = 1;
        return NULL;
    }

    node->text = lines[(*index)++];
    node->yes = node->no = NULL;
    node->is_answer = (node->text[0] == '*');

    if (node->is_answer) {
        (*count)++;
    } else {
        node->yes = build_tree(lines, index, num_lines, count, error);
        if (*error) return NULL;

        node->no = build_tree(lines, index, num_lines, count, error);
        if (*error) return NULL;
    }
    return node;
}

void run_knowledge_system(Node *root, int count) {
    printf("Expert z bufetu to vie.\n");
    if (!root) {
        printf("Chybna databaza\n");
        return;
    }

    printf("Pozna %d druhov ovocia a zeleniny.\n", count);
    printf("Odpovedajte 'a' pre prvu moznost alebo 'n' pre druhu moznost.\n");

    Node *node = root;
    while (node) {
        printf("%s\n", node->text);
        if (node->is_answer) {
            printf("Koniec\n");
            return;
        }

        char input[10];
        if (!fgets(input, sizeof(input), stdin)) {
            printf("Koniec vstupu\n");
            return;
        }

        input[strcspn(input, "\n")] = 0;
        if (strcmp(input, "a") == 0) {
            node = node->yes;
        } else if (strcmp(input, "n") == 0) {
            node = node->no;
        } else {
            printf("Nerozumiem\n");
            return;
        }
    }
}

void free_tree(Node *node) {
    if (!node) return;
    if (!node->is_answer) {
        free_tree(node->yes);
        free_tree(node->no);
    }
    free(node);
}

int main(void) {
    char **lines;
    int num_lines;

    if (read_knowledge_base(&lines, &num_lines) != 0 || num_lines == 0) {
        printf("Expert z bufetu to vie.\n");
        printf("Chybna databaza\n");
        return 0;
    }

    int index = 0, count = 0, error = 0;
    Node *root = build_tree(lines, &index, num_lines, &count, &error);

    if (error || index != num_lines || count == 0) {
        printf("Expert z bufetu to vie.\n");
        printf("Chybna databaza\n");
        for (int i = 0; i < num_lines; i++) {
            free(lines[i]);
        }
        free(lines);
        free_tree(root);
        return 0;
    }

    run_knowledge_system(root, count);
    free_tree(root);
    for (int i = 0; i < num_lines; i++) {
        free(lines[i]);
    }
    free(lines);
    return 0;
}