// Un parser de verdad, en pequeño: expresiones aritméticas con números, +, * y paréntesis.
// Tiene las dos etapas de siempre. El lexer parte el texto en tokens con un autómata finito.
// El parser descendente recursivo tiene una función por variable de la gramática sin ambigüedad
//   E → E + T | T      T → T * F | F      F → ( E ) | número
// y lee cada token una sola vez, de izquierda a derecha.
#ifndef EXPR_H
#define EXPR_H

#include <cstddef>
#include <limits>
#include <stdexcept>
#include <string>
#include <vector>

enum class TokenKind { Number, Plus, Star, LParen, RParen, End };

struct Token {
    TokenKind kind = TokenKind::End;
    std::string text;     // el texto del token: "42", "+", "("
    std::size_t pos = 0;  // dónde empieza, contando desde 0
};

// El lexer. Es un DFA con dos estados: fuera de un número y dentro de un número.
// Los tokens son los de las expresiones regulares [0-9]+, \+, \*, \( y \); los espacios se saltan.
// Siempre termina la lista con un token End.
inline std::vector<Token> lex(const std::string& text) {
    std::vector<Token> tokens;
    std::size_t i = 0;
    while (i < text.size()) {
        char c = text[i];
        if (c == ' ') {
            i++;
        } else if (c >= '0' && c <= '9') {
            std::size_t begin = i;
            while (i < text.size() && text[i] >= '0' && text[i] <= '9') {
                i++;
            }
            tokens.push_back({TokenKind::Number, text.substr(begin, i - begin), begin});
        } else if (c == '+') {
            tokens.push_back({TokenKind::Plus, "+", i++});
        } else if (c == '*') {
            tokens.push_back({TokenKind::Star, "*", i++});
        } else if (c == '(') {
            tokens.push_back({TokenKind::LParen, "(", i++});
        } else if (c == ')') {
            tokens.push_back({TokenKind::RParen, ")", i++});
        } else {
            throw std::runtime_error("columna " + std::to_string(i + 1) + ": el carácter " + std::string(1, c) +
                                     " no forma ningún token");
        }
    }
    tokens.push_back({TokenKind::End, "", text.size()});
    return tokens;
}

// Lo que el parser devuelve por cada subexpresión: su valor y su árbol, escrito con todos los paréntesis.
struct Parsed {
    long long value = 0;
    std::string tree;
};

// El parser. next es la posición del token que toca leer: solo avanza.
struct Parser {
    std::vector<Token> tokens;
    std::size_t next = 0;
    std::size_t calls = 0;  // llamadas a expression, term y factor

    const Token& peek() const { return tokens[next]; }

    [[noreturn]] void fail(const std::string& expected) const {
        const Token& token = peek();
        std::string got = token.kind == TokenKind::End ? "el final" : token.text;
        throw std::runtime_error("columna " + std::to_string(token.pos + 1) + ": se esperaba " + expected +
                                 " y llegó " + got);
    }

    // E → E + T | T. La recursión por la izquierda se vuelve un ciclo: un T, y después cero o
    // más veces "+ T". Cada vuelta agrupa hacia la izquierda, como la regla E → E + T.
    Parsed expression() {
        calls++;
        Parsed left = term();
        while (peek().kind == TokenKind::Plus) {
            next++;
            Parsed right = term();
            if (left.value > std::numeric_limits<long long>::max() - right.value) {
                throw std::runtime_error("el resultado no cabe en 64 bits");
            }
            left = {left.value + right.value, "(" + left.tree + " + " + right.tree + ")"};
        }
        return left;
    }

    // T → T * F | F, con el mismo ciclo.
    Parsed term() {
        calls++;
        Parsed left = factor();
        while (peek().kind == TokenKind::Star) {
            next++;
            Parsed right = factor();
            if (right.value != 0 && left.value > std::numeric_limits<long long>::max() / right.value) {
                throw std::runtime_error("el resultado no cabe en 64 bits");
            }
            left = {left.value * right.value, "(" + left.tree + " * " + right.tree + ")"};
        }
        return left;
    }

    // F → ( E ) | número. El token que viene decide la regla: no hay nada que adivinar.
    Parsed factor() {
        calls++;
        if (peek().kind == TokenKind::Number) {
            const std::string& text = tokens[next++].text;
            if (text.size() > 18) {
                throw std::runtime_error("el número " + text + " no cabe en 64 bits");
            }
            return {std::stoll(text), text};
        }
        if (peek().kind == TokenKind::LParen) {
            next++;
            Parsed inside = expression();
            if (peek().kind != TokenKind::RParen) {
                fail(")");
            }
            next++;
            return inside;
        }
        fail("un número o (");
    }
};

// Analiza la lista completa de tokens. Lanza std::runtime_error si no es una expresión.
inline Parsed parse(const std::vector<Token>& tokens, std::size_t* calls = nullptr) {
    Parser parser;
    parser.tokens = tokens;
    Parsed result = parser.expression();
    if (parser.peek().kind != TokenKind::End) {
        parser.fail("+, * o el final");
    }
    if (calls != nullptr) {
        *calls = parser.calls;
    }
    return result;
}

#endif
