Leetcode atoi (string ke integer)

Question

tautan di sini

Saya akan menyertakan solusi dengan Python dan C ++ dan Anda dapat memeriksanya. Saya sangat tertarik untuk meninjau kode C ++ yang merupakan hal yang baru saya pelajari; mereka yang tidak tahu C ++ dapat meninjau kode Python.

---

Pernyataan masalah

Implementasikan atoiyang mengubah string menjadi integer. Fungsi pertama membuang karakter spasi putih sebanyak yang diperlukan hingga karakter non-spasi pertama ditemukan. Kemudian, memulai dari karakter ini mengambil tanda plus atau minus opsional diikuti dengan sebanyak mungkin digit numerik, dan menafsirkannya sebagai nilai numerik. String dapat berisi karakter tambahan setelah yang membentuk bilangan integral, yang diabaikan dan tidak berpengaruh pada perilaku fungsi ini. Jika urutan pertama karakter non spasi dalam str bukan bilangan integral yang valid, atau jika tidak ada urutan seperti itu karena str kosong atau hanya berisi karakter spasi, tidak ada konversi yang dilakukan. Jika tidak ada konversi valid yang dapat dilakukan, nilai nol dikembalikan.

catatan:

Hanya karakter spasi ' 'yang dianggap sebagai karakter spasi. Asumsikan kita berurusan dengan lingkungan yang hanya dapat menyimpan bilangan bulat dalam kisaran bilangan bulat bertanda 32-bit: [−2³¹, 2³¹ - 1]. Jika nilai numerik berada di luar kisaran nilai yang dapat diwakili, 2³¹ - 1 atau −2³¹ dikembalikan.

Contoh 1:

Input: str = "42"
Output: 42

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

Contoh 3:

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

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

Contoh 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

Sebaiknya tambahkan pengujian unit ke kedua implementasi, baik untuk menunjukkan bahwa kode berfungsi sebagaimana mestinya, dan untuk memungkinkan pemfaktoran ulang dengan percaya diri. Sertakan tes yang cukup untuk melatih semua persyaratan dalam spesifikasi (di luar jangkauan, karakter tidak valid, +/ -/ tidak ada, dll).

Saya akan meninjau kode C ++ lebih detail.

Kami hilang #include <cctype>, dibutuhkan untuk std::isspace()dan std::isdigit(), dan #include <stdexcept>.

Persyaratan mengatakan bahwa " Hanya karakter spasi '' dianggap sebagai karakter spasi ", jadi kita tidak boleh menggunakan std::isspace()yang akan cocok dengan kumpulan karakter yang lebih luas, termasuk baris baru dan tab.

Algoritme ini tidak efisien - tidak ada alasan untuk melintasi string lebih dari sekali. Kita dapat mempertimbangkan satu karakter pada satu waktu, memulai konversi ketika kita melihat karakter non-spasi pertama, dan menyelesaikannya di akhir digit.

Penggunaannya std::stoi()mungkin di luar semangat latihan seperti ini - Anda diharapkan menunjukkan kemampuan untuk membuat kode algoritme inti!

Kita harus sangat berhati-hati untuk menghindari overflow integer. Kami tidak dapat memeriksanya setelah itu terjadi, karena kami memasuki dunia Perilaku Tidak Terdefinisi, membuat seluruh program tidak ditentukan! Salah satu kemungkinannya adalah mengakumulasi hasil dalam tipe unsigned yang memiliki jangkauan lebih besar dari tipe bertanda yang sesuai. Namun berhati-hatilah saat menangani nilai paling negatif dalam rentang tersebut, yang tidak memiliki nilai positif yang sesuai!

---

Implementasi alternatif

Begini cara saya mengatasi masalah di atas. Mulailah dengan beberapa tes:

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

Sekarang mari kita implementasikan fungsinya. Saya akan menggunakan iterator melalui tampilan string untuk ini:

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

Masih ada beberapa masalah (saya tidak suka angka ajaib yang di-hardcode), tetapi ini lebih aman dan lebih jelas daripada aslinya.

Olahraga

Sekarang ubah antarmuka untuk menerima semua jenis jenis karakter, dan kembalikan jenis bilangan bulat yang diinginkan (dengan nilai saturasi yang sesuai):

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