[8] String to Integer (atoi)

© Jarvus Chen / www.jarvus.net

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.

Required knowledge

Variables type

// In 32-bits system
INT_MAX = +2^32 =  2,147,483,647
INT_MIN = -2^32 = -2,147,483,648

// long long range (2^64)
-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

char to int in ASCII

char zero = '0';
char nine= '9';
int digit0 = zero - 48;
int digit9 = nine - 48;

Then, digit0 is 0 and digit9 is 9.

My solution

I can expect there are many invalid char in the input string. My first stage is to eliminate useless part and then get the starting location as start. Second, use result = result*10 + digit to transfer each char to integer number. The only notice is we have to check variables bound limitation.

int myAtoi(char* str) {

    int size = strlen(str);
    int start = 0;
    int sign = 1;
    int signFlag = 0;
    int count = 0;

    // eliminate invalid char before target numbers
    while ( str[start] == '0' || str[start] == ' ' || str[start] == '+' || str[start] == '-'){
        if ( str[start] == '-'){
            sign = sign*-1;
            signFlag++;
        }else if ( str[start] == '+'){
            signFlag++;
        }
        if ( signFlag > 1){
            return 0;
        }
        start++;
    }
    if ( str[start-1] == ' ' && signFlag != 0){
        return 0;
    }

    // start counting the result value
    long long result = 0;
    for ( int i = start ; i < size  ; i++ ){
        int digit = str[i] - 48;
        if ( digit < 0 || digit > 9 ){
            return checkBound(result, sign);
        }else{
            result = result*10 + digit;
            count++;
            if ( count > 10 ){
                return checkBound(result, sign);
            }
        }
    } 
    result = checkBound(result, sign);
    return result;
}

// check is it out of int and long long limitation
int checkBound(long long input, int sign){

    if ( input*sign > 0 && sign < 0){
        return INT_MIN;
    }else if ( input*sign < 0 && sign > 0){
        return INT_MAX;
    }else if ( input*sign > INT_MAX ){
        return INT_MAX;
    }else if ( input*sign < INT_MIN ){
        return INT_MIN;
    }
    return input*sign;
}

Others solution

https://discuss.leetcode.com/topic/12955/my-c-code-accepted-with-4ms

It check int bound every time. Other, it use *str - '0' to transfer char to int and just str++ to move to the next location.

int myAtoi(char* str) {
    long result = 0;
    int sign = 1;
    //discard the first sequence of whitespace characters.
    while(isspace(*str))
    {
        str++;
    }
    if((*str == '+') || (*str == '-'))
    {
        sign = (*str == '+') ? 1:0;
        str++;
    }
    if(!isdigit(*str))
    {
        return 0;
    }
    while(isdigit(*str) && (result <= INT_MAX))
    {
        result = result * 10 + *str - '0' + 0;
        str++;
    }
    if(result > INT_MAX)
    {
        return sign == 1 ? INT_MAX : INT_MIN;
    }
    return sign == 1 ? result : -result;
}