现在的位置: 首页 > 综合 > 正文

程序员编程艺术第三十~三十一章：字符串转换成整数，通配符字符串匹配 程序员编程艺术第三十~三十一章：字符串转换成整数，通配符字符串匹配

2017年11月03日 ⁄ 综合 ⁄ 共 29210字 ⁄ 字号 小 中 大 ⁄ 评论关闭

程序员编程艺术第三十~三十一章：字符串转换成整数，通配符字符串匹配

分类： 12.TAOPP string 11.TAOPP（编程艺术）2013-06-04
17:52 19484人阅读 评论(98) 收藏 举报

目录(?)[+]

第三十~三十一章：字符串转换成整数，带通配符的字符串匹配

前言

    之前本一直想写写神经网络算法和EM算法，但写这两个算法实在需要大段大段的时间，而平时上班，周末则跑去北大教室自习看书（顺便以时间为序，说下过去半年看过的自觉还不错的数学史方面的书：《数理统计学简史》《微积分概念发展史》《微积分的历程：从牛顿到勒贝格》《数学恩仇录》《数学与知识的探求》《古今数学思想》《素数之恋》），故一直未曾有时间写。

     然最近在负责一款在线编程挑战平台：http://hero.pongo.cn/（简称hero，通俗理解是中国的topcoder，当然，一直在不断完善中，与一般OJ不同点在于，OJ侧重为参与ACM竞赛者提供刷题练习的场所，而hero则着重为企业招聘面试服务），在上面出了几道编程面试题，有些题目看似简单，但一coding，很多问题便立马都在hero上给暴露出来了，故就从hero上的编程挑战题切入，继续更新本程序员编程艺术系列吧。

    况且，前几天与一朋友聊天，他说他认识的今年360招进来的三四十人应届生包括他自己找工作时基本都看过我的博客，则更增加了更新此编程艺术系列的动力。

    OK，本文讲两个问题：

  • 第三十章、字符串转换成整数，从确定思路，到写出有瑕疵的代码，继而到microsoft & linux的atoi实现，再到第一份比较完整的代码，最后以Net/OS中的实现结尾，看似很简单的一个问题，其实非常不简单；
  • 第三十一章、字符串匹配问题
    还是这句老话，有问题恳请随时批评指正，感谢。

第三十章、字符串转换成整数

    先看题目：

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

    我们来一步一步分析（共9小节，重点在下文第8小节及后续内容），直至写出第一份准确的代码：

1、本题考查的实际上就是字符串转换成整数的问题，或者说是要你自行实现atoi函数。那如何实现把表示整数的字符串正确地转换成整数呢？以"345"作为例子：

  1. 当我们扫描到字符串的第一个字符'3'时，由于我们知道这是第一位，所以得到数字3。
  2. 当扫描到第二个数字'4'时，而之前我们知道前面有一个3，所以便在后面加上一个数字4，那前面的3相当于30，因此得到数字：3*10+4=34。
  3. 继续扫描到字符'5'，'5'的前面已经有了34，由于前面的34相当于340，加上后面扫描到的5，最终得到的数是：34*10+5=345。

    因此，此题的思路便是：每扫描到一个字符，我们便把在之前得到的数字乘以10，然后再加上当前字符表示的数字。

    2、思路有了，有一些细节需要注意，如zhedahht所说：

  1. “由于整数可能不仅仅之含有数字，还有可能以'+'或者'-'开头，表示整数的正负。因此我们需要把这个字符串的第一个字符做特殊处理。如果第一个字符是'+'号，则不需要做任何操作；如果第一个字符是'-'号，则表明这个整数是个负数，在最后的时候我们要把得到的数值变成负数。
  2. 接着我们试着处理非法输入。由于输入的是指针，在使用指针之前，我们要做的第一件是判断这个指针是不是为空。如果试着去访问空指针，将不可避免地导致程序崩溃。
  3. 另外，输入的字符串中可能含有不是数字的字符。每当碰到这些非法的字符，我们就没有必要再继续转换。
  4. 最后一个需要考虑的问题是溢出问题。由于输入的数字是以字符串的形式输入，因此有可能输入一个很大的数字转换之后会超过能够表示的最大的整数而溢出。”
    比如，当给的字符串是如左边图片所示的时候，有考虑到么？当然，它们各自对应的正确输出如右边图片所示（假定你是在32位系统下，且编译环境是VS2008以上）：


    3、很快，可能你就会写下如下代码：
  1. //copyright@zhedahht 2007    
  2. enum Status {kValid = 0, kInvalid};  
  3. int g_nStatus = kValid;  
  4.   
  5. // Convert a string into an integer  
  6. int StrToInt(const char* str)  
  7. {  
  8.     g_nStatus = kInvalid;  
  9.     long long num = 0;  
  10.   
  11.     if(str != NULL)  
  12.     {  
  13.         const char* digit = str;  
  14.   
  15.         // the first char in the string maybe '+' or '-'  
  16.         bool minus = false;  
  17.         if(*digit == '+')  
  18.             digit ++;  
  19.         else if(*digit == '-')  
  20.         {  
  21.             digit ++;  
  22.             minus = true;  
  23.         }  
  24.   
  25.         // the remaining chars in the string  
  26.         while(*digit != '\0')  
  27.         {  
  28.             if(*digit >= '0' && *digit <= '9')  
  29.             {  
  30.                 num = num * 10 + (*digit - '0');  
  31.   
  32.                 // overflow    
  33.                 if(num > std::numeric_limits<int>::max())  
  34.                 {  
  35.                     num = 0;  
  36.                     break;  
  37.                 }  
  38.   
  39.                 digit ++;  
  40.             }  
  41.             // if the char is not a digit, invalid input  
  42.             else  
  43.             {  
  44.                 num = 0;  
  45.                 break;  
  46.             }  
  47.         }  
  48.   
  49.         if(*digit == '\0')  
  50.         {  
  51.             g_nStatus = kValid;  
  52.             if(minus)  
  53.                 num = 0 - num;  
  54.         }  
  55.     }  
  56.     return static_cast<int>(num);  
  57. }  
    run下上述程序，会发现当输入字符串是下图中红叉叉部分所对应的时候，程序结果出错：  

    

    两个问题：

  1. 当输入的字符串不是数字，而是字符的时候，比如“1a”，上述程序直接返回了0（而正确的结果应该是得到1）：

    1. // if the char is not a digit, invalid input  
    2.                   else  
    3.                   {  
    4.                       num = 0;  
    5.                       break;  
    6.                   }  
  2. 处理溢出时，有问题。因为它遇到溢出情况时，直接返回了0：
    1. // overflow    
    2.                 if(num > std::numeric_limits<int>::max())  
    3.                 {  
    4.                     num = 0;  
    5.                     break;  
    6.                 }  
    4、把代码做下微调，如下（注：库函数atoi规定超过int值，按最大值maxint：2147483647来，超过-int按最小值minint：-2147483648来）：
  1. //copyright@SP_daiyq 2013/5/29  
  2. int StrToInt(const char* str)  
  3. {  
  4.     int res = 0; // result  
  5.     int i = 0; // index of str  
  6.     int signal = '+'; // signal '+' or '-'  
  7.     int cur; // current digit  
  8.   
  9.     if (!str)  
  10.         return 0;  
  11.   
  12.     // skip backspace  
  13.     while (isspace(str[i]))  
  14.         i++;  
  15.   
  16.     // skip signal  
  17.     if (str[i] == '+' || str[i] == '-')  
  18.     {  
  19.         signal = str[i];  
  20.         i++;  
  21.     }  
  22.   
  23.     // get result  
  24.     while (str[i] >= '0' && str[i] <= '9')  
  25.     {  
  26.         cur = str[i] - '0';  
  27.   
  28.         // judge overlap or not  
  29.         if ( (signal == '+') && (cur > INT_MAX - res*10) )  
  30.         {  
  31.             res = INT_MAX;  
  32.             break;  
  33.         }  
  34.         else if ( (signal == '-') && (cur -1 > INT_MAX - res*10) )  
  35.         {  
  36.             res = INT_MIN;  
  37.             break;  
  38.         }  
  39.   
  40.         res = res * 10 + cur;  
  41.         i++;  
  42.     }  
  43.   
  44.     return (signal == '-') ? -res : res;  
  45. }  
    此时会发现，上面第3小节末所述的第1个小问题（当输入的字符串不是数字，而是字符的时候）解决了：

    

    但， 上文第3小节末所述的第2个小问题：溢出问题却没有解决。即当给定下述测试数据的时候，问题就来了：
需要转换的字符串                        
  代码运行结果    理应得到的正确结果

    

    什么问题呢？比如说用上述代码转换这个字符串："    10522545459"，它本应得到的正确结果应该是2147483647，但程序实际得到的结果却是：1932610867。故很明显，程序没有解决好上面的第2个小问题：溢出问题。原因是什么呢？咱们来分析下代码，看是如何具体处理溢出情况的：
  1. // judge overlap or not  
  2.         if ( (signal == '+') && (cur > INT_MAX - res*10) )  
  3.         {  
  4.             res = INT_MAX;  
  5.             break;  
  6.         }  
  7.         else if ( (signal == '-') && (cur -1 > INT_MAX - res*10) )  
  8.         {  
  9.             res = INT_MIN;  
  10.             break;  
  11.         }  

    接着上面的例子来，比如给定字符串"    10522545459"，除去空格有11位，而MAX_INT，即2147483647是10位数，当扫描到最后一个字符‘9’的时候，程序会比较 9 和 2147483647 - 1052254545*10的大小。

     问题立马就暴露出来了，因为此时让res*10，即让1052254545*10 > MAX_INT，溢出无疑，程序已经出错，再执行下面这行代码已无意义：
  1. cur > INT_MAX - res*10  

    也就是说，对于字符串"10522545459", 当扫描到最后一个字符‘9’时，根据上文第1小节的字符串转换成整数的思路：“每扫描到一个字符，我们便把在之前得到的数字乘以10，然后再加上当前字符表示的数字”，为了得到最终的整数，我们得如此计算：

1052254545*10 + 4，

    然实际上当程序计算到1052254545*10时，

1052254545*10 >

2147483647

    此时已经溢出了,若再执意计算，则程序逻辑将出错，故此后也就不能再判断字串的最后一位4是否大于2147483647%10了（耐不得烦想尽快看到最终正确代码的读者可以直接跳到下文第8节）。

  

    5、上面说给的程序没有“很好的解决溢出问题。由于输入的数字是以字符串的形式输入，因此有可能输入一个很大的数字转换之后会超过能够表示的最大的整数而溢出”。那么，到底代码该如何写呢？
    像下面这样？：
  1. //copyright@fuwutu 2013/5/29  
  2. int StrToInt(const char* str)  
  3. {  
  4.     bool negative = false;  
  5.     long long result = 0;  
  6.     while (*str == ' ' || *str == '\t')  
  7.     {  
  8.         ++str;  
  9.     }  
  10.     if (*str == '-')  
  11.     {  
  12.         negative = true;  
  13.         ++str;  
  14.     }  
  15.     else if (*str == '+')  
  16.     {  
  17.         ++str;  
  18.     }  
  19.   
  20.     while (*str != '\0')  
  21.     {  
  22.         int n = *str - '0';  
  23.         if (n < 0 || n > 9)  
  24.         {  
  25.             break;  
  26.         }  
  27.   
  28.         if (negative)  
  29.         {  
  30.             result = result * 10 - n;  
  31.             if (result < -2147483648LL)  
  32.             {  
  33.                 result = -2147483648LL;  
  34.             }  
  35.         }  
  36.         else  
  37.         {  
  38.             result = result * 10 + n;  
  39.             if (result > 2147483647LL)  
  40.             {  
  41.                 result = 2147483647LL;  
  42.             }  
  43.         }  
  44.         ++str;  
  45.     }  
  46.   
  47.   return result;  
  48. }  
    run下程序，看看运行结果：

    

     上图所示程序貌似通过了，然实际上它还是未能处理数据溢出的问题，因为它只是做了个取巧，即把返回的值esult定义成了long long，如下所示：
  1. long long result = 0;  
    故严格说来，我们依然未写出准确的规范代码。
    6、那到底该如何解决这个数据溢出的问题呢？咱们先来看看Microsoft是如何实现atoi的吧：
  1. //atol函数  
  2. //Copyright (c) 1989-1997, Microsoft Corporation. All rights reserved.  
  3. long __cdecl atol(  
  4.     const char *nptr  
  5.     )  
  6. {  
  7.     int c; /* current char */  
  8.     long total; /* current total */  
  9.     int sign; /* if ''-'', then negative, otherwise positive */  
  10.   
  11.     /* skip whitespace */  
  12.     while ( isspace((int)(unsigned char)*nptr) )  
  13.         ++nptr;  
  14.   
  15.     c = (int)(unsigned char)*nptr++;  
  16.     sign = c; /* save sign indication */  
  17.     if (c == ''-'' || c == ''+'')  
  18.         c = (int)(unsigned char)*nptr++; /* skip sign */  
  19.   
  20.     total = 0;  
  21.   
  22.     while (isdigit(c)) {  
  23.         total = 10 * total + (c - ''0''); /* accumulate digit */  
  24.         c = (int)(unsigned char)*nptr++; /* get next char */  
  25.     }  
  26.   
  27.     if (sign == ''-'')  
  28.         return -total;  
  29.     else  
  30.         return total; /* return result, negated if necessary */  
  31. }  
    其中，isspace和isdigit函数的实现代码为：
  1. isspace(int x)    
  2. {    
  3.     if(x==' '||x=='/t'||x=='/n'||x=='/f'||x=='/b'||x=='/r')    
  4.         return 1;    
  5.     else     
  6.         return 0;    
  7. }    
  8.   
  9. isdigit(int x)    
  10. {    
  11.     if(x<='9'&&x>='0')             
  12.         return 1;     
  13.     else     
  14.         return 0;    
  15. }   
    然后atoi调用上面的atol函数，如下所示：
  1. //atoi调用上述的atol  
  2. int __cdecl atoi(  
  3.     const char *nptr  
  4.     )  
  5. {  
  6.     //Overflow is not detected. Because of this, we can just use  
  7.     return (int)atol(nptr);  
  8. }  

    但很遗憾的是，上述atoi标准代码依然返回的是long：

  1. long total; /* current total */  
  2. if (sign == ''-'')  
  3.     return -total;  
  4. else  
  5.     return total; /* return result, negated if necessary */  

    再者，下面这里定义成long的total与10相乘，即total*10很容易溢出：

  1. long total; /* current total */  
  2. total = 10 * total + (c - ''0''); /* accumulate digit */  
   最后，根据本文评论下的读者meiyuli反应：“测试数据是字符串"-21474836480"，api算出来的是-2147483648，用上述代码算出来的结果是0”，如此，上述微软的这个atoi源码是有问题的。
     7、microsoft既然不行，读者想必很自然的想到linux。So，咱们接下来便看看linux内核中是如何实现此字符串转换为整数的问题的。linux内核中提供了以下几个函数：
  1. simple_strtol，把一个字符串转换为一个有符号长整数；
  2. simple_strtoll，把一个字符串转换为一个有符号长长整数；
  3. simple_strtoul，把一个字符串转换为一个无符号长整数；
  4. simple_strtoull，把一个字符串转换为一个无符号长长整数
    相关源码及分析如下。
    首先，atoi调下面的strtol：
  1. //linux/lib/vsprintf.c  
  2. //Copyright (C) 1991, 1992  Linus Torvalds  
  3. //simple_strtol - convert a string to a signed long  
  4. long simple_strtol(const char *cp, char **endp, unsigned int base)  
  5. {  
  6.     if (*cp == '-')  
  7.         return -simple_strtoul(cp + 1, endp, base);  
  8.   
  9.     return simple_strtoul(cp, endp, base);  
  10. }  
  11. EXPORT_SYMBOL(simple_strtol);  

    然后，上面的strtol调下面的strtoul：

  1. //simple_strtoul - convert a string to an unsigned long  
  2. unsigned long simple_strtoul(const char *cp, char **endp, unsigned int base)  
  3. {  
  4.     return simple_strtoull(cp, endp, base);  
  5. }  
  6. EXPORT_SYMBOL(simple_strtoul);  

    接着，上面的strtoul调下面的strtoull：

  1. //simple_strtoll - convert a string to a signed long long  
  2. long long simple_strtoll(const char *cp, char **endp, unsigned int base)  
  3. {  
  4.     if (*cp == '-')  
  5.         return -simple_strtoull(cp + 1, endp, base);  
  6.   
  7.     return simple_strtoull(cp, endp, base);  
  8. }  
  9. EXPORT_SYMBOL(simple_strtoll);  

    最后，strtoull调_parse_integer_fixup_radix和_parse_integer来处理相关逻辑：

  1. //simple_strtoull - convert a string to an unsigned long long  
  2. unsigned long long simple_strtoull(const char *cp, char **endp, unsigned int base)  
  3. {  
  4.     unsigned long long result;  
  5.     unsigned int rv;  
  6.   
  7.     cp = _parse_integer_fixup_radix(cp, &base);  
  8.     rv = _parse_integer(cp, base, &result);  
  9.     /* FIXME */  
  10.     cp += (rv & ~KSTRTOX_OVERFLOW);  
  11.   
  12.     if (endp)  
  13.         *endp = (char *)cp;  
  14.   
  15.     return result;  
  16. }  
  17. EXPORT_SYMBOL(simple_strtoull);  

    重头戏来了。接下来，我们来看上面strtoull函数中的parse_integer_fixup_radix和_parse_integer两段代码。如鲨鱼所说

  • “真正的处理逻辑主要是在_parse_integer里面，关于溢出的处理，_parse_integer处理的很优美，
  • 而_parse_integer_fixup_radix是用来自动根据字符串判断进制的”。
    先来看_parse_integer函数：

  1. //lib/kstrtox.c, line 39    
  2. //Convert non-negative integer string representation in explicitly given radix to an integer.    
  3. //Return number of characters consumed maybe or-ed with overflow bit.    
  4. //If overflow occurs, result integer (incorrect) is still returned.    
  5. unsigned int _parse_integer(const char *s, unsigned int base, unsigned long long *p)    
  6. {    
  7.     unsigned long long res;    
  8.     unsigned int rv;    
  9.     int overflow;    
  10.     
  11.     res = 0;    
  12.     rv = 0;    
  13.     overflow = 0;    
  14.     while (*s) {    
  15.         unsigned int val;    
  16.     
  17.         if ('0' <= *s && *s <= '9')    
  18.             val = *s - '0';    
  19.         else if ('a' <= _tolower(*s) && _tolower(*s) <= 'f')    
  20.             val = _tolower(*s) - 'a' + 10;    
  21.         else    
  22.             break;    
  23.     
  24.         if (val >= base)    
  25.             break;    
  26.         /*  
  27.          * Check for overflow only if we are within range of  
  28.          * it in the max base we support (16)  
  29.          */    
  30.         if (unlikely(res & (~0ull << 60))) {    
  31.             if (res > div_u64(ULLONG_MAX - val, base))    
  32.                 overflow = 1;    
  33.         }    
  34.         res = res * base + val;    
  35.         rv++;    
  36.         s++;    
  37.     }    
  38.     *p = res;    
  39.     if (overflow)    
  40.         rv |= KSTRTOX_OVERFLOW;    
  41.     return rv;    
  42. }  
    解释下两个小细节：
  1. 上头出现了个unlikely，其实unlikely和likely经常出现在linux相关内核源码中

    1. if(likely(value)){  
    2.     //等价于if(likely(value)) == if(value)  
    3. }  
    4. else{  
    5. }  

    likely表示value为真的可能性更大，而unlikely表示value为假的可能性更大，这两个宏被定义成：

    1. //include/linux/compiler.h  
    2. # ifndef likely  
    3. #  define likely(x) (__builtin_constant_p(x) ? !!(x) : __branch_check__(x, 1))  
    4. # endif  
    5. # ifndef unlikely  
    6. #  define unlikely(x)   (__builtin_constant_p(x) ? !!(x) : __branch_check__(x, 0))  
    7. # endif  
  2. 呈现下div_u64的代码：
    1. //include/linux/math64.h  
    2. //div_u64  
    3. static inline u64 div_u64(u64 dividend, u32 divisor)  
    4. {  
    5.     u32 remainder;  
    6.     return div_u64_rem(dividend, divisor, &remainder);  
    7. }  
    8.   
    9. //div_u64_rem  
    10. static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)  
    11. {  
    12.     *remainder = dividend % divisor;  
    13.     return dividend / divisor;  
    14. }  
    最后看下_parse_integer_fixup_radix函数：
  1. //lib/kstrtox.c, line 23  
  2. const char *_parse_integer_fixup_radix(const char *s, unsigned int *base)  
  3. {  
  4.     if (*base == 0) {  
  5.         if (s[0] == '0') {  
  6.             if (_tolower(s[1]) == 'x' && isxdigit(s[2]))  
  7.                 *base = 16;  
  8.             else  
  9.                 *base = 8;  
  10.         } else  
  11.             *base = 10;  
  12.     }  
  13.     if (*base == 16 && s[0] == '0' && _tolower(s[1]) == 'x')  
  14.         s += 2;  
  15.     return s;  
  16. }  
    读者MJN君在我的建议下，对上述linux内核中的atoi函数进行了测试，咱们来看下测试结果如何。
2147483647 : 2147483647
2147483648 : -2147483648
10522545459 : 1932610867
-2147483648 : -2147483648
-2147483649 : -2147483647
-10522545459 : 1932610867
    如上，根据程序的输出结果可以看出，对于某些溢出的情况，atoi程序的处理并不符合本题的要求。
 也就是说，atoi程序对溢出的处理是一个标准，而本题要求对溢出的处理则是另外一个标准，所以说直接用atoi程序达不到本题的要求，但你不能因为本题的标准而否认atoi程序的正确性。
  既然直接借用atoi的源码（原理是parseXXX，int i=Integer.parseInt(String str)，把str转换成int的方法），不符合题目要求，则咱们另寻他路。
  路漫漫其修远兮，吾等将上下而求索，但与此同时，我们已渐入佳境。
  

   8、根据我们第1小节达成一致的字符串转换成整数的思路：“每扫描到一个字符，我们便把在之前得到的数字乘以10，然后再加上当前字符表示的数字”，相信读者已经觉察到，在扫描到最后一个字符的时候，如果之前得到的数比较大，此时若再让其扩大10倍，相对来说是比较容易溢出的。

    但车到山前必有路，既然让一个比较大的int整型数括大10倍，比较容易溢出， 那么在不好判断是否溢出的情况下，可以尝试使用除法。即如MJN所说：
  1. 与其将n扩大10倍,，冒着溢出的风险, 再与MAX_INT进行比较（如果已经溢出, 则比较的结果没有意义），
  2. 不如未雨绸缪先用n与MAX_INT/10进行比较： 若n>MAX_INT/10（当然同时还要考虑n=MAX_INT/10的情况）， 说明最终得到的整数一定会溢出， 故此时可以当即进行溢出处理，直接返回最大值MAX_INT，从而也就免去了计算n*10这一步骤。
    也就是说，计算n*10前,先比较n与MAX_INT/10大小，若n>MAX_INT/10，那么n*10肯定大于MAX_INT，即代表最后得到的整数n肯定溢出，既然溢出，不能再计算n*10，直接提前返回MAX_INT就行了。
    一直以来，我们努力的目的归根结底是为了更好的处理溢出，但上述做法最重要的是巧妙的规避了计算n*10这一乘法步骤，转换成计算除法MAX_INT/10代替，不能不说此法颇妙。

   他的代码如下，如有问题请指出：

  1. //copyright@njnu_mjn 2013  
  2. int StrToDecInt(const char* str)      
  3. {      
  4.     static const int MAX = (int)((unsigned)~0 >> 1);      
  5.     static const int MIN = -(int)((unsigned)~0 >> 1) - 1;      
  6.     unsigned int n = 0;      
  7.     int sign = 1;      
  8.     int c;      
  9.       
  10.     while (isspace(*str))      
  11.         ++str;      
  12.     if (*str == '+' || *str == '-')      
  13.     {      
  14.         if (*str == '-')      
  15.             sign = -1;      
  16.         ++str;      
  17.     }      
  18.     while (isdigit(*str))      
  19.     {      
  20.         c = *str - '0';      
  21.         if (sign > 0 && (n > MAX/10 || (n == MAX/10 && c > MAX%10)))      
  22.         {      
  23.             n = MAX;      
  24.             break;      
  25.         }      
  26.         else if (sign < 0 && (n > (unsigned)MIN/10       
  27.                               || (n == (unsigned)MIN/10 && c > (unsigned)MIN%10)))      
  28.         {      
  29.             n = MIN;      
  30.             break;      
  31.         }      
  32.         n = n * 10 + c;      
  33.         ++str;      
  34.     }      
  35.     return sign > 0 ? n : -n;      
  36. }    

    上述代码从测试结果来看，暂未发现什么问题

输入 
输出
10522545459 :     2147483647
-10522545459 :   -2147483648

    咱们再来总结下上述代码是如何处理溢出情况的。对于正数来说，它溢出的可能性有两种：

  1. 一种是诸如2147483650，即n > MAX/10 的；
  2. 一种是诸如2147483649，即n == MAX/10 && c > MAX%10。

   故咱们上面处理溢出情况的代码便是：

  1. c = *str - '0';    
  2.         if (sign > 0 && (n > MAX/10 || (n == MAX/10 && c > MAX%10)))    
  3.         {    
  4.             n = MAX;    
  5.             break;    
  6.         }    
  7.         else if (sign < 0 && (n > (unsigned)MIN/10     
  8.                               || (n == (unsigned)MIN/10 && c > (unsigned)MIN%10)))    
  9.         {    
  10.             n = MIN;    
  11.             break;    
  12.         }    

    不过，即便如此，有些细节是改进的，如他自己所说：

  1. n的声明及定义应该为
    1. int n = 0;    
  2. 将MAX/10,MAX%10,(unsigned)MIN/10及(unsigned)MIN%10保存到变量中, 防止重复计算

    这样，优化后的代码为：

  1. //copyright@njnu_mjn 2013  
  2. int StrToDecInt(const char* str)    
  3. {    
  4.     static const int MAX = (int)((unsigned)~0 >> 1);    
  5.     static const int MIN = -(int)((unsigned)~0 >> 1) - 1;    
  6.     static const int MAX_DIV = (int)((unsigned)~0 >> 1) / 10;    
  7.     static const int MIN_DIV = (int)((((unsigned)~0 >> 1) + 1) / 10);    
  8.     static const int MAX_R = (int)((unsigned)~0 >> 1) % 10;    
  9.     static const int MIN_R = (int)((((unsigned)~0 >> 1) + 1) % 10);    
  10.     int n = 0;    
  11.     int sign = 1;    
  12.     int c;    
  13.     
  14.     while (isspace(*str))    
  15.         ++str;    
  16.     if (*str == '+' || *str == '-')    
  17.     {    
  18.         if (*str == '-')    
  19.             sign = -1;    
  20.         ++str;    
  21.     }    
  22.     while (isdigit(*str))    
  23.     {    
  24.         c = *str - '0';    
  25.         if (sign > 0 && (n > MAX_DIV || (n == MAX_DIV && c >= MAX_R)))    
  26.         {    
  27.             n = MAX;    
  28.             break;    
  29.         }    
  30.         else if (sign < 0 && (n > MIN_DIV     
  31.                                                     || (n == MIN_DIV && c >= MIN_R)))    
  32.         {    
  33.             n = MIN;    
  34.             break;    
  35.         }    
  36.         n = n * 10 + c;    
  37.         ++str;    
  38.     }    
  39.     return sign > 0 ? n : -n;    
  40. }    
    部分数据的测试结果如下图所示：
输入            输出
10522545459  : 2147483647
-10522545459 : -2147483648
2147483648   : 2147483647
-2147483648  : -2147483648

   是否已是完美？如MJN君本人所说“我的实现与linux内核的atoi函数的实现, 都有一个共同的问题: 即使出错, 函数也返回了一个值, 导致调用者误认为自己传入的参数是正确的, 但是可能会导致程序的其他部分产生莫名的错误且很难调试”。


  9、最后看下Nut/OS中atoi的实现，同时，本小节内容主要来自参考文献条目9，即MJN的博客：

  1. 00077 #include <compiler.h>  
  2. 00078 #include <stdlib.h>  
  3. 00079   
  4. 00084   
  5. 00092 int atoi(CONST char *str)  
  6. 00093 {  
  7. 00094     return ((int) strtol(str, (char **) NULL, 10));  
  8. 00095 }  

  上述代码中strtol实现的思想跟上文第7节所述的MJN君的思路类似，也是除法代替乘法。加上测试函数后的具体代码如下：

  1. #include <errno.h>  
  2. #include <stdio.h>  
  3. #include <ctype.h>  
  4. #include <limits.h>  
  5.   
  6. #define CONST      const  
  7.   
  8. long mstrtol(CONST char *nptr, char **endptr, int base)  
  9. {  
  10.     register CONST char *s;  
  11.     register long acc, cutoff;  
  12.     register int c;  
  13.     register int neg, any, cutlim;  
  14.   
  15.     /* 
  16.      * Skip white space and pick up leading +/- sign if any. 
  17.      * If base is 0, allow 0x for hex and 0 for octal, else 
  18.      * assume decimal; if base is already 16, allow 0x. 
  19.      */  
  20.     s = nptr;  
  21.     do {  
  22.         c = (unsigned char) *s++;  
  23.     } while (isspace(c));  
  24.     if (c == '-') {  
  25.         neg = 1;  
  26.         c = *s++;  
  27.     } else {  
  28.         neg = 0;  
  29.         if (c == '+')  
  30.             c = *s++;  
  31.     }  
  32.     if ((base == 0 || base == 16) && c == '0' && (*s == 'x' || *s == 'X')) {  
  33.         c = s[1];  
  34.         s += 2;  
  35.         base = 16;  
  36.     }  
  37.     if (base == 0)  
  38.         base = c == '0' ? 8 : 10;  
  39.   
  40.     /* 
  41.      * Compute the cutoff value between legal numbers and illegal 
  42.      * numbers.  That is the largest legal value, divided by the 
  43.      * base.  An input number that is greater than this value, if 
  44.      * followed by a legal input character, is too big.  One that 
  45.      * is equal to this value may be valid or not; the limit 
  46.      * between valid and invalid numbers is then based on the last 
  47.      * digit.  For instance, if the range for longs is 
  48.      * [-2147483648..2147483647] and the input base is 10, 
  49.      * cutoff will be set to 214748364 and cutlim to either 
  50.      * 7 (neg==0) or 8 (neg==1), meaning that if we have accumulated 
  51.      * a value > 214748364, or equal but the next digit is > 7 (or 8), 
  52.      * the number is too big, and we will return a range error. 
  53.      * 
  54.      * Set any if any `digits' consumed; make it negative to indicate 
  55.      * overflow. 
  56.      */  
  57.     cutoff = neg ? LONG_MIN : LONG_MAX;  
  58.     cutlim = cutoff % base;  
  59.     cutoff /= base;  
  60.     if (neg) {  
  61.         if (cutlim > 0) {  
  62.             cutlim -= base;  
  63.             cutoff += 1;  
  64.         }  
  65.         cutlim = -cutlim;  
  66.     }  
  67.     for (acc = 0, any = 0;; c = (unsigned char) *s++) {  
  68.         if (isdigit(c))  
  69.             c -= '0';  
  70.         else if (isalpha(c))  
  71.             c -= isupper(c) ? 'A' - 10 : 'a' - 10;  
  72.         else  
  73.             break;  
  74.         if (c >= base)  
  75.             break;  
  76.         if (any < 0)  
  77.             continue;  
  78.         if (neg) {  
  79.             if ((acc < cutoff || acc == cutoff) && c > cutlim) {  
  80.                 any = -1;  
  81.                 acc = LONG_MIN;  
  82.                 errno = ERANGE;  
  83.             } else {  
  84.                 any = 1;  
  85.                 acc *= base;  
  86.                 acc -= c;  
  87.             }  
  88.         } else {  
  89.             if ((acc > cutoff || acc == cutoff) && c > cutlim) {  
  90.                 any = -1;  
  91.                 acc = LONG_MAX;  
  92.                 errno = ERANGE;  
  93.             } else {  
  94.                 any = 1;  
  95.                 acc *= base;  
  96.                 acc += c;  
  97.             }  
  98.         }  
  99.     }  
  100.     if (endptr != 0)  
  101.         *endptr = (char *) (any ? s - 1 : nptr);  
  102.     return (acc);  
  103. }  
  104.   
  105. int matoi2(CONST char *str)  
  106. {  
  107.     return ((int) mstrtol(str, (char **) NULL, 10));  
  108. }  
  109.   
  110. int mgetline(char* buf, size_t n) {  
  111.   size_t idx = 0;  
  112.   int c;  
  113.     
  114.   while (--n > 0 && (c = getchar()) != EOF && c != '\n') {  
  115.     buf[idx++] = c;  
  116.   }  
  117.   buf[idx] = '\0';  
  118.   return idx;  
  119. }  
  120.   
  121. #define MAX_LINE 200  
  122.   
  123. int main() {  
  124.     char buf[MAX_LINE];  
  125.     while (mgetline(buf, MAX_LINE) >= 0) {  
  126.         if (strcmp(buf, "quit") == 0) break;  
  127.         printf("matoi2=%d\n", matoi2(buf));  
  128.     }  
  129.     return 0;  
  130. }  

    同样，MJN对上述实现测试了下，结果如下:

10522545459
matoi2=2147483647
-10522545459
matoi2=-2147483648

    程序貌似对溢出的处理是正确的, 真的吗? 再把测试数据换成"10522545454"（与"10522545459"的区别在于最后一个字符）

10522545454
matoi2=1932610862
-10522545454
matoi2=-1932610862

    症结就在于下面这段代码：

  1. if (neg) {  
  2.             if ((acc < cutoff || acc == cutoff) && c > cutlim) {  
  3.                 any = -1;  
  4.                 acc = LONG_MIN;  
  5.                 errno = ERANGE;  
  6.             } else {  
  7.                 any = 1;  
  8.                 acc *= base;  
  9.                 acc -= c;  
  10.             }  
  11.         } else {  
  12.             if ((acc > cutoff || acc == cutoff) && c > cutlim) {  
  13.                 any = -1;  
  14.                 acc = LONG_MAX;  
  15.                 errno = ERANGE;  

    要想得到正确的输出结果，需要改动两个地方：

    ①其中这行：

  1. if ((acc > cutoff || acc == cutoff) && c > cutlim)  

    应该改为：

  1. if ( acc > cutoff ||  (acc == cutoff) && c > cutlim)  )  

    ②与此同时，这行:

  1. if ((acc < cutoff || acc == cutoff) && c > cutlim) {  

    改为：

  1. if (acc < cutoff || (acc == cutoff && c > cutlim)) {  

    为何要这样修改呢？细心的读者相信还是会记得上文第8节中关于正数的两种溢出情况的可能性：“对于正数来说，它溢出的可能性有两种：

  1. 一种是诸如2147483650，即n > MAX/10 的；
  2. 一种是诸如2147483649，即n == MAX/10 && c > MAX%10。”

    也就是说无论是"10522545459"，还是"10522545454"，都是属于第1种情况，即“诸如2147483650，即n > MAX/10的”，此时直接返回MAX_INT即可，所以不需要也不能再去判断n == MAX/10的情况。

    这个处理思路类似于上文第8节处理溢出情况的代码：

  1. if (sign > 0 && (n > MAX/10 || (n == MAX/10 && c > MAX%10)))      
  2.         {      
  3.             n = MAX;      
  4.             break;      
  5.         }      
  6.         else if (sign < 0 && (n > (unsigned)MIN/10       
  7.                               || (n == (unsigned)MIN/10 && c > (unsigned)MIN%10)))      
  8.         {      
  9.             n = MIN;      
  10.             break;      
  11.         }      

    So，修改过后的代码测试正常:

10522545459
matoi2=2147483647
-10522545459\
matoi2=-2147483648
10522545454
matoi2=2147483647
-10522545454
matoi2=-2147483648
quit
    OK，字符串转换成整数这一问题已基本解决。但如果面试官继续问你，如何把整数转换成字符串呢？欢迎于本文评论下或hero上show出你的思路或代码。

第三十一章、带通配符的字符串匹配问题

字符串匹配问题，给定一串字符串，按照指定规则对其进行匹配，并将匹配的结果保存至output数组中，多个匹配项用空格间隔，最后一个不需要空格。

要求：

  1. 匹配规则中包含通配符？和*，其中？表示匹配任意一个字符，*表示匹配任意多个（>=0）字符。
  2. 匹配规则要求匹配最大的字符子串，例如a*d,匹配abbdd而非abbd,即最大匹配子串。
  3. 匹配后的输入串不再进行匹配，从当前匹配后的字符串重新匹配其他字符串。

请实现函数：char* my_find(char  input[],   char rule[])

举例说明

input:abcadefg
rule:a?c
output:abc

input :newsadfanewfdadsf
rule: new
output: new new

input :breakfastfood
rule: f*d
output:fastfood

注意事项：

  1. 自行实现函数my_find，勿在my_find函数里夹杂输出，且不准用C、C++库，和Java的String对象；
  2. 请注意代码的时间，空间复杂度，及可读性，简洁性；
  3. input=aaa，rule=aa时，返回一个结果aa，即可。

    1、本题与上述第三十章的题不同，上题字符串转换成整数更多考察对思维的全面性和对细节的处理，本题则更多的是编程技巧。闲不多说，直接上代码：

  1. //copyright@cao_peng 2013/4/23  
  2. int str_len(char *a) {  //字符串长度  
  3.     if (a == 0) {  
  4.         return 0;  
  5.     }  
  6.     char *t = a;  
  7.     for (;*t;++t)  
  8.         ;  
  9.     return (int) (t - a);  
  10. }  
  11.   
  12. void str_copy(char *a,const char *b,int len) {  //拷贝字符串 a = b  
  13.     for (;len > 0; --len, ++b,++a) {  
  14.         *a = *b;  
  15.     }  
  16.     *a = 0;  
  17. }  
  18.   
  19. char *str_join(char *a,const char *b,int lenb) { //连接字符串 第一个字符串被回收  
  20.     char *t;  
  21.     if (a == 0) {  
  22.         t = (char *) malloc(sizeof(char) * (lenb + 1));   
  23.         str_copy(t, b, lenb);  
  24.         return t;  
  25.     }  
  26.     else {  
  27.         int lena = str_len(a);  
  28.         t = (char *) malloc(sizeof(char) * (lena + lenb + 2));  
  29.         str_copy(t, a, lena);  
  30.         *(t + lena) = ' ';  
  31.         str_copy(t + lena + 1, b, lenb);  
  32.         free(a);  
  33.         return t;  
  34.     }  
  35. }  
  36.   
  37. int canMatch(char *input, char *rule) { // 返回最长匹配长度 -1表示不匹配　  
  38.     if (*rule == 0) { //已经到rule尾端  
  39.         return 0;  
  40.     }  
  41.     int r = -1 ,may;  
  42.     if (*rule == '*') {  
  43.         r = canMatch(input, rule + 1);  // *匹配0个字符  
  44.         if (*input) {  
  45.             may = canMatch(input + 1, rule);  // *匹配非0个字符  
  46.             if ((may >= 0) && (++may > r)) {  
  47.                 r = may;  
  48.             }  
  49.         }  
  50.     }  
  51.     if (*input == 0) {  //到尾端  
  52.         return r;  
  53.     }  
  54.     if ((*rule == '?') || (*rule == *input)) {  
  55.         may = canMatch(input + 1, rule + 1);  
  56.         if ((may >= 0) && (++may > r)) {  
  57.             r = may;  
  58.         }  
  59.     }  
  60.     return r;  
  61. }  
  62.   
  63. char * my_find(char  input[],   char rule[]) {  
  64.     int len = str_len(input);  
  65.     int *match = (int *) malloc(sizeof(int) * len);  //input第i位最多能匹配多少位 匹配不上是-1  
  66.     int i,max_pos = - 1;  
  67.     char *output = 0;  
  68.   
  69.     for (i = 0; i < len; ++i) {  
  70.         match[i] = canMatch(input + i, rule);  
  71.         if ((max_pos < 0) || (match[i] > match[max_pos])) {  
  72.             max_pos = i;  
  73.         }  
  74.     }  
  75.     if ((max_pos < 0) || (match[max_pos] <= 0)) {  //不匹配  
  76.         output = (char *) malloc(sizeof(char));  
  77.         *output = 0;   // \0  
  78.         return output;  
  79.     }  
  80.     for (i = 0; i < len;) {  
  81.         if (match[i] == match[max_pos]) { //找到匹配  
  82.             output = str_join(output, input + i, match[i]);  
  83.             i += match[i];  
  84.         }  
  85.         else {  
  86.             ++i;  
  87.         }  
  88.     }  
  89.     free(match);  
  90.     return output;  
  91. }  

     2、本题也可以直接写出DP方程，如下代码所示：

  1. //copyright@chpeih 2013/4/23  
  2. char* my_find(char  input[],   char rule[])  
  3. {  
  4.     //write your code here  
  5.     int len1,len2;  
  6.     for(len1 = 0;input[len1];len1++);  
  7.     for(len2 = 0;rule[len2];len2++);  
  8.     int MAXN = len1>len2?(len1+1):(len2+1);  
  9.     int  **dp;  
  10.   
  11.     //dp[i][j]表示字符串1和字符串2分别以i j结尾匹配的最大长度  
  12.     //记录dp[i][j]是由之前那个节点推算过来  i*MAXN+j  
  13.     dp = new int *[len1+1];  
  14.     for (int i = 0;i<=len1;i++)  
  15.     {  
  16.         dp[i] = new int[len2+1];  
  17.   
  18.     }  
  19.   
  20.     dp[0][0] = 0;  
  21.     for(int i = 1;i<=len2;i++)  
  22.         dp[0][i] = -1;  
  23.     for(int i = 1;i<=len1;i++)  
  24.         dp[i][0] = 0;  
  25.   
  26.     for (int i = 1;i<=len1;i++)  
  27.     {  
  28.         for (int j = 1;j<=len2;j++)  
  29.         {  
  30.             if(rule[j-1]=='*'){  
  31.                 dp[i][j] = -1;  
  32.                 if (dp[i-1][j-1]!=-1)  
  33.                 {  
  34.                     dp[i][j] = dp[i-1][j-1]+1;  
  35.   
  36.                 }  
  37.                 if (dp[i-1][j]!=-1 && dp[i][j]<dp[i-1][j]+1)  
  38.                 {  
  39.                     dp[i][j] = dp[i-1][j]+1;  
  40.   
  41.                 }  
  42.             }else if (rule[j-1]=='?')  
  43.             {  
  44.                 if(dp[i-1][j-1]!=-1){  
  45.                     dp[i][j] = dp[i-1][j-1]+1;  
  46.   
  47.                 }else dp[i][j] = -1;  
  48.             }   
  49.             else  
  50.             {  
  51.                 if(dp[i-1][j-1]!=-1 && input[i-1]==rule[j-1]){  
  52.                     dp[i][j] = dp[i-1][j-1]+1;  
  53.                 }else dp[i][j] = -1;  
  54.             }  
  55.         }  
  56.     }  
  57.   
  58.     int m = -1;//记录最大字符串长度  
  59.     int *ans = new int[len1];  
  60.     int count_ans = 0;//记录答案个数  
  61.     char *returnans = new char[len1+1];  
  62.     int count = 0;  
  63.     for(int i = 1;i<=len1;i++)  
  64.         if (dp[i][len2]>m){  
  65.             m = dp[i][len2];  
  66.             count_ans = 0;  
  67.             ans[count_ans++] = i-m;  
  68.         }else if(dp[i][len2]!=-1 &&dp[i][len2]==m){  
  69.             ans[count_ans++] = i-m;  
  70.         }  
  71.   
  72.         if (count_ans!=0)  
  73.         {      
  74.             int len = ans[0];  
  75.             for (int i = 0;i<m;i++)  
  76.             {  
  77.                 printf("%c",input[i+ans[0]]);  
  78.                 returnans[count++] = input[i+ans[0]];  
  79.             }  
  80.             for (int j = 1;j<count_ans;j++)  
  81.             {  
  82.                 printf(" ");  
  83.                 returnans[count++] = ' ';  
  84.                 len = ans[j];  
  85.                 for (int i = 0;i<m;i++)  
  86.                 {  
  87.                     printf("%c",input[i+ans[j]]);  
  88.                     returnans[count++] = input[i+ans[j]];  
  89.                 }  
  90.             }  
  91.             printf("\n");  
  92.             returnans[count++] = '\0';  
  93.         }  
  94.   
  95.         return returnans;  
  96. }  

     欢迎于本文评论下或hero上show your code。

参考文献及推荐阅读

  1. http://zhedahht.blog.163.com/blog/static/25411174200731139971/；
  2. http://hero.pongo.cn/，本文大部分代码都取自左边hero上参与答题者提交的代码，欢迎你也去挑战；
  3. 字符串转换成整数题目完整描述：http://hero.pongo.cn/Question/Details?ID=47&ExamID=45；
  4. 字符串匹配问题题目完整描述：http://hero.pongo.cn/Question/Details?ID=28&ExamID=28；
  5. linux3.8.4版本下的相关字符串整数转换函数概览：https://git.kernel.org/cgit/linux/kernel/git/stable/linux-stable.git/tree/lib/vsprintf.c?id=refs/tags/v3.9.4；
  6. 关于linux中的likely和unlikely：http://blog.21ic.com/user1/5593/archives/2010/68193.html；
  7. 如果你喜欢编程挑战，除了topcoder和hero，你应该还多去leetcode上逛逛：http://leetcode.com/onlinejudge；
  8. atio函数的实现：http://blog.csdn.net/njnu_mjn/article/details/9099405；
  9. atoi函数的实现: linux内核atoi函数的测试：http://blog.csdn.net/njnu_mjn/article/details/9104143；
  10. Nut/OS中atoi函数的实现：http://www.ethernut.de/api/atoi_8c_source.html；
  11. 一读者写的hero上“字符串转换成整数”一题的解题报告（测试正确）：http://blog.csdn.net/u011070134/article/details/9116831；
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞