字元串轉換為整數 Sring to Integer

題目：輸入一個表示整數的字元串，把該字元串轉換成整數并輸出。例如輸入字元串"345"，則輸出整數345。分析：這道題盡管不是很難，學過C/C++語言一般都能實作基本功能，但不同程式員就這道題寫出的代碼有很大差別，可以說這道題能夠很好地反應出程式員的思維和程式設計習慣，是以已經被包括微軟在内的多家公司用作面試題。建議讀者在往下看之前自己先編寫代碼，再比較自己寫的代碼和下面的參考代碼有哪些不同。

首先我們分析如何完成基本功能，即如何把表示整數的字元串正确地轉換成整數。還是以"345"作為例子。當我們掃描到字元串的第一個字元'3'時，我們不知道後面還有多少位，僅僅知道這是第一位，是以此時得到的數字是3。當掃描到第二個數字'4'時，此時我們已經知道前面已經一個3了，再在後面加上一個數字4，那前面的3相當于30，是以得到的數字是3*10+4=34。接着我們又掃描到字元'5'，我們已經知道了'5'的前面已經有了34，由于後面要加上一個5，前面的34就相當于340了，是以得到的數字就是34*10+5=345。

分析到這裡，我們不能得出一個轉換的思路：每掃描到一個字元，我們把在之前得到的數字乘以10再加上目前字元表示的數字。這個思路用循環不難實作。

由于整數可能不僅僅之含有數字，還有可能以'+'或者'-'開頭，表示整數的正負。是以我們需要把這個字元串的第一個字元做特殊處理。如果第一個字元是'+'号，則不需要做任何操作；如果第一個字元是'-'号，則表明這個整數是個負數，在最後的時候我們要把得到的數值變成負數。

接着我們試着處理非法輸入。由于輸入的是指針，在使用指針之前，我們要做的第一件是判斷這個指針是不是為空。如果試着去通路空指針，将不可避免地導緻程式崩潰。另外，輸入的字元串中可能含有不是數字的字元。每當碰到這些非法的字元，我們就沒有必要再繼續轉換。最後一個需要考慮的問題是溢出問題。由于輸入的數字是以字元串的形式輸入，是以有可能輸入一個很大的數字轉換之後會超過能夠表示的最大的整數而溢出。

現在已經分析的差不多了，開始考慮編寫代碼。首先我們考慮如何聲明這個函數。由于是把字元串轉換成整數，很自然我們想到：

int StrToInt(const char* str);

這樣聲明看起來沒有問題。但當輸入的字元串是一個空指針或者含有非法的字元時，應該傳回什麼值呢？0怎麼樣？那怎麼區分非法輸入和字元串本身就是”0”這兩種情況呢？

接下來我們考慮另外一種思路。我們可以傳回一個布爾值來訓示輸入是否有效，而把轉換後的整數放到參數清單中以引用或者指針的形式傳入。于是我們就可以聲明如下：

bool StrToInt(const char *str, int& num);

這種思路解決了前面的問題。但是這個函數的使用者使用這個函數的時候會覺得不是很友善，因為他不能直接把得到的整數指派給其他整形變臉，顯得不夠直覺。

前面的第一種聲明就很直覺。如何在保證直覺的前提下當碰到非法輸入的時候通知使用者呢？一種解決方案就是定義一個全局變量，每當碰到非法輸入的時候，就标記該全局變量。使用者在調用這個函數之後，就可以檢驗該全局變量來判斷轉換是不是成功。

下面我們寫出完整的實作代碼。參考代碼：

enum Status {kValid = 0, kInvalid};

int g_nStatus = kValid;

///

// Convert a string into an integer

///

int StrToInt(const char* str)

{

       g_nStatus = kInvalid;

      long long num = 0;

      if(str != NULL)

       {

            const char* digit = str;

            // the first char in the string maybe '+' or '-'

            bool minus = false;

            if(*digit == '+')

                   digit ++;

            else if(*digit == '-')

             {

                   digit ++;

                   minus = true;

             }

            // the remaining chars in the string

            while(*digit != '\0')

             {

                  if(*digit >= '0' && *digit <= '9')

                   {

                         num = num * 10 + (*digit - '0');

                        // overflow 

                        if(num > std::numeric_limits<int>::max())

                         {

                               num = 0;

                               break;

                         }

                         digit ++;

                   }

                  // if the char is not a digit, invalid input

                  else

                   {

                         num = 0;

                        break;

                   }

             }

            if(*digit == '\0')

             {

                   g_nStatus = kValid;

                  if(minus)

                         num = 0 - num;

             }

       }

       return static_cast<int>(num);

}

讨論：在參考代碼中，我選用的是第一種聲明方式。不過在面試時，我們可以選用任意一種聲明方式進行實作。但當面試官問我們選擇的理由時，我們要對兩者的優缺點進行評價。第一種聲明方式對使用者而言非常直覺，但使用了全局變量，不夠優雅；而第二種思路是用傳回值來表明輸入是否合法，在很多API中都用這種方法，但該方法聲明的函數使用起來不夠直覺。

最後值得一提的是，在C語言提供的庫函數中，函數atoi能夠把字元串轉換整數。它的聲明是int atoi(const char *str)。該函數就是用一個全局變量來标志輸入是否合法的。

Java Solution

public int atoi(String str) { if (str == null || str.length() < 1) return 0;   // trim white spaces str = str.trim();   char flag = '+';   // check negative or positive int i = 0; if (str.charAt(0) == '-') { flag = '-'; i++; } else if (str.charAt(0) == '+') { i++; } // use double to store result double result = 0;   // calculate value while (str.length() > i && str.charAt(i) >= '0' && str.charAt(i) <= '9') { result = result * 10 + (str.charAt(i) - '0'); i++; }   if (flag == '-') result = -result;   // handle max and min if (result > Integer.MAX_VALUE) return Integer.MAX_VALUE;   if (result < Integer.MIN_VALUE) return Integer.MIN_VALUE;   return (int) result; }