String to Integer(atoi)

https://leetcode.com/problems/string-to-integer-atoi/

Description

String to Integer (atoi)

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).

The algorithm for myAtoi(string s) is as follows:

1. Read in and ignore any leading whitespace.

2. Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.

3. Read in next the characters until the next non-digit charcter or the end of the input is reached. The rest of the string is ignored.

4. Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).

5. If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1.

6. Return the integer as the final result.

Note:

• Only the space character ' ' is considered a whitespace character.

• Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.

Example 1:

Input: str = "42"
Output: 42
Explanation: The underlined characters are what is read in, the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
         ^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "42" ("42" is read in)
           ^
The parsed integer is 42.
Since 42 is in the range [-231, 231 - 1], the final result is 42.

Example 2:

Input: str = "   -42"
Output: -42
Explanation:
Step 1: "   -42" (leading whitespace is read and ignored)
            ^
Step 2: "   -42" ('-' is read, so the result should be negative)
             ^
Step 3: "   -42" ("42" is read in)
               ^
The parsed integer is -42.
Since -42 is in the range [-231, 231 - 1], the final result is -42.

Example 3:

Input: str = "4193 with words"
Output: 4193
Explanation:
Step 1: "4193 with words" (no characters read because there is no leading whitespace)
         ^
Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "4193 with words" ("4193" is read in; reading stops because the next character is a non-digit)
             ^
The parsed integer is 4193.
Since 4193 is in the range [-231, 231 - 1], the final result is 4193.

Example 4:

Input: str = "words and 987"
Output: 0
Explanation:
Step 1: "words and 987" (no characters read because there is no leading whitespace)
         ^
Step 2: "words and 987" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "words and 987" (reading stops immediately because there is a non-digit 'w')
         ^
The parsed integer is 0 because no digits were read.
Since 0 is in the range [-231, 231 - 1], the final result is 4193.

Example 5:

Input: str = "-91283472332"
Output: -2147483648
Explanation:
Step 1: "-91283472332" (no characters read because there is no leading whitespace)
         ^
Step 2: "-91283472332" ('-' is read, so the result should be negative)
          ^
Step 3: "-91283472332" ("91283472332" is read in)
                     ^
The parsed integer is -91283472332.
Since -91283472332 is less than the lower bound of the range [-231, 231 - 1], the final result is clamped to -231 = -2147483648.

Constraints:

• 0 <= s.length <= 200

• s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.

Even if this function has already be implemented in STL, it is still valuable to know how to write it by yourself. As there is a comment in the discussion part, Ironically, the most disliked problem on LeetCode is the type of problem that you would encounter the most as a real world software developer, we should be diligent to edge cases in this problem. The examples and constraints in this problem are very helpful.

Solution scan from left to right

class Solution {
public:
    int myAtoi(string s) {
        int i = 0;
        int sign = 1;
        int count = 0;// count optional sign number
        int res = 0;
        if (s.empty())return 0;
        
        //Discard whitespaces in the beginning
        while(i < s.size() && s[i] == ' ')
            i++;
        
        //Check if optional sign if it exists
        while(i < s.size() && (s[i] == '+' || s[i] == '-')){
            count++;
            sign = (s[i++] == '-')? -1 : 1;
        }
        if(count>1) count = 0;
        else count = 1;
        
        //Build the result and check for overflow/underflow condition
        while(i < s.size() && s[i]>='0' && s[i]<='9')
        {
            if(res > INT_MAX / 10 || (res == INT_MAX / 10 && s[i] - '0' > INT_MAX % 10)){
                return(sign == 1)? INT_MAX : INT_MIN;
            } 
            res = res * 10 + (s[i++] - '0');
        }
      return res * sign*count;
    }
};

The key of this problem is about edge cases, e.g. overflow and underflow:

Since integer must be within the 32-bit signed integer range.

Handling overflow and underflow conditions

If the integer is positive, for 32 bit signed integer, INT_MAX is 2147483647 (2^31-1). To avoid integer overflow, we must ensure that it doesn't exceed this value. This condition needs to be handled when the result is greater than or equal to INT_MAX/10​ (214748364)

• Case 1). If result = INT\_MAX/10, it would result in integer overflow if next integer character is greater than 7. (7 in this case is last digit of INT_MAX(2147483647). We can use INT_MAX%10 to generically represent the last digit.

• Case 2). If result>INT_MAX​/10, we are sure that adding next number would result in integer overflow.

This holds for negative integer as well. In the 32-bit integer, INT_MIN value is -2147483648 (-2^31). As the last digit is greater than 7 (INT\_MAX% 10), integer underflow can also be handled using the above approach.

We must return INT_MAX in case of integer overflow and INT_MIN in case of integer underflow.

Also, it must be noted that in some languages like Python, an integer value is not restricted by the number of bits. Handling of overflow and underflow won't be required in such cases. We could simply check if the value of an integer is out of specified range [-2^31, 2^31-1]

Steps of the algorithm

1. Discard all the whitespaces at the beginning of the string.

2. There could be an optional sign of a numerical value +/-+/−. It should be noted that the integer is positive by default if there is no sign present and there could be at most one sign character.

3. Build the result using the above algorithm until there exists a non-whitespace character that is a number (00 to 99). Simultaneously, check for overflow/underflow conditions at each step.

Other things need to pay attention

When optional sign is more than 1, the result must be 0.