Leetcode atoi (dizeden tamsayıya)

Question

buraya bağlantı

Python ve C ++ 'da bir çözüm ekleyeceğim ve bir tane inceleyebilirsiniz. Çoğunlukla, yeni öğrenmeye başladığım bir şey olan C ++ kodunu gözden geçirmekle ilgileniyorum; C ++ 'yı bilmeyenler Python kodunu inceleyebilirler.

---

Sorun bildirimi

atoiBir dizeyi tam sayıya dönüştüren uygulama . İşlev, ilk olarak, boşluk olmayan ilk karakter bulunana kadar gerektiği kadar çok boşluk karakterini atar. Daha sonra, bu karakterden başlayarak, isteğe bağlı bir artı veya eksi işareti ve ardından mümkün olduğunca çok sayısal rakam alır ve bunları sayısal bir değer olarak yorumlar. Dize, yok sayılan ve bu işlevin davranışı üzerinde hiçbir etkisi olmayan, integral sayısını oluşturanlardan sonra ek karakterler içerebilir. Str'deki boşluk olmayan karakterlerin ilk dizisi geçerli bir integral sayı değilse veya dizilerden herhangi biri boş olduğundan veya yalnızca boşluk karakterleri içerdiğinden böyle bir dizi yoksa, dönüştürme gerçekleştirilmez. Geçerli bir dönüştürme gerçekleştirilemezse, sıfır değeri döndürülür.

Not:

Yalnızca ' 'boşluk karakteri bir boşluk karakteri olarak kabul edilir. Yalnızca 32 bitlik işaretli tamsayı aralığında tam sayıları depolayabilen bir ortamla uğraştığımızı varsayalım: [−2³¹, 2³¹ - 1]. Sayısal değer gösterilebilir değerler aralığının dışındaysa, 2³¹ - 1 veya −2³¹ döndürülür.

Örnek 1:

Input: str = "42"
Output: 42

Örnek 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.

Örnek 3:

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

Örnek 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.

Örnek 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

Her iki uygulamaya da birim testleri eklemek , hem kodun amaçlandığı gibi çalıştığını göstermek hem de güvenli bir şekilde yeniden düzenlemelere izin vermek için iyi bir fikirdir . Spesifikasyondaki tüm gereksinimleri (aralık dışı, geçersiz karakterler, +/ -/ hiçbir şey, vb.) Uygulamak için yeterli testi dahil edin .

C ++ kodunu daha ayrıntılı olarak inceleyeceğim.

Eksik #include <cctype>, std::isspace()ve için gerekli std::isdigit(), ve #include <stdexcept>.

Gereksinim, " Yalnızca boşluk karakteri '' bir boşluk karakteri olarak kabul edilir " diyor, bu nedenle std::isspace()satırsonu ve sekme dahil daha geniş bir karakter kümesiyle eşleşecek olanı kullanmamalıyız .

Algoritma verimsizdir - dizeyi birden fazla kez geçmek için hiçbir neden yoktur. İlk boşluk olmayan karakteri gördüğümüzde dönüşüme başlayıp rakamların sonunda bitirerek bir seferde tek bir karakter düşünebiliriz.

Kullanmak std::stoi()muhtemelen bunun gibi bir alıştırmanın ruhu dışındadır - çekirdek algoritmayı kodlama yeteneğini göstermeniz beklenir!

Tam sayı taşmasını önlemek için son derece dikkatli olmalıyız. Tanımsız Davranış dünyasına girdiğimizden, tüm programı belirsiz hale getirdiğimizden, gerçekleştikten sonra bunu kontrol edemeyiz ! Bir olasılık, sonucu, karşılık gelen işaretli tipten daha geniş bir menzile sahip olan işaretsiz bir tipte toplamaktır. Ancak aralıktaki, karşılık gelen pozitif bir değeri olmayan en negatif değerle uğraşırken dikkatli olun!

---

Alternatif uygulama

Yukarıdaki sorunları şu şekilde ele alacağım. Bazı testlerle başlayın:

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

Şimdi işlevi uygulayalım. Bunun için bir dize görünümü aracılığıyla bir yineleyici kullanacağım :

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

Hala bazı sorunlar var (sabit kodlanmış sihirli sayılardan hoşlanmıyorum), ancak bu hem daha güvenli hem de orijinalinden daha net.

Egzersiz yapmak

Şimdi arayüzü her tür karakter türünü kabul edecek şekilde değiştirin ve istenen tam sayı türünü (uygun doygunluk değerleriyle) döndürün:

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