8. String to Integer (atoi)

Description:

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.

Requirements for atoi:
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. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

Solutions:

Approach 1: Use long to handle the overflow

We need to deal with 4 issues[[1]]:

1. trim leading white spaces
2. number sign
3. overflow
4. invalid input
   [1]:https://discuss.leetcode.com/topic/2666/my-simple-solution?page=1

The 1st problem can be handled in 2 ways:
1.use trim() method of String object or 2. use a pointer to skip all the leading spaces and end up at the first non-whitespace character

The 2nd problem is easy to solve. We just need to see if the first non-whitespace character is '+' or '-'.

The 3rd problem can be handled by using a long variable, once we find the overflow happens, we break the loop and return the max_int or min_int.

The 4th problem is easy, too. Once we meet the non-digit character, we just stop our calculation process.

Here is the solution:

public class Solution {
    public int myAtoi(String str) {
        String s = str.trim();
        if (s.length() == 0 || s == null) return 0;
        boolean positive = true;
        int i = 0;
        if (s.charAt(0) == '-') {
            positive = false;
            i++;
        } else if (s.charAt(0) == '+') {
            i++;
        }
        
        long res = 0;
        while (i < s.length() && (s.charAt(i) >= '0' && s.charAt(i) <= '9')) {
            res = res*10 + s.charAt(i) - '0';
            i++;
            System.out.println("---" + i);
            // Note: you cannot use res > int_max+1
            // becuase int_max+1 will overflow to be int_min
            // why we use res-1 > int_max but not res > int
            // is because we need to handle both int_max and int_min
            if (res-1 > Integer.MAX_VALUE) break;
        }
        
        if (positive) {
            if (res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
            return (int)res;
        } else {
            if (res-1 > Integer.MAX_VALUE) return Integer.MIN_VALUE;
            return ((int)res)*(-1);
        }
    }
}

Approach 2: Use int to handle the overflow

In Approach 1, we check if the overflow happens after each calculation. However, we can "predict" if the overflow will happen before calculation.
As in Approach 1, the calculation process is res = res*10 + s.charAt(i) and the res is always positive through the process. However, when we are going to "add" the next digit character to res, we can check if res is going to overflow by checking:

res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && str.charAt(i) - '0' > 7)

Explanation:

• If res > Integer.MAX_VALUE/10, this will cause res*10 > Integer.MAX_VALUE in the next calculation, so if res > Integer.MAX_VALUE/10, the overflow must happen.
• If res == Integer.MAX_VALUE/10, the overflow may not necessarily happen because if the next digit character is 7 or even small. res*10 + 7 is still can be presented by an int variable. But if the next digit character is greater than 7, it only can be 8 or 9. Then we should take the number sign into consideration. However, if we think it over carefully:
• if the number is positive: whether the next is 8 or 9, res overflows, so we should return Integer.MAX_VALUE immediately.
• if the number is negative: if the next is 8, res does not overflow but would be Integer.MAX_VALUE, at this point we don't have to see if the next character is digit and "add" it to res because the overflow will happen so we should return Integer.MIN_VALUE; if the next is 9, res overflows and we should return Integer.MIN_VALUE. As a result, whether it is 8 or 9, we should return Integer.MIN_VALUE.

So only res == Integer.MAX_VALUE/10 is not enough to say that overflow will happen but res == Integer.MAX_VALUE/10 && s.charAt(i- > '7' will handle it.

The solution is:

public class Solution {
    public int myAtoi(String str) {
        if (str == null || str.isEmpty()) return 0;
        int sign = 1, base = 0, i = 0, n = str.length();
        while (i < n && s.charAt(i) == ' ') i++;
        if (i < n && (str.charAt(i) == '-' || str.charAt(i) == '+'))
            sign = str.charAt(i++) == '-' ? -1 : 1;
        while (i < n && str.charAt(i) >= '0' && str.charAt(i) <= '9') {
            if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && str.charAt(i) - '0' > 7)) {
                return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            res = 10 * res + (str.charAt(i++) - '0');
        }
        return res * sign;
    }
}

Note: every time we call s.charAt(i) we should check if i goes out of the boundary.