## 題目描述 輸入一個由數字組成的字符串，把它轉換成整數并輸出。例如：輸入字符串"123"，輸出整數123。 給定函數原型`int StrToInt(const char *str)`?，實現字符串轉換成整數的功能，不能使用庫函數atoi。 ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/01.03.md#分析與解法)分析與解法 本題考查的實際上就是字符串轉換成整數的問題，或者說是要你自行實現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(const char *str) { int n = 0; while (*str != 0) { int c = *str - '0'; n = n * 10 + c; ++str; } return n; } ~~~ 顯然，上述代碼忽略了以下細節： 1. 空指針輸入：輸入的是指針，在訪問空指針時程序會崩潰，因此在使用指針之前需要先判斷指針是否為空。 2. 正負符號：整數不僅包含數字，還有可能是以'+'或'-'開頭表示正負整數，因此如果第一個字符是'-'號，則要把得到的整數轉換成負整數。 3. 非法字符：輸入的字符串中可能含有不是數字的字符。因此，每當碰到這些非法的字符，程序應停止轉換。 4. 整型溢出：輸入的數字是以字符串的形式輸入，因此輸入一個很長的字符串將可能導致溢出。 上述其它問題比較好處理，但溢出問題比較麻煩，所以咱們來重點看下溢出問題。 一般說來，當發生溢出時，取最大或最小的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) < n_10(1052254545\_10)，所以當掃描到最后一個字符‘9’的時候，執行上面的這行代碼： ~~~ c > MAX_INT - n * 10 ~~~ 已無意義，因為此時(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定義了長整型，但最后返回時系統會自動轉換成整型。咱們下面主要來看第二種處理方式。 對于上面第二種方式，先舉兩個例子說明下： * 如果我們要轉換的字符串是"2147483697"，那么當我掃描到字符'9'時，判斷出214748369 > MAX_INT / 10 = 2147483647 / 10 = 214748364（C語言里，整數相除自動取整，不留小數），則返回MAX_INT； * 如果我們要轉換的字符串是"2147483648"，那么判斷最后一個字符'8'所代表的數字8與MAX_INT % 10 = 7的大小，前者大，依然返回MAX_INT。 一直以來，我們努力的目的歸根結底是為了更好的處理溢出，但上述第二種處理方式考慮到直接計算n * 10 + c 可能會大于MAX_INT導致溢出，那么便兩邊同時除以10，只比較n和MAX_INT / 10的大小，從而巧妙的規避了計算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; } ~~~ 從而，字符串轉換成整數，完整的參考代碼為： ~~~ 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; } //確定是數字后才執行循環 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; } //把之前得到的數字乘以10，再加上當前字符表示的數字。 n = n * 10 + c; ++str; } return sign > 0 ? n : -n; } ~~~ ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/01.03.md#舉一反三)舉一反三 1. 實現string到double的轉換 分析：此題雖然類似于atoi函數，但畢竟double為64位，而且支持小數，因而邊界條件更加嚴格，寫代碼時需要更加注意。