Leetcode atoi (cadena a entero)

Question

enlace aquí

Incluiré una solución en Python y C ++ y puedes revisar una. Lo que más me interesa es revisar el código C ++, que es algo que comencé a aprender recientemente; aquellos que no conocen C ++ pueden revisar el código Python.

---

Planteamiento del problema

Implemento atoique convierte una cadena en un número entero. La función primero descarta tantos caracteres de espacio en blanco como sea necesario hasta que se encuentra el primer carácter que no es de espacio en blanco. Luego, a partir de este carácter se toma un signo más o menos inicial opcional seguido de tantos dígitos numéricos como sea posible, y los interpreta como un valor numérico. La cadena puede contener caracteres adicionales después de los que forman el número entero, que se ignoran y no tienen ningún efecto en el comportamiento de esta función. Si la primera secuencia de caracteres que no son espacios en blanco en str no es un número entero válido, o si tal secuencia no existe porque str está vacía o contiene solo caracteres de espacio en blanco, no se realiza ninguna conversión. Si no se pudo realizar una conversión válida, se devuelve un valor cero.

Nota:

Solo el carácter de espacio ' 'se considera un carácter de espacio en blanco. Suponga que estamos tratando con un entorno que solo podría almacenar enteros dentro del rango de enteros con signo de 32 bits: [−2³¹, 2³¹ - 1]. Si el valor numérico está fuera del rango de valores representables, se devuelve 2³¹ - 1 o −2³¹.

Ejemplo 1:

Input: str = "42"
Output: 42

Ejemplo 2:

Input: str = "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign. Then take as many numerical digits as possible, which gets 42.

Ejemplo 3:

Input: str = "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

Ejemplo 4:

Input: str = "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical digit or a +/- sign. Therefore no valid conversion could be performed.

Ejemplo 5:

Input: str = "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer. Thefore INT_MIN (−231) is returned.

---

str_int.py

def convert(s):
    chars = (c for c in s)
    ss = []
    while True:
        try:
            current = next(chars)
            if (space := current.isspace()) and ss:
                break
            if (pm := current in '+-') and ss:
                break
            if not current.isnumeric() and not pm and not space:
                break
            if not space:
                ss.append(current)
        except StopIteration:
            break
    try:
        number = int(''.join(ss).strip())
        if number < 0:
            return max(-2 ** 31, number)
        return min(2 ** 31 - 1, number)
    except ValueError:
        return 0


if __name__ == '__main__':
    print(convert("    48-"))

str_int.h

#ifndef LEETCODE_STR_TO_INT_H
#define LEETCODE_STR_TO_INT_H

#include <string>

int atoi_impl(const std::string& s, size_t start_idx, size_t end_idx);
int convert_str(const std::string &s);

#endif //LEETCODE_STR_TO_INT_H

str_int.cpp

#include <string>
#include <iostream>


int atoi_impl(const std::string& s, size_t start_idx, size_t end_idx) {
    try {
        return std::stoi(s.substr(start_idx, end_idx));
    }
    catch (const std::out_of_range &e) {
        return (s[start_idx] == '-') ? INT32_MIN : INT32_MAX;
    }
    catch (const std::invalid_argument &e) {
        return 0;
    }
}


int convert_str(const std::string &s) {
    size_t start_idx = 0;
    size_t end_idx = s.size();
    for (size_t i = 0; i < s.size(); ++i) {
        bool digit = std::isdigit(s[i]);
        bool pm = s[i] == '+' || s[i] == '-';
        bool space = std::isspace(s[i]);
        if (i == start_idx && !space && !digit && !pm)
            return 0;
        if ((space || !digit) && i != start_idx) {
            end_idx = i;
            break;
        }
        if (space)
            start_idx++;
    }
    if (start_idx != end_idx)
        return atoi_impl(s, start_idx, end_idx);
    return 0;
}


int main() {
    std::cout << "result1: " << convert_str(" -912332") << "\n";
}

Answer 1

Sería una buena idea agregar pruebas unitarias a ambas implementaciones, tanto para demostrar que el código funciona según lo previsto, como para permitir refactorizaciones con confianza. Incluya suficientes pruebas para ejercitar todos los requisitos en la especificación (fuera de rango, caracteres inválidos, +/ -/ nada, etc.).

Revisaré el código C ++ con más detalle.

Estamos perdidos #include <cctype>, necesarios para std::isspace()y std::isdigit(), y #include <stdexcept>.

El requisito dice que " Sólo el carácter de espacio" se considera un carácter de espacio en blanco ", por lo que no deberíamos usar el std::isspace()que coincidirá con un conjunto más amplio de caracteres, incluyendo nueva línea y tabulación.

El algoritmo es ineficaz: no hay razón para atravesar la cadena más de una vez. Podemos considerar un solo carácter a la vez, comenzando la conversión cuando vemos el primer carácter sin espacio y terminando al final de los dígitos.

El uso std::stoi()probablemente esté fuera del espíritu de un ejercicio como este: ¡se espera que demuestre la capacidad de codificar el algoritmo central!

Debemos tener mucho cuidado para evitar el desbordamiento de enteros. No podemos verificarlo después de que sucedió, ya que estamos en el mundo de Comportamiento indefinido, ¡haciendo que todo el programa no esté especificado! Una posibilidad es acumular el resultado en un tipo sin firmar que tenga un rango mayor que el tipo con signo correspondiente. ¡Pero tenga cuidado al tratar con el valor más negativo del rango, que no tiene un valor positivo correspondiente!

---

Implementación alternativa

Así es como abordaría los problemas anteriores. Comience con algunas pruebas:

#include <iostream>
#include <cstdlib>

#define COMPARE(expected, actual)                       \
    do {                                                \
        if (expected != actual) {                       \
            ret = EXIT_FAILURE;                         \
            std::cerr << "Expected " << (expected)      \
                      << " but got " << (actual)        \
                      << " from " << #actual << '\n';   \
        }                                               \
    } while (0)

int main()
{
    int ret = EXIT_SUCCESS;
    COMPARE(0, convert_str(""));
    COMPARE(0, convert_str("0"));
    COMPARE(0, convert_str("-0"));
    COMPARE(1, convert_str("1"));
    COMPARE(1, convert_str("  1"));
    COMPARE(1, convert_str("1e2"));
    COMPARE(0, convert_str("\t1"));
    COMPARE(-1, convert_str(" -1"));
    COMPARE(-1, convert_str(" -001"));
    COMPARE(2147483647, convert_str("2147483647"));
    COMPARE(2147483647, convert_str("2147483648"));
    COMPARE(-2147483648, convert_str("-2147483648"));
    COMPARE(-2147483648, convert_str("-2147483649"));
    return ret;
}

Ahora implementemos la función. Usaré un iterador a través de una vista de cadena para esto:

#include <cctype>
#include <cstdint>
#include <string_view>
#include <type_traits>

int_fast32_t convert_str(std::string_view s)
{
    uint_fast32_t value = 0;
    bool negative = false;
    auto i = s.begin();
    auto const end = s.end();

    // skip whitespace
    while (i != end && *i == ' ') {
        ++i;
    }
    if (i == end) {
        return 0;
    }

    // handle optional sign indicator
    if (*i == '-') {
        negative = true;
        ++i;
    } else if (*i == '+') {
        ++i;
    }

    // process the digits
    while (i != end && std::isdigit(unsigned(*i))) {
        if (value > 214748364
            || value == 214748364 && *i > '7' + negative) {
            // would overflow
            return negative ? -2147483648 : 2147483647;
        }

        // usual case
        value = value * 10 + (*i - '0');
        ++i;
    }

    // convert to result type
    int_fast32_t signed_value = value;
    return negative ? -signed_value : signed_value;
}

Todavía hay algunos problemas (no me gustan los números mágicos codificados), pero esto es más seguro y claro que el original.

Ejercicio

Ahora cambie la interfaz para aceptar cualquier tipo de tipo de carácter y devuelva un tipo de entero deseado (con los valores de saturación apropiados):

template<typename Integer, typename Char, typename Traits>
Integer convert_str(std::basic_string_view<Char,Traits> s);