Leetcode atoi (da stringa a intero)

Question

link qui

Includerò una soluzione in Python e C ++ e potrai esaminarne una. Sono principalmente interessato a rivedere il codice C ++ che è una cosa che ho iniziato a imparare di recente; chi non conosce il C ++ può rivedere il codice Python.

---

Dichiarazione problema

Implementa atoiche converte una stringa in un numero intero. La funzione innanzitutto scarta tutti i caratteri di spazio necessari fino a quando non viene trovato il primo carattere diverso da spazi. Quindi, a partire da questo carattere prende un segno più o meno iniziale opzionale seguito da quante più cifre numeriche possibile e le interpreta come un valore numerico. La stringa può contenere caratteri aggiuntivi dopo quelli che formano il numero intero, che vengono ignorati e non hanno alcun effetto sul comportamento di questa funzione. Se la prima sequenza di caratteri non di spaziatura in str non è un numero intero valido, o se non esiste tale sequenza perché str è vuota o contiene solo caratteri di spaziatura, non viene eseguita alcuna conversione. Se non è stato possibile eseguire una conversione valida, viene restituito un valore zero.

Nota:

Solo il carattere spazio ' 'è considerato un carattere spazio vuoto. Supponiamo di avere a che fare con un ambiente che può memorizzare solo interi all'interno dell'intervallo di interi con segno a 32 bit: [−2³¹, 2³¹ - 1]. Se il valore numerico è fuori dall'intervallo di valori rappresentabili, viene restituito 2³¹ - 1 o −2³¹.

Esempio 1:

Input: str = "42"
Output: 42

Esempio 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.

Esempio 3:

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

Esempio 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.

Esempio 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

Sarebbe una buona idea aggiungere test unitari a entrambe le implementazioni, sia per dimostrare che il codice funziona come previsto, sia per consentire refactoring con sicurezza. Includere un numero sufficiente di test per esercitare tutti i requisiti nella specifica (fuori intervallo, caratteri non validi, +/ -/ niente, ecc.).

Rivedrò il codice C ++ in modo più dettagliato.

Ci mancano #include <cctype>, abbiamo bisogno di std::isspace()e std::isdigit(), e #include <stdexcept>.

Il requisito dice che " Solo il carattere spazio" è considerato uno spazio vuoto ", quindi non dovremmo usare std::isspace()quale corrisponderà a un insieme più ampio di caratteri, inclusi i caratteri di nuova riga e di tabulazione.

L'algoritmo è inefficiente: non c'è motivo di attraversare la stringa più di una volta. Possiamo considerare un singolo carattere alla volta, iniziando la conversione quando vediamo il primo carattere non spazio e finendo alla fine delle cifre.

L'uso std::stoi()è probabilmente al di fuori dello spirito di un esercizio come questo: ci si aspetta che tu dimostri la capacità di codificare l'algoritmo di base!

Dobbiamo essere estremamente attenti per evitare l'overflow di numeri interi. Non possiamo controllarlo dopo che è successo, dato che siamo nel mondo di Undefined Behavior, rendendo l' intero programma non specificato! Una possibilità è accumulare il risultato in un tipo senza segno che ha un intervallo più ampio del tipo con segno corrispondente. Ma fai attenzione quando hai a che fare con il valore più negativo nell'intervallo, che non ha un valore positivo corrispondente!

---

Implementazione alternativa

Ecco come risolverei i problemi di cui sopra. Inizia con alcuni test:

#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;
}

Ora implementiamo la funzione. Userò un iteratore attraverso una visualizzazione stringa per questo:

#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;
}

Ci sono ancora alcuni problemi (non mi piacciono i numeri magici codificati), ma questo è più sicuro e più chiaro dell'originale.

Esercizio

Ora cambia l'interfaccia per accettare qualsiasi tipo di tipo di carattere e restituisci un tipo intero desiderato (con valori di saturazione appropriati):

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