2
\$\begingroup\$

link here

I'll include a solution in Python and C++ and you can review one. I'm mostly interested in reviewing the C++ code which is a thing I recently started learning; those who don't know C++ can review the Python code.


Problem statement

Implement atoi which converts a string to an integer. The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value. The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function. If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed. If no valid conversion could be performed, a zero value is returned.

Note:

Only the space character ' ' is considered a whitespace character. Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2³¹, 2³¹ − 1]. If the numerical value is out of the range of representable values, 2³¹ − 1 or −2³¹ is returned.

Example 1:

Input: str = "42"
Output: 42

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

Example 3:

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

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

Example 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";
}
\$\endgroup\$
0
4
\$\begingroup\$

It would be a good idea to add unit tests to both implementations, both to demonstrate that the code works as intended, and to allow refactorings with confidence. Include enough tests to excercise all the requirements in the specification (out of range, invalid characters, +/-/nothing, etc).

I'll review the C++ code in more detail.

We're missing #include <cctype>, needed for std::isspace() and std::isdigit(), and #include <stdexcept>.

The requirement says that "Only the space character ' ' is considered a whitespace character", so we should not be using std::isspace() which will match a wider set of characters, including newline and tab.

The algorithm is inefficient - there's no reason to traverse the string more than once. We can consider a single character at a time, starting conversion when we see the first non-space character, and finishing at the end of the digits.

Using std::stoi() is probably outside the spirit of an exercise such as this - you're expected to demonstrate the ability to code the core algorithm!

We need to be extremely careful to avoid integer overflow. We can't check for it after it's happened, as we're into the world of Undefined Behaviour, making the whole program unspecified! One possibility is to accumulate the result in an unsigned type which has larger range than the corresponding signed type. But be careful when dealing with the most-negative value in the range, which doesn't have a corresponding positive value!


Alternative implementation

Here's how I would address the problems above. Start with some tests:

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

Now let's implement the function. I'll use an iterator through a string view for this:

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

There are still some issues (I don't like the hard-coded magic numbers), but this is both safer and clearer than the original.

Exercise

Now change the interface to accept any kind of character type, and return a desired integer type (with appropriate saturation values):

template<typename Integer, typename Char, typename Traits>
Integer convert_str(std::basic_string_view<Char,Traits> s);
\$\endgroup\$
8
  • \$\begingroup\$ There is a problem with leetcode's platform that causes a runtime error that indicates there is an overflow which does not happen elsewhere and cannot be caught using try and catch I'm mentioning this because I know that stoi() is probably illegal and that's why I overloaded the atoi_impl() function. And regarding the traversal of the string more than once, can you point to where that happens for a second time? Do you mean in atoi_impl()? \$\endgroup\$ – bullseye Nov 13 '20 at 9:33
  • \$\begingroup\$ Actually I was mistaken - it's just harder to follow when split into two functions (convert_str() and atoi_impl(). \$\endgroup\$ – Toby Speight Nov 13 '20 at 12:58
  • \$\begingroup\$ No, I wasn't mistaken - convert_str() goes looking for end_idx, then atoi_impl() starts again at the beginning. \$\endgroup\$ – Toby Speight Nov 13 '20 at 13:00
  • \$\begingroup\$ you're right, I overlooked it while trying several approaches \$\endgroup\$ – bullseye Nov 13 '20 at 13:14
  • 2
    \$\begingroup\$ (5) Don't worry about templates yet if that's beyond your current learning. (4) i is an iterator into the string view; it isn't a pointer, but is designed to be used similarly. (3) I used #define here because it can reproduce its argument as a string (#actual), but that's something of a distraction and you don't need to understand that yet. (2) I don't understand your question. (1) Just luck that your platform happens to define those functions with the includes you have. In general, you need to read each function's documentation to see which include is required. \$\endgroup\$ – Toby Speight Nov 13 '20 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.