【经典算法】字符串转换成整数

本系列为《编程之法：面试和算法心得》的读书笔记。

算法1.3：字符串转换成整数

• 题目描述

  输入一个由数字组成的字符串，把它转换成整数并输出。例如:输入字符串”123”，输出整数为123。给定函数原型 int StrToInt(const char *str)，实现字符串转换成整数的功能，不能使用库函数atoi。

• 分析与解法

思路分析：当扫描字符串的第一个字符“1”时，由于是第一位，故得到数字1；继续向后扫描到第二个字符”2“，之前已经得到数字1，在其后添加一个数字2，得到数字12，相当于前面的数字扩大了10倍然后加上刚扫描到的数字2，即：1×10+2=12。同理，扫描到第三个字符”3“，即可得到最终整数123为所求。故而，其基本思路就是：从左至右扫描字符串，把之前得到的数字乘以10，再加上当前字符表示的数字。 但是，在处理过程中，需要考虑以下问题：

1）空指针的输入：输入的是指针，在访问空指针时程序会崩溃，需要提前判空；
2）正负符号：整数不仅包括数字，还有可能包括以“+”或“-”开头表示正负整数，遇到负号“-”需要做转换；
3）非法字符：输入的字符串中可能有不是数字的字符（如误操作其他字符），需要预先判断，碰到非法字符程序应停止转换；
4）整型溢出：输入的数字是以字符串的形式输入，若输入一个很长的字符串可能导致溢出。

// 算法1.3：字符串转成整数
int StrToInt(const char* str)
{
	static const int MAX_INT = (int)((unsigned)~0 >> 1);
	static const int MIN_INT = -(int)((unsigned)~0 >> 1);
	unsigned int n = 0;

	// 判空
	if(str == 0)
	{
		return 0;
	}

	// 处理空格
	while(isspace(*str))
	{
		++str;
	}
	
	// 处理正负
	int sign = 1;
	if(*str == '+' || *str == '-')
	{
		if(*str == '-')
		{
			sign = -1;
		}
		str++;
	}

	while(isdigit(*str))
	{
		int c = *str - '0';
		if(sign > 0 && (n > MAX_INT/10 || (n == MAX_INT/10 && c > MAX_INT%10)))
		{
			n = MAX_INT;
			break;
		}
		else if(sign < 0 && (n > (unsigned)MIN_INT/10 || (n == (unsigned)MIN_INT/10 && c > (unsigned)MIN_INT%10)))
		{
			n = MIN_INT;
			break;
		}
		
		n = n *10 + c;
		str++;
	}
	return sign > 0 ? n:-n;
}

算法分析：此算法难点在于处理数据溢出，其时间复杂度为 $O(n)$。

• 练习题

实现 string 到 double 的转换。