Leetcode atoi (преобразование строки в целое число)

Question

ссылка здесь

Я включу решение на Python и C ++, и вы можете его просмотреть. Меня больше всего интересует анализ кода C ++, который я недавно начал изучать; те, кто не знает C ++, могут просмотреть код Python.

---

Постановка задачи

Реализация, atoiкоторая преобразует строку в целое число. Функция сначала отбрасывает столько пробельных символов, сколько необходимо, пока не будет найден первый непробельный символ. Затем, начиная с этого символа, берет необязательный начальный знак плюс или минус, за которым следует как можно больше числовых цифр, и интерпретирует их как числовое значение. Строка может содержать дополнительные символы после тех, которые образуют целое число, которые игнорируются и не влияют на поведение этой функции. Если первая последовательность непробельных символов в str не является допустимым целым числом или если такая последовательность не существует, потому что строка str пуста или содержит только символы пробела, преобразование не выполняется. Если действительное преобразование не может быть выполнено, возвращается нулевое значение.

Заметка:

Только пробел ' 'считается символом пробела. Предположим, мы имеем дело со средой, которая может хранить только целые числа в диапазоне 32-битных целых чисел со знаком: [−2³¹, 2³¹ - 1]. Если числовое значение выходит за пределы диапазона представимых значений, возвращается 2³¹ - 1 или −2³¹.

Пример 1:

Input: str = "42"
Output: 42

Пример 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.

Пример 3:

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

Пример 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.

Пример 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

Было бы неплохо добавить модульные тесты к обеим реализациям, чтобы продемонстрировать, что код работает так, как задумано, и чтобы обеспечить уверенный рефакторинг. Включите достаточно тестов, чтобы выполнить все требования спецификации (выход за пределы допустимого диапазона, недопустимые символы, +/ -/ ничего и т. Д.).

Я рассмотрю код C ++ более подробно.

Нам не хватает #include <cctype>, мы нуждаемся в std::isspace()и std::isdigit(), и #include <stdexcept>.

Требование гласит, что « только пробел считается символом пробела », поэтому мы не должны использовать тот, std::isspace()который будет соответствовать более широкому набору символов, включая новую строку и табуляцию.

Алгоритм неэффективен - нет смысла проходить строку более одного раза. Мы можем рассматривать один символ за раз, начиная преобразование, когда мы видим первый непробельный символ, и заканчивая концом цифр.

Использование std::stoi(), вероятно, выходит за рамки такого упражнения, как это - вы должны продемонстрировать способность кодировать основной алгоритм!

Нам нужно быть предельно осторожными, чтобы избежать целочисленного переполнения. Мы не можем проверить это после того, как это произошло, поскольку мы находимся в мире неопределенного поведения, что делает всю программу неопределенной! Одна из возможностей - накапливать результат в типе без знака, который имеет больший диапазон, чем соответствующий тип со знаком. Но будьте осторожны, имея дело с наиболее отрицательным значением в диапазоне, которому нет соответствующего положительного значения!

---

Альтернативная реализация

Вот как я бы решил вышеупомянутые проблемы. Начнем с нескольких тестов:

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

Теперь реализуем функцию. Для этого я буду использовать итератор в строковом представлении :

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

Есть еще некоторые проблемы (мне не нравятся жестко запрограммированные магические числа), но это и безопаснее, и понятнее, чем оригинал.

Упражнение

Теперь измените интерфейс, чтобы он принимал любой тип символа и возвращал желаемый целочисленный тип (с соответствующими значениями насыщенности):

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