字符串转换成整数

Posted on | In |

算法涉及较少，主要是考虑细节

  • 字符串为null或空””
  • -,+判断
  • illegal的字符（字符串中包含非数字）
  • 字符串长度问题，只有’+’或’-‘
  • 溢出问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package StringToInteger;

public class stringToInteger {
public static int convert(String s) throws Exception{
	if(s==null||s.length()==0)
		throw new Exception("illegal number input");
	int result=0;
	int sign=1; 
	float MAX_DIV=Integer.MAX_VALUE/10;
	float MIN_DIV=Integer.MIN_VALUE/10;
	float  MAX_M=Integer.MAX_VALUE%10;
	float  MIN_M=Integer.MIN_VALUE%10;
	char c=s.charAt(0);
	if(c=='-'||c=='+')
	{
		if(c=='-') sign=-1;
		if(s.length()==1) throw new Exception("illegal number input");
	}
for(int i=1;i<s.length();i++)
{
	int digit=s.charAt(i)-'0';
	if(digit>=0&&digit<=9)
	{
		if(sign>0&&(result>MAX_DIV||(result==MAX_DIV&&digit>MAX_M)))
				throw new Exception("number overflow");
		if(sign<0&&(result<MIN_DIV||(result==MIN_DIV&&digit>MIN_M)))
			throw new Exception("number overflow");
			result=result*10+digit;
	}
	else{
		throw new Exception("illegal number input");
	}
	
}
result=sign>0?result:-result;
		return result;
			
	
}
public static void main(String[] args){
	try{
	int a=convert("+11");
	int b=convert("-11");	
	System.out.println(a);
	System.out.println(b);
	
}catch(Exception e)
	{
	e.printStackTrace();
	}
}
}

一般判断溢出会这样判断 digit > INT_MAX - result*10 （先不考虑正负问题），但是这段代码是有问题的。

INT_MAX = 2147483647， 如果输入的字符串是2147483657，那么执行到最后一位时，会有 result*10 = 2147483650 > INT_MAX，此时已经溢出，所以答案必然出错。

对于正数来说，溢出有两种可能：
一种是诸如 2147483650，即 result > MAX/10 的；
一种是诸如 2147483649，即 result == MAX/10 && digit > MAX%10 的。

解决办法

  • 先用result与INT_MAX/10比较，如果result>INT_MAX/10,那么必然溢出
  • 如果result=INT_MAX/10,比较此时的digit位,如果digit>INT_MAX%10,那么也必然溢出

INT_MAX = 2147483647 而 INT_MIN = -2147483648，两者绝对值不相等。因此，正负数溢出的条件不一样，所以代码中用了两个条件来判断溢出情况。

JDK 中 parseInt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/*
 * Integer 类中的 parseInt 函数
 * Copyright (c) 1994, 2010, Oracle and/or its affiliates. All rights reserved.
 */
public static int parseInt (String s) throws NumberFormatException {
    return parseInt(s,10);
}
public static int parseInt(String s, int radix)
            throws NumberFormatException
{
    /*
     * WARNING: This method may be invoked early during VM initialization
     * before IntegerCache is initialized. Care must be taken to not use
     * the valueOf method.
     */
    if (s == null) {
        throw new NumberFormatException( "null");        //判断null的情况
    }
    if (radix < Character. MIN_RADIX) {                  //转换的进制不能小于2
        throw new NumberFormatException( "radix " + radix +
                                        " less than Character.MIN_RADIX");
    }
    if (radix > Character. MAX_RADIX) {               //转换的进制不能大于36
        throw new NumberFormatException( "radix " + radix +
                                        " greater than Character.MAX_RADIX");
    }
    int result = 0;                    //对应整数结果
    boolean negative = false;          //保存整数的正负状态
    int i = 0, len = s.length();
    int limit = -Integer. MAX_VALUE;     //合法数字的上限（下限）
    int multmin;                         //在做乘法计算时能走到的合法上限（下限）
    int digit;     //当前字符对应的数字
    if (len > 0) {
        char firstChar = s.charAt(0);
        if (firstChar < '0') { // Possible leading "+" or "-"
            if (firstChar == '-') {
                negative = true;
                limit = Integer. MIN_VALUE;
            } else if (firstChar != '+')
                throw NumberFormatException. forInputString(s);
            if (len == 1) //不能只有一个"+"或者"-"
                throw NumberFormatException. forInputString(s);
            i++;
        }
        multmin = limit / radix;
        while (i < len) {
            // Accumulating negatively avoids surprises near MAX_VALUE
            digit = Character. digit(s.charAt(i++),radix);     //以指定的进制转换整数字符
            if (digit < 0) {                                   //不能是非数字
                throw NumberFormatException. forInputString(s);
            }
            if (result < multmin) {                         //判断溢出
                throw NumberFormatException. forInputString(s);
            }
            result *= radix;
            if (result < limit + digit) {
                throw NumberFormatException. forInputString(s);
            }
            result -= digit;
        }
    } else {     //字符串不能为""，即长度要大于0
        throw NumberFormatException. forInputString(s);
    }
    return negative ? result : -result;
}
可以看到parseInt(String s)函数调用了parseInt(String s, int radix)，源码中参数的检查，异常输入的判断都非常全面。可以说严谨和巧妙是这段程序最大的特点。比较难懂的可能是溢出判断那一段。

if (result < multmin) {                         //判断溢出
    throw NumberFormatException. forInputString(s);
}
result *= radix;
if (result < limit + digit) {
    throw NumberFormatException. forInputString(s);
}
result -= digit;

JDK 将所有的整数先当做负数来处理了，为什么呢？

我们知道有符号 int 的上下限是-2147483648 ~ 2147483647，可见负数表达的范围比正数多一个，这样就好理解为什么在开头要把 limit 全部表达为负数（下限）。这样的操作减少了后续的判断，可以一步到位，相当于二者选择取其大一样，大的包含了小的，不用像我的代码一样正负数情况都判断一次。同理，那么 multmin 也都是负数了，而且可以认为是只和进制参数 radix 有关系。在这里 multmin 就是-INT_MAX/10，当负数时就是INT_MIN/10。所以与上文类似，第一个条件就是若-result < -INT_MAX/10则是溢出。不满足第一个条件的情况下，result10肯定不会溢出了。所以第二个条件判断若 - result10 < -INT_MAX + digit，则是溢出。

比如对于最大的负数来说，当扫描到最后一位时，result = -214748364，multmin=-214748364
第一个条件result < multmin不满足， 执行result *= radix之后，result = -2147483640
第二个条件result < limit + digit，即 -2147483640<-2147483648+8 也不满足条件。
所以正常输出。