#1.字符串转整数

2017-05-31

要求：

把一个字符串转变成整数： eg. “19088” -> 19088, “-123” -> -123

考虑：

  1. 空指针
  2. 符号的正负
  3. 是包含非法字符：-, 0~9之外的。
  4. 结果是否溢出

知识点：

  1. 字符串指针： 

    1
    const char* strs[10] = {"aaa", "bb", nullptr, ..., "123"}

  2. 字符串指针操作: 

    1
    2
    3
    char* s; 
    s++; // 指针后移一位
    while(*s != 0){} // 是否到字符串尾部'\0'

  3. 有符号整数（int）的范围：[-2^31, 0), [0, 2^31 - 1)
    2147483647 -2147483648
    +0, -0 占了两个名额，所以2^31-1

  4. 判断 a + x 是否会溢出： 

    1
    2
    3
    4
    // a + x > INT_MAX
    if(x > 0 && (a > INT_MAX - x)) return true;
    // a + x < INT_MIN
    if(x < 0 && (a < INT_MIN - x)) return true;

  5. 判断 a * x 是否会溢出： 

    1
    2
    3
    4
    // a * x > INT_MAX
    if(x > 0 && (a > INT_MAX / x)) return true;
    // a * x < INT_MIN
    if(x < 0 && (a < INT_MIN / x)) return true;

代码：

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
/*
* Prob: 字符串转nt
* Idea: overflow, null, illegal char, negtative.
* Time: O(len(s))
* Space: O(len(s))
* Mistakes: 指针++，而不是*s++;
* 2017-05-31
*/
#include<bits/stdc++.h>
using namespace std;
bool will_overflow(int a, int x, const char* type){
    if(strcmp(type, "add")){
        if(x > 0 && (a > INT_MAX - x)) return true;
        if(x < 0 && (a < INT_MIN - x)) return true;
    }else{
        if(x > 0 && (a > INT_MAX / x)) return true;
        if(x < 0 && (a < INT_MIN / x)) return true;
    }
    return false;
}
int str2int(const char* s){
    if(s == nullptr) {cout<<"null!"<<endl; return -1;}
    bool neg = false;
    if(*s == '-') neg = true;
    int number = 0;
    while(*s != 0){
        if(*s == '-') {s++;continue;}
        if(*s > '9' || *s <'0'){ cout<<"illegal str!"<<endl; return -1;}
        if(!will_overflow(number, 10, "mul")){
            number = number * 10;
            int d = *s - '0';
            if(!will_overflow(number, d, "add")) {number += d;}
            else {cout<<"overflow!"<<endl; return -1;}
        }else {cout<<"overflow!"<<endl; return -1;}
        s++;
    }
    if(neg) number = -number;
    return number;
}
int main(){
    const char* strs[10] = {"-0", "0", nullptr,  "-18997", "-018997", "1232", "0018997", "9.34", "78dd90", "122139142182951451345134"};
    for(int i=0; i<10; i++)
        cout<<i<<':'<<str2int(strs[i])<<endl;
    return 0;
}