算法练习之一

今天瞎逛论坛，看到一个很不错的题目，拿来练练手，记录一下，以便日后回看。

先看题目：

输入一个表示整数的字符串，把该字符串转换成整数并输出，例如输入字符串"345"，则输出整数 345。
给定函数原型 int StrToInt(const char *str) ，完成函数 StrToInt，实现字符串转换成整数的功能，不得用库函数 atoi（即便准许使用，其对于溢出情况的处理也达不到题目的要求.)

输入：　　　　　　　输出：

123　　　　　　　　123

-123　　　　　　　　-123

23a4　　　　　　　　23

2147483648　　　　2147483647

-2147483649　　　-2147483648

10522545459　　　2147483647

题目分析：

初看这套题貌似很简单，但是真正开始动手敲键盘的时候才发现里面有太多的陷阱。

陷阱一：是否考虑到了正负号的问，即代码能正确处理123与-123

陷阱二：是否考虑到字符串中有非法字符，例如23a4，该如何处理。我们目前假设输出23是正确的

陷阱三：如果输入的字符串超出了int型整数所能表示的最大范围怎么办？例如输入10522545459，我们知道int型最大范围为-2147483648~2147483647。我们假设一旦溢出时，输出最大　　　　或最小数。在写代码过程中，溢出问题是最大的障碍。

陷阱四：字符串是空怎么办？默认字符串为空是输出0.

OK，将以上陷阱考虑清楚以后开始写代码了

  1 #include <iostream>
  2 #include <string.h>
  3 #include <limits>
  4 #include <limits.h>
  5 using namespace std;
  6 
  7 const int MAXSIZE=1000;
  8 enum Status{ kValid = 0, kInvalid};
  9 int g_nStatus = kValid;
 10 
 11 /*版本一
 12 此版本基本实现了将字符串型整数转换为int整数，但是对于一些非法的输入依旧是不行的
 13 例如：23a4，它只会返回0，而不是23；还有一旦越界后，它也是输出的0
 14 */
 15 int StrToInt( const char* str )
 16 {
 17     g_nStatus = kInvalid;
 18     long long num=0;
 19 
 20     if( str != NULL )
 21     {
 22         const char* digit = str;
 23         bool minus = false;
 24 
 25         if( *digit == '+' )
 26         {
 27             digit++;
 28         }
 29         else if( *digit == '-' )
 30         {
 31             digit++;
 32             minus=true;
 33         }
 34 
 35         while( *digit != '' )
 36         {
 37             if( *digit >='0' && *digit <='9' )
 38             {
 39                 num = num*10 + ( *digit - '0' );
 40 
 41                 if( num > numeric_limits<int>::max() )
 42                 {
 43                     num=0;
 44                     break;
 45                 }
 46                 digit++;
 47             }
 48             else
 49             {
 50                 num=0;
 51                 break;
 52             }
 53         }
 54         if( *digit == '' )
 55         {
 56             g_nStatus = kValid;
 57             if( minus )
 58             {
 59                 num=0-num;
 60             }
 61         }
 62     }
 63 
 64     return static_cast<int>(num);
 65 }
 66 
 67 /*版本二：
 68 此版本较上面的有了更好的改进，首先对于溢出问题有了很好的处理，INT_MAX是标准库里定义的int型最大值INT_MIN是最小值
 69 其次，在遇到非法字符时，循环跳出，但之前记录的数依旧会返回，也就是实现了23a4返回23的功能。
 70 小贴士：INT_MAX=2147483647   INT_MIN=-2147483648 (需要头文件limits.h) 这也是( cur-1 > INT_MAX - res*10 )这样写的原因
 71 
 72 但是，（显然这个版本还是有错），如果输入10522545459他会输出1932610867，
 73 原因是如果之前所得数已经较大了，再乘10就必定溢出，也就是超出int所能表示最大范围，会发生逻辑错误。
 74 */
 75 int StrToInt_2( const char* str )
 76 {
 77     int res=0;
 78     int i=0;
 79     int signal = '+';
 80     int cur;
 81 
 82     if( !str )
 83     {
 84         return 0;
 85     }
 86 
 87     while( isspace(str[i]))
 88     {
 89         i++;
 90     }
 91 
 92     if( str[i] == '+' || str[i] == '-')
 93     {
 94         signal = str[i];
 95         i++;
 96     }
 97 
 98     while( str[i] >= '0' && str[i] <= '9' )
 99     {
100         cur=str[i]-'0';
101         if( (signal == '+' ) && ( cur > INT_MAX - res*10 ) )
102         {
103             res=INT_MAX;   
104             break;
105         }
106         else if( (signal == '-' ) && ( cur-1 > INT_MAX - res*10 ) )
107         {
108             res=INT_MIN;   
109             break;
110         }
111 
112         res=res*10+cur;
113         i++;
114     }
115 
116     return signal=='-'?-res:res;
117 }
118 
119 /*版本三：
120 此版本我没有想出来，而是参考july的博文写出的。
121 它的做法最重要的是巧妙的规避了计算 n*10 这一乘法步骤，转换成计算除法 MAX_INT/10 代替，不能不说此法颇妙。
122 这样的话在超出int型最大范围前就能提早发现它将要溢出。关键代码在***处
123 目前这个版本的代码是最为接近正确答案的了，不过也许会有更好的代码，待日后发现再说吧！
124 
125 这个版本所存在的问题就显得无足轻重了：它的实现与 linux 内核的 atoi 函数的实现, 都有一个共同的问题: 
126 即使出错, 函数也返回了一个值, 导致调用者误认为自己传入的参数是正确的, 但是可能会导致程序的其他部分产生莫名的错误且很难调试”。
127 */
128 int StrToInt_3( const char* str )
129 {
130     const int MAX_DIV=INT_MAX/10;
131     const int MIN_DIV=INT_MIN/10;
132     const int MAX_R=INT_MAX%10;
133     const int MIN_R=INT_MIN%10;
134     //另一种实现，可以不需要limit.h的头文件，便于移植
135     /*
136     const int MAX = (int)((unsigned)~0 >> 1);
137     const int MIN = -(int)((unsigned)~0 >> 1) - 1;
138     const int MAX_DIV = (int)((unsigned)~0 >> 1) / 10;
139     const int MIN_DIV = (int)((((unsigned)~0 >> 1) + 1) / 10);
140     const int MAX_R = (int)((unsigned)~0 >> 1) % 10;
141     const int MIN_R = (int)((((unsigned)~0 >> 1) + 1) % 10);
142     */
143 
144     int res=0;
145     int i=0;
146     int signal = '+';
147     int cur;
148 
149     if( !str )
150     {
151         return 0;
152     }
153 
154     while( isspace(str[i]))
155     {
156         i++;
157     }
158 
159     if( str[i] == '+' || str[i] == '-')
160     {
161         signal = str[i];
162         i++;
163     }
164 
165     while( str[i] >= '0' && str[i] <= '9' )
166     {
167         cur=str[i]-'0';
168         if( (signal == '+' ) && ( res > MAX_DIV || (res == MAX_DIV && cur >= MAX_R)) )  //***
169         {
170             res=INT_MAX;   /*或res=MAX*/
171             break;
172         }
173         else if( (signal == '-' ) && ( res > MIN_DIV || (res == MIN_DIV && cur >= MIN_R)) ) //***
174         {
175             res=INT_MIN;   /*或res=MIN*/
176             break;
177         }
178 
179         res=res*10+cur;
180         i++;
181     }
182 
183     return signal=='-'?-res:res;
184 }
185 
186 
187 int main( void )
188 {
189     char str[MAXSIZE];
190     memset( str, 0, MAXSIZE);
191     while( cin.getline( str, MAXSIZE ))
192     {
193         cout<<str<<"          "<<StrToInt_2(str)<<endl;
194     }
195 
196     return 0;
197 }

写完这道题以后，也给我自己提个醒：

1.拿到一道题时候要充分考虑输入的各种情况，能够对所有非法输入有一个正确处理，这就是所谓的程序的鲁棒性（健壮性）

2.所有题目题目的解法都离不开基础，程序中用的都是基础的数据结构。int+array=all

3.善于分析题目中隐含的小知识，细节决定成败。这也是我目前所或缺的。