【剑指offer-C++】JZ67：把字符串转换成整数(atoi)

题目描述

描述：写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。传入的字符串可能有以下部分组成:

1.若干空格；
2.（可选）一个符号字符（‘+’ 或 ‘-’）；
3. 数字，字母，符号，空格组成的字符串表达式；
4. 若干空格；

转换算法如下:
1.去掉无用的前导空格；
2.第一个非空字符为+或者-号时，作为该整数的正负号，如果没有符号，默认为正数；
3.判断整数的有效部分：
3.1 确定符号位之后，与之后面尽可能多的连续数字组合起来成为有效整数数字，如果没有有效的整数部分，那么直接返回0；
3.2 将字符串前面的整数部分取出，后面可能会存在存在多余的字符(字母，符号，空格等)，这些字符可以被忽略，它们对于函数不应该造成影响；
3.3 整数超过 32 位有符号整数范围 [−2³¹, 2³¹ − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2³¹的整数应该被调整为 −2³¹ ，大于 2³¹ − 1 的整数应该被调整为 2³¹ − 1；
4.去掉无用的后导空格；

数据范围:
1.0 <=字符串长度<= 100；
2.字符串由英文字母（大写和小写）、数字（0-9）、’ ‘、’+‘、’-’ 和 ‘.’ 组成；

输入："82"
返回值：82

输入："   -12  "
返回值：-12
说明：去掉前后的空格，为-12  

输入："4396 clearlove"
返回值：4396
说明：6后面的字符不属于有效的整数部分，去除，但是返回前面提取的有效部分  

输入："clearlove 4396"
返回值：0

输入："-987654321111"
返回值：-2147483648

解题思路

把字符串转换成整数(atoi)：最直观的想法是，从字符串高位向低位遍历，然后逐个取字符串元素，先将字符转换为整型，再利用数位关系将其转换为数值。在纯数字的情况下，当然可以像这样做，但是本题中含有非法字符，且明确说明，在若干空格后，可能会存在符号，接着出现的一连串数字才是转换为数值的重要部分，如果后面再出现非法字符需要被舍弃。也就是说，字符串1234hello转换为数字则为1234，而字符串hello1234转换为数字是为0，即其是非法的，那么我们就不能从后向前遍历字符串，而应该从前向后遍历字符串。(试错)

idea：使用index标记字符串下标，其初始化为0；使用flag标记正负数，其true表示正数而false表示负数；使用hasNum标记是否已经碰到过数字，其true表示碰到过而false表示没碰到；使用res标记结果，其初始为0；具体做法如下：首先去掉前导空格，然后标记正负数，接着遍历剩余字符：如果遇到空格，则判断是否碰到过数字，如果碰到过则直接break，因为题目中说明是符号后一连串的整数，例如字符串+0 1234，其转换为数字应该是0，反之则直接跳过空格；如果遇到数字，则标记碰到过数字，然后进行越界处理，接着如果没越界则继续计算数值；如果遇到其他非法字符，则直接break；最后根据flag标记的正负数情况来处理结果res，再返回res即可。

// 处理越界 可以学习一下越界处理
if(res>INT_MAX/10||(res==INT_MAX/10 &&(s[index]-'0')>INT_MAX%10))
return flag==true?INT_MAX:INT_MIN;

    int StrToInt(string s) {// 字符串长度int n=s.size();// 字符串下标int index=0;// 标记正负数 true是正数 false是负数bool flag=true;// 标记记录过数字bool hasNum=false;// 记录结果int res=0;// 去除前导空格while(s[index]==' ')index++;// 标记负数if(s[index]=='-'){flag=false;index++;}// 正数 默认也是正数else if(s[index]=='+'){index++;}// 遍历剩余字符while(index<n){// 去除空格if(s[index]==' '){// + 0 1234if(hasNum)break;elseindex++;}// 数字 0-9else if(s[index]>='0'&&s[index]<='9'){// 标记出现数字hasNum=true;// 处理越界if(res>INT_MAX/10||(res==INT_MAX/10 &&(s[index]-'0')>INT_MAX%10))return flag==true?INT_MAX:INT_MIN;res=res*10+(s[index]-'0');index++;}// 非法字符elsebreak;}// 负数if(flag==false)res=-res;return res;}

优化：状态机模型。我们知道，根据上述转换规则来写的话，代码会出现很多判断条件，从而显得十分臃肿。其实，一般涉及到字符串的转换时，可以考虑状态机的解法。有限状态机指的是有限个状态以及这些状态之间的转移，其中转移是由当前状态以及条件得到下一个状态，所以我们首先要考虑有哪几个状态以及有哪些条件，再根据状态个数m和条件个数n绘制出大小为m*n的状态转移矩阵。以该题为例：字符类型无非就是空格、符号+/-、数字0-9、以及其他非法字符；状态无非就是初始状态start、符号位sign、数值number、以及结束end；其状态转移图以及状态转移表如下。

idea：我们可以将上述四个状态映射为数字0、1、2、3，然后使用一个常数矩阵来存储状态转移，接着从头到尾遍历字符串，根据当前的字符类型，进入相应的状态，同时判断是否超过int上下界。

// 其中行表示当前状态 列分别表示遇到空格、符号、数字、非法字符相应的转换状态
vector<vector<int>> states={{0,1,2,3},{1,3,2,3},{3,3,2,3},{3,3,3,3}     // 遇到非法字符直接退出循环故该行可省略
};

int StrToInt(string s) 
{// 其中行表示当前状态 列分别表示遇到空格、符号、数字、非法字符相应的转换状态vector<vector<int>> states={{0,1,2,3},{1,3,2,3},{3,3,2,3}};// 存储结果int res=0;// 标记正负数bool flag=true;// 初始状态为0int state=0;// 字符串长度int n=s.size();// 字符串当前元素char ch;// 从前向后遍历字符串for(int i=0;i<n;i++){// 当前元素ch=s[i];// 遇到空格if(ch==' ')state=states[state][0];// 遇到符号else if(ch=='+'||ch=='-'){state=states[state][1];// 第一次遇到符号if(state==1)flag=(ch=='-')?false:true;// 第二次遇到符号elsebreak;}// 遇到数字else if(ch>='0'&&ch<='9')state=states[state][2];// 遇到非法字符elsebreak;// 非法状态if(state==3)break;// 计算数值if(state==2){// 溢出处理if(res>INT_MAX/10||(res==INT_MAX/10 &&(ch-'0')>INT_MAX%10))return flag==true?INT_MAX:INT_MIN;// 计算数值res=res*10+(ch-'0');}}// 根据flag返回结果return flag==true?res:-res;
}