atoi实现 - 一周思进

LeetCode第8题，atoi实现

这一题个人觉得主要是考察越界处理

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−2^31, 2^31 − 1]。如果数值超过这个范围，请返回 INT_MAX (2^31 − 1) 或 INT_MIN (−2^31) 。

代码实现如下：

#include <ctype.h>      // isdigit 头文件
#include <limits.h>     // INT_MAX 头文件

int my_atoi(char *str)
{
    int i = 0;
    int flag = 1;
    unsigned int data = 0;
    int c = 0;

    if (NULL == str)
    {
        return 0;
    }

    while (str[i] == ' ')
    {
        i++;
    }

    if (str[i] == '+')
    {
        i++;
        flag = 1;
    }
    else if (str[i] == '-')
    {
        i++;
        flag = -1;
    }

    while (isdigit(str[i]))
    {
        c = (str[i]-'0');
        if (flag == 1 && (data > INT_MAX/10 || (data == INT_MAX/10 &&  c > INT_MAX%10)))
        {
            return INT_MAX;
        }
        else if (flag == -1 && (data > (unsigned)INT_MIN /10 
                || (data == (unsigned)INT_MIN/10 && c > (unsigned)INT_MIN%10)))
        {
            return INT_MIN;
        }
        else
        {
            data = data * 10 + c;
        }
        i++;
    }
    
    return data * flag;
}

几个点：
1、int型最大值和最小值可以直接用宏INT_MAX和INT_MIN表示，在头文件"limits.h"中定义

2、越界需要通过越界值/10操作提前来进行判断，类似两数相加判断是否会越界，也可以提前通过最大值来减原有值与相加值进行比较

3、这里data需要声明成无符号int整型，否则LeetCode就会出现如下错误：“Line 44: Char 18: runtime error: signed integer overflow: 8 + 2147483640 cannot be represented in type ‘int’ (solution.c)”

但可能你看本地运行并没有错，你输入”-2147483648”，输出的结果也是”-2147483648”,
实际上这个结果是 8 + 2147483640 存放到 int类型的变量后整型溢出变成的”-2147483648”。

然后看官方题解，居然用的是状态机，之前还学习了下状态机，C编程-状态机实现，真不知道还能这么用…

发现按之前写的模板真搞不来，这状态表得写好多行才行…

按题解方式用C语言实现了下，先定义状态和事件：

enum STATE{
    START,
    SIGNED,
    IS_NUMBER,
    END,
};

enum EVENT{
    SPACE,
    SYMBOL,
    NUMBER,
    OTHER,
};

画对应的状态变化表格

当前状态	空格	符号	数字	其他
START	START	SIGNED	IS_NUMBER	END
SIGNED	END	END	IS_NUMBER	END
IS_NUMBER	END	END	IS_NUMBER	END
END	END	END	END	END

/**
 * @brief 根据输入字符返回对应事件
 * 
 * @param c 
 * @param p_event 
 */
void get_event(char c, int *p_event)
{
    if (NULL == p_event)
    {
        return ;
    }

    if (c == ' ')
    {
        *p_event = SPACE;
    }
    else if (c == '+' || c == '-')
    {
        *p_event = SYMBOL;
    }
    else if (isdigit(c))
    {
        *p_event = NUMBER;
    }
    else
    {
        *p_event = OTHER;
    }

    return;
}


int my_atoi(char *str)
{
    int state = START;
    int i = 0;
    int event = 0;
    unsigned int data = 0;
    int flag = 1;
    int c = 0;

    if (NULL == str)
    {
        printf("str is null.\n");
        return 0;
    }

    for (; str[i]; i++)
    {
        get_event(str[i], &event);
        state = type[state][event];

        if (state == END)
        {
            break;
        }
        else if (state == SIGNED)
        {
            if (str[i] == '-')
            {
                flag = -1;
            }
        }
        else if (state == IS_NUMBER)
        {
            c = (str[i]-'0');
            if (flag == 1 && (data > INT_MAX/10 || (data == INT_MAX/10 &&  c > INT_MAX%10)))
            {
                return INT_MAX;
            }
            else if (flag == -1 && (data > (unsigned)INT_MIN /10 
                    || (data == (unsigned)INT_MIN/10 && c > (unsigned)INT_MIN%10)))
            {
                return INT_MIN;
            }
            else
            {
                data = data * 10 + c;
                
            }
        }
    }

    return data * flag;
}

反正这种实现方式个人是觉得挺麻烦的…

日常工作需要注意atoi本身只能返回int类型数据，所以一定要清楚所要处理的字符串数据是否会超过这个大小，如果会超过，可以使用atoll。

FEATURED TAGS