// Verificador del laboratorio: verificador CASO.in CASO.out SALIDA
// Una cadena puede tener varios árboles de derivación, así que la salida no se compara con
// CASO.out como texto. De CASO.out solo se toma si cada cadena se genera o no. Para cada cadena
// que se genera, se comprueba que el árbol entregado es un árbol de derivación de esa cadena:
// la raíz es la variable inicial, cada nodo con sus hijos es una regla de la gramática, y las
// hojas, de izquierda a derecha, forman la cadena.
// Termina con 0 si la salida es correcta. Si no, escribe la razón y termina con 1.
#include <cstddef>
#include <fstream>
#include <iostream>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

struct Cfg {
    std::set<std::string> variables;
    std::set<std::pair<std::string, std::vector<std::string>>> rules;  // (A, lado derecho); A → ε tiene lado derecho vacío
    std::string start;
};

static std::vector<std::string> split_words(const std::string& text) {
    std::istringstream in(text);
    std::vector<std::string> words;
    std::string word;
    while (in >> word) {
        words.push_back(word);
    }
    return words;
}

static int fail(std::size_t string_number, const std::string& message) {
    std::cout << "cadena " << string_number << ": " << message << '\n';
    return 1;
}

// La salida como lista de palabras. Los corchetes son palabras por sí solos.
static std::vector<std::string> tokens_of(std::istream& in) {
    std::vector<std::string> tokens;
    std::string current;
    char c = 0;
    while (in.get(c)) {
        bool space = (c == ' ' || c == '\n' || c == '\t' || c == '\r');
        if (space || c == '[' || c == ']') {
            if (!current.empty()) {
                tokens.push_back(current);
                current.clear();
            }
            if (!space) {
                tokens.push_back(std::string(1, c));
            }
        } else {
            current += c;
        }
    }
    if (!current.empty()) {
        tokens.push_back(current);
    }
    return tokens;
}

// Lee un árbol [A hijo hijo …] a partir de tokens[at] y comprueba cada nodo contra las reglas.
// Agrega sus hojas a leaves y deja en root la variable de la raíz. Si algo falla, deja la razón en error.
static bool read_tree(const Cfg& g, const std::vector<std::string>& tokens, std::size_t& at, std::string& root,
                      std::string& leaves, std::string& error, int depth) {
    if (depth > 100000) {
        error = "el árbol es demasiado profundo";
        return false;
    }
    if (at >= tokens.size() || tokens[at] != "[") {
        error = "se esperaba [ al empezar un árbol";
        return false;
    }
    at++;
    if (at >= tokens.size() || g.variables.count(tokens[at]) == 0) {
        error = "después de [ va una variable" + (at < tokens.size() ? ", y hay " + tokens[at] : std::string());
        return false;
    }
    root = tokens[at];
    at++;
    std::vector<std::string> body;
    bool eps = false;
    while (at < tokens.size() && tokens[at] != "]") {
        if (tokens[at] == "[") {
            std::string child;
            if (!read_tree(g, tokens, at, child, leaves, error, depth + 1)) {
                return false;
            }
            body.push_back(child);
        } else if (tokens[at] == "eps") {
            eps = true;
            at++;
        } else {
            // Una hoja es un terminal: un solo carácter que no es una variable.
            if (tokens[at].size() != 1 || g.variables.count(tokens[at]) > 0) {
                error = "una hoja debe ser un terminal, y hay " + tokens[at];
                return false;
            }
            body.push_back(tokens[at]);
            leaves += tokens[at];
            at++;
        }
    }
    if (at >= tokens.size()) {
        error = "falta ] para cerrar el árbol de " + root;
        return false;
    }
    at++;
    if (eps && !body.empty()) {
        error = "eps solo puede ser el único hijo de un nodo";
        return false;
    }
    if (g.rules.count({root, body}) == 0) {
        std::string text;
        for (const std::string& symbol : body) {
            text += " " + symbol;
        }
        error = "el nodo " + root + " ->" + (body.empty() ? " eps" : text) + " no es una regla de la gramática";
        return false;
    }
    return true;
}

int main(int argc, char** argv) {
    if (argc != 4) {
        std::cout << "uso: verificador CASO.in CASO.out SALIDA\n";
        return 2;
    }
    std::ifstream input(argv[1]);
    std::ifstream expected(argv[2]);
    std::ifstream output(argv[3]);
    if (!input || !expected || !output) {
        std::cout << "no se pudo abrir alguno de los archivos\n";
        return 2;
    }

    // La gramática y las cadenas del caso.
    Cfg g;
    std::vector<std::string> strings;
    std::string line;
    while (std::getline(input, line)) {
        if (!line.empty() && line[0] == '#') {
            continue;
        }
        std::vector<std::string> words = split_words(line);
        if (words.empty() || words[0] == "terminals:" || words[0] == "rules:") {
            continue;
        }
        if (words[0] == "variables:") {
            g.variables.insert(words.begin() + 1, words.end());
        } else if (words[0] == "start:") {
            g.start = words[1];
        } else if (words[0] == "strings:") {
            int count = std::stoi(words[1]);
            for (int s = 0; s < count; s++) {
                std::string w;
                std::getline(input, w);
                strings.push_back(w);
            }
            break;
        } else {
            std::vector<std::string> body;
            for (std::size_t i = 2; i <= words.size(); i++) {
                if (i < words.size() && words[i] != "|") {
                    if (words[i] != "eps") {
                        body.push_back(words[i]);
                    }
                    continue;
                }
                g.rules.insert({words[0], body});
                body.clear();
            }
        }
    }

    // Qué cadenas se generan, según la respuesta esperada. El árbol de CASO.out no se usa.
    std::vector<bool> generated;
    while (std::getline(expected, line)) {
        std::vector<std::string> words = split_words(line);
        if (words.size() == 1 && words[0] == "genera") {
            generated.push_back(true);
        } else if (words.size() == 2 && words[0] == "no" && words[1] == "genera") {
            generated.push_back(false);
        }
    }
    if (generated.size() != strings.size()) {
        std::cout << "el archivo de respuestas no corresponde al caso\n";
        return 2;
    }

    std::vector<std::string> tokens = tokens_of(output);
    std::size_t at = 0;
    for (std::size_t s = 0; s < strings.size(); s++) {
        const std::string shown = strings[s].empty() ? "la cadena vacía" : strings[s];
        if (at >= tokens.size()) {
            return fail(s + 1, "falta la respuesta");
        }
        if (tokens[at] == "no" && at + 1 < tokens.size() && tokens[at + 1] == "genera") {
            at += 2;
            if (generated[s]) {
                return fail(s + 1, "dice no genera, y la gramática sí genera " + shown);
            }
            continue;
        }
        if (tokens[at] != "genera") {
            return fail(s + 1, "se esperaba genera o no genera, y hay " + tokens[at]);
        }
        at++;
        if (!generated[s]) {
            return fail(s + 1, "dice genera, y la gramática no genera " + shown);
        }
        std::string root, leaves, error;
        if (!read_tree(g, tokens, at, root, leaves, error, 0)) {
            return fail(s + 1, error);
        }
        if (root != g.start) {
            return fail(s + 1, "la raíz del árbol es " + root + ", y debe ser la variable inicial " + g.start);
        }
        if (leaves != strings[s]) {
            return fail(s + 1, "las hojas del árbol forman " + (leaves.empty() ? std::string("la cadena vacía") : leaves) +
                                   ", y la cadena es " + shown);
        }
    }
    if (at != tokens.size()) {
        std::cout << "sobra salida después de la última respuesta: " << tokens[at] << '\n';
        return 1;
    }
    return 0;
}
