字符串轉換成整數(shù)

題目描述：

輸入一個由數(shù)字組成的字符串，把它轉換成整數(shù)并輸出。例如：輸入字符串"123"，輸出整數(shù)123。

給定函數(shù)原型 int StrToInt(const char *str) ，實現(xiàn)字符串轉換成整數(shù)的功能，不能使用庫函數(shù)atoi。

分析和解法：

本題考查的實際上就是字符串轉換成整數(shù)的問題，或者說是要你自行實現(xiàn)atoi函數(shù)。那如何實現(xiàn)把表示整數(shù)的字符串正確地轉換成整數(shù)呢？以"123"作為例子：

• 當我們掃描到字符串的第一個字符'1'時，由于我們知道這是第一位，所以得到數(shù)字1。
• 當掃描到第二個數(shù)字'2'時，而之前我們知道前面有一個1，所以便在后面加上一個數(shù)字2，那前面的1相當于10，因此得到數(shù)字：1*10+2=12。
• 繼續(xù)掃描到字符'3'，'3'的前面已經(jīng)有了12，由于前面的12相當于120，加上后面掃描到的3，最終得到的數(shù)是：12*10+3=123。

因此，此題的基本思路便是：從左至右掃描字符串，把之前得到的數(shù)字乘以10，再加上當前字符表示的數(shù)字。

這題很簡單，但是依然有一些細節(jié)需要注意：

• 空指針輸入：輸入的是指針，在訪問空指針時程序會崩潰，因此在使用指針之前需要先判斷指針是否為空。
• 正負符號：整數(shù)不僅包含數(shù)字，還有可能是以'+'或'-'開頭表示正負整數(shù)，因此如果第一個字符是'-'號，則要把得到的整數(shù)轉換成負整數(shù)。
• 非法字符：輸入的字符串中可能含有不是數(shù)字的字符。因此，每當碰到這些非法的字符，程序應停止轉換。
• 整型溢出：輸入的數(shù)字是以字符串的形式輸入，因此輸入一個很長的字符串將可能導致溢出。

上述其它問題比較好處理，但溢出問題比較麻煩，所以咱們來重點看下溢出問題。一般說來，當發(fā)生溢出時，取最大或最小的int值。即大于正整數(shù)能表示的范圍時返回MAX_INT：2147483647；小于負整數(shù)能表示的范圍時返回MIN_INT：-2147483648。

我們先設置一些變量：

• sign用來處理數(shù)字的正負，當為正時sign > 0，當為負時sign < 0
• n存放最終轉換后的結果
• c表示當前數(shù)字

而后，你可能會編寫如下代碼段處理溢出問題：

//當發(fā)生正溢出時，返回INT_MAX
if ((sign == '+') && (c > MAX_INT - n * 10))
{
    n = MAX_INT;
    break;
}
//發(fā)生負溢出時，返回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) < n*10(1052254545*10)，所以當掃描到最后一個字符‘9’的時候，執(zhí)行上面的這行代碼：c > MAX_INT - n * 10已無意義，因為此時(MAX_INT - n * 10)已經(jīng)小于0，程序已經(jīng)出錯。

針對這種由于輸入了一個很大的數(shù)字轉換之后會超過能夠表示的最大的整數(shù)而導致的溢出情況，我們有兩種處理方式可以選擇：

• 一個取巧的方式是把轉換后返回的值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時，那么比較最后一個數(shù)字c跟MAX_INT % 10的大小，即如果n == MAX_INT / 10且c > MAX_INT % 10，則照樣返回MAX_INT。

對于上面第一種方式，雖然我們把n定義了長整型，但最后返回時系統(tǒng)會自動轉換成整型。咱們下面主要來看第二種處理方式。

對于上面第二種方式，先舉兩個例子說明下：

如果我們要轉換的字符串是"2147483697"，那么當我掃描到字符'9'時，判斷出214748369 > MAX_INT / 10 = 2147483647 / 10 = 214748364（C語言里，整數(shù)相除自動取整，不留小數(shù)），則返回MAX_INT；

如果我們要轉換的字符串是"2147483648"，那么判斷最后一個字符'8'所代表的數(shù)字8與MAX_INT % 10 = 7的大小，前者大，依然返回MAX_INT。

一直以來，我們努力的目的歸根結底是為了更好的處理溢出，但上述第二種處理方式考慮到直接計算 n * 10 + c 可能會大于MAX_INT導致溢出，那么便兩邊同時除以10，只比較 n和MAX_INT / 10的大小，從而巧妙的規(guī)避了計算n*10這一乘法步驟，轉換成計算除法MAX_INT/10代替，不能不說此法頗妙。

如此我們可以寫出正確的處理溢出的代碼：

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;
}

源代碼如下：

#include <iostream>
#include <locale>
using namespace std;

int StrToInt(const char* str)
{
    static const int MAX_INT = (int)((unsigned)~0 >> 1);
    static const int MIN_INT = -(int)((unsigned)~0 >>1) - 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;  
    }
    //確定是數(shù)字后才執(zhí)行循環(huán)
    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;
        }
        //把之前得到的數(shù)字乘10，再加上當前字符表示的數(shù)字
        n = n * 10 + c;
        ++str; 
    } 
    return sign > 0 ? n : -n;
}

int main()
{
    char str[20];
    int num;
    cin >> str;
    num = StrToInt(str);
    cout << num << endl;
    return 0;
}

分析：這個題目很簡單，但是對于一些細節(jié)的處理一定要小心，還有就是注意處理順序。

特別注意：

• 我們在處理數(shù)據(jù)時一定要考慮全面一些，針對于各種不同的錯誤給出相應的解決方案。

參考資料：《編程之法》The Art of Programming By July