[算法] 字符串转换成整数


#1

题目描述

输入一个由数字组成的字符串,把它转换成整数并输出。例如:输入字符串“123”,输出整数123。
给定函数原型 int StrToInt(const char *str) ,实现字符串转换成整数的功能,不能使用库函数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. 整型溢出:输入的数字是以字符串的形式输入,因此输入一个很长的字符串将可能导致溢出。

考虑以上问题后,解法就比较简单了。下面是一个C++的例子。熟悉其他语言的同学也可以提供其他语言的解法。

// A simple C++ program for implementation of atoi 
#include <bits/stdc++.h>  
  
using namespace std; 
int myAtoi(const char *str) 
  { 
    int sign = 1, base = 0, i = 0; 
    // if whitespaces then ignore. 
    while (str[i] == ' ') 
     {   
      i++; 
     } 
    // sign of number 
    if (str[i] == '-' || str[i] == '+') { 
        sign = 1 - 2 * (str[i++] == '-');  
    } 
   // checking for valid input 
    while (str[i] >= '0' && str[i] <= '9')  
      { 
        //handling overflow test case   
        if (base >  INT_MAX / 10 || (base == INT_MAX / 10 && str[i] - '0' > 7)) { 
            if (sign == 1) return INT_MAX; 
            else return INT_MIN; 
        } 
        base  = 10 * base + (str[i++] - '0'); 
    } 
    return base * sign; 
} 
  
int main() 
{ 
    char str[] = "-123"; 
    int val = myAtoi(str); 
    printf ("%d ", val); 
    return 0; 
}