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。