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

#define MAXLINE 256

typedef struct TreeNode {
    char text[MAXLINE];
    struct TreeNode *yes_branch;
    struct TreeNode *no_branch;
} TreeNode;

static TreeNode* read_tree_node() {
    char buffer[MAXLINE];

    if (!fgets(buffer, sizeof(buffer), stdin))
        return NULL;

    if (buffer[0] == '\n' || buffer[0] == '\r')
        return NULL;

    TreeNode *node = calloc(1, sizeof(TreeNode));
    if (!node)
        exit(1);

    strncpy(node->text, buffer, MAXLINE - 1);

    if (node->text[0] == '*') {
        node->yes_branch = NULL;
        node->no_branch = NULL;
        return node;
    }

    node->yes_branch = read_tree_node();
    node->no_branch = read_tree_node();
    return node;
}

static void free_tree(TreeNode *root) {
    if (!root) return;
    free_tree(root->yes_branch);
    free_tree(root->no_branch);
    free(root);
}

static int count_leafs(TreeNode *root) {
    if (!root) return 0;
    if (!root->yes_branch && !root->no_branch)
        return 1;
    return count_leafs(root->yes_branch) + count_leafs(root->no_branch);
}

static int validate_tree(TreeNode *root) {
    if (!root) return 0;

    int is_leaf = (root->text[0] == '*');

    if (is_leaf) {
        if (root->yes_branch || root->no_branch)
            return 0;
        return 1;
    }

    if (!root->yes_branch || !root->no_branch)
        return 0;

    return validate_tree(root->yes_branch) && validate_tree(root->no_branch);
}

static void run_dialog(TreeNode *root) {
    if (!root) return;

    printf("%s", root->text);

    if (!root->yes_branch && !root->no_branch) {
        printf("Koniec\n");
        return;
    }

    char c;
    if (scanf(" %c", &c) != 1) {
        printf("Koniec vstupu\n");
        return;
    }

    if (c == 'a') {
        run_dialog(root->yes_branch);
    } else if (c == 'n') {
        run_dialog(root->no_branch);
    } else {
        printf("Nerozumiem\n");
    }
}

int main() {
    TreeNode *root = read_tree_node();

    printf("Expert z bufetu to vie.\n");

    if (!root || !validate_tree(root)) {
        printf("Chybna databaza\n");
        free_tree(root);
        return 0;
    }

    char chk[MAXLINE];
    if (!fgets(chk, sizeof(chk), stdin)) {
        printf("Chybna databaza\n");
        free_tree(root);
        return 0;
    }
    if (!(chk[0] == '\n' || chk[0] == '\r')) {
        printf("Chybna databaza\n");
        free_tree(root);
        return 0;
    }

    int total = count_leafs(root);

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

    run_dialog(root);

    free_tree(root);
    return 0;
}