将字符串转化为整数（不使用库函数）

港控/mmm° 2022-05-18 01:14 171阅读 0赞

### 题目描述 ###

输入一个由数字组成的字符串，把它转换成整数并输出。例如：输入字符串”123”，输出整数123。   
给定函数原型int StrToInt(String str) ，实现字符串转换成整数的功能，不能使用库函数 Integer.parseInt(str);

### 分析与解法 ###

本题考查的实际上就是字符串转换成整数的问题，或者说是要你自行实现atoi函数。那如何实现把表示整数的字符串正确地转换成整数呢？以”123”作为例子：

*  当我们扫描到字符串的第一个字符’1’时，由于我们知道这是第一位，所以得到数字1。
 *  当扫描到第二个数字’2’时，而之前我们知道前面有一个1，所以便在后面加上一个数字2，那前面的1相当于10，因此得到数字：1\*10+2=12。
 *  继续扫描到字符’3’，’3’的前面已经有了12，由于前面的12相当于120，加上后面扫描到的3，最终得到的数是：12\*10+3=123。

因此，此题的基本思路便是：从左至右扫描字符串，把之前得到的数字乘以10，再加上当前字符表示的数字。

思路有了，你可能不假思索，写下如下代码：

int StrToInt(String str)
    {
        int n = 0;
        int m = str.length();
        int i = 0;
        while (i != m)
        {
            int c = str.charAt(i) - '0';
            n = n * 10 + c;
            i++;
        }
        return n;
    }

显然，上述代码忽略了以下细节：

*  空指针输入：输入的是指针，在访问空指针时程序会崩溃，因此在使用指针之前需要先判断指针是否为空。
 *  正负符号：整数不仅包含数字，还有可能是以’+’或’-‘开头表示正负整数，因此如果第一个字符是’-‘号，则要把得到的整数转换成负整数。
 *  非法字符：输入的字符串中可能含有不是数字的字符。因此，每当碰到这些非法的字符，程序应停止转换。
 *  整型溢出：输入的数字是以字符串的形式输入，因此输入一个很长的字符串将可能导致溢出。

上述其它问题比较好处理，但溢出问题比较麻烦，所以咱们来重点看下溢出问题。

一般说来，当发生溢出时，取最大或最小的int值。即大于正整数能表示的范围时返回MAX\_INT：2147483647 小于负整数能表示的范围时返回MIN\_INT：-2147483648。

我们先设置一些变量：

*  sign用来处理数字的正负，当为正时sign > 0，当为负时sign < 0
 *  n存放最终转换后的结果
 *  c表示当前数字

而后，你可能会编写如下代码段处理溢出问题：

//当发生正溢出时，返回INT_MAX
    if ((sign == '+') && (c > MAX_INT - n * 10))
    {
        n = MAX_INT;
        break;
    }
    //发生负溢出时，返回INT_MIN
    else if ((sign == '-') && (c - 1 > MAX_INT - n * 10))
    {
        n = MIN_INT;
        break;
    }

但当上述代码转换” 10522545459”会出错，因为正常的话理应得到MAX\_INT：2147483647，但程序运行结果将会是：1932610867。

为什么呢？因为当给定字符串” 10522545459”时，而MAX\_INT是2147483647，即MAX\_INT(2147483647) < n10(1052254545\\10)，所以当扫描到最后一个字符‘9’的时候，执行上面的这行代码：

c > MAX_INT - n * 10
    //*10以后 n 已经放不下这个数字了

已无意义，因为此时(MAX\_INT - n \* 10)已经小于0，程序已经出错。

针对这种由于输入了一个很大的数字转换之后会超过能够表示的最大的整数而导致的溢出情况，我们有两种处理方式可以选择：

*  一个取巧的方式是把转换后返回的值n定义成long long，即long long n；
 *  另外一种则是只比较n和MAX\_INT / 10的大小，即： 
    
     *  若n > MAX\_INT / 10，那么说明最后一步转换时，n\*10必定大于MAX\_INT，所以在得知n > MAX\_INT / 10时，当即返回MAX\_INT。
     *  若n == MAX\_INT / 10时，那么比较最后一个数字c跟MAX\_INT % 10的大小，即如果n == MAX\_INT /10且c > MAX\_INT % 10，则照样返回MAX\_INT。

一直以来，我们努力的目的归根结底是为了更好的处理溢出，但上述第二种处理方式考虑到直接计算n\*10 + c 可能会大于MAX\_INT导致溢出，那么便两边同时除以10，只比较n和MAX\_INT / 10的大小，从而巧妙的规避了计算n\*10这一乘法步骤，转换成计算除法MAX\_INT/10代替，不能不说此法颇妙。

如此我们可以写出正确的处理溢出的代码：

c = str.charAt(i) - '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 > Math.abs(MIN_INT) / 10 || (n == Math.abs(MIN_INT) / 10 && c > Math.abs(MIN_INT) % 10)))
    {
        n = MIN_INT;
        break;
    }

从而，字符串转换成整数，完整的参考代码为：

int StrToInt(String str)
    {
        static final int MAX_INT = Integer.MAX_VALUE;
        static final int MIN_INT = Integer.MIN_VALUE;
        int n = 0;
    
        //判断是否输入为空
        if (str.isEmpty())
        {
            return 0;
        }
    
        //处理空格
        str = trimStr(str);
    
        //处理正负
        int sign = 1;
        if (str.charAt(i) == '+' || str.charAt(i) == '-')
        {
            if (str.charAt(i) == '-')
                sign = -1;
            str = str.subString(1);//去除符号位，心里有B数
        }
    
        //确定是数字后才执行循环
        for(int i=0;i<str.length;i++)
        {
            //处理溢出
            int c = str.charAt(i) - '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;
            }
    
            //把之前得到的数字乘以10，再加上当前字符表示的数字。
            n = n * 10 + c;
            i++;
        }
        return sign > 0 ? n : -n;
    }
    
     public String trimStr(String str){
         String val = str.trim();
         StringBuilder sb = new StringBuilder();
         String s2="";
         for (int i =0; i<val.length();i++){
             char t = val.charAt(i);
             if(t != ' ')
             sb.append(t);
         }
         return s2;
     }