在一次传递中从字符串解析 int 的算法

Question

我正在尝试编写一个从字符串表示形式解析整数的函数。

我的问题是我不知道如何一次遍历字符串就可以做到这一点。如果我提前知道输入仅包含 '0'、'1'、...、'9' 范围内的字符并且字符串的长度为 n，我当然可以计算

character_1 * 10^(n-1) + character_2 * 10^(n-2) + .... + character_n * 10^0

但我想处理我介绍的一般情况。

我不是在寻找库函数，而是在 "pure C" 中寻找实现此目的的算法。

这是我开始的代码：

int parse_int (const char * c1, const char * c2, int * i)
{
    /*
        [c1, c2]: Range of characters in the string
               i: Integer whose string representnation will be converted

        Returns the number of characters parsed. 

        Exs. "2342kjsd32" returns 4, since the first 4 characters were parsed.
             "hhsd3b23" returns 0
    */

    int n = 0;
    *i = 0;
    while (c1!= c2)
    {
        char c = *c1;
        if (c >= '0' && c <= '9')
        {

        }
    }
    return n;
}

Answer 1

这是一个工作版本：

#include <stdio.h>

int parse_int (const char * c1, const char * c2, int * i)
{
   /*
      [c1, c2]: Range of characters in the string
             i: Integer whose string representnation will be converted

      Returns the number of characters parsed. 

      Exs. "2342kjsd32" returns 4, since the first 4 characters were parsed.
      "hhsd3b23" returns 0
    */

   int n = 0;
   *i = 0;
   for (; c1 != c2; c1++)
   {
      char c = *c1;
      if (c >= '0' && c <= '9')
      {
         ++n;
         *i = *i * 10 + c - '0';
      }
      else
      {
         break;
      }
   }

   return n;
}

int main()
{
   int i;
   char const* c1 = "2342kjsd32";
   int n = parse_int(c1, c1+10, &i);
   printf("n: %d, i: %d\n", n, i);
   return 0;
}

输出：

n: 4, i: 2342

Answer 2

我认为这是计算解析字符的好方法

int parse(char *str)
{
    int k = 0;
    while(*str)
    {
        if((*str >= '0') & (*str <= '9'))
            break;
        str++;
        k++;
    }
    return k;
}

Answer 3

正如一些评论和答案所建议的那样，也许更清楚一点：您必须 "shift" 结果 "left" 通过在添加新数字之前的每次迭代中将其乘以 10 .

的确，这应该让我们想起Horner's method。如您所知，结果可以写成多项式：

result = c1 * 10^(n-1) + c2 * 10^(n-2) + ... + cn * 10^0

这个等式可以改写为：

result = cn + 10*(... + 10*(c2 + 10*c1))

这种方法所基于的形式是什么。从您已经看到的公式中，您不需要知道要乘以第一个数字的 10 的次方，直接从头开始。

这是一个例子：

#include <stdio.h>

int parse_int(const char * begin, const char * end, int * result) {
    int d = 0;
    for (*result = 0; begin != end; d++, begin++) {
        int digit = *begin - '0';
        if (digit >= 0 && digit < 10) {
            *result *= 10;
            *result += digit;
        }
        else break;
    }
    return d;
}

int main() {
    char arr[] = "2342kjsd32";
    int result;
    int ndigits = parse_int(arr, arr+sizeof(arr), &result);
    printf("%d digits parsed, got: %d\n", ndigits, result);
    return 0;
}

使用 sscanf() 也可以实现同样的效果，适用于使用 C 标准库（也可以处理负数）的每个人：

#include <stdio.h>

int main() {
    char arr[] = "2342kjsd32";
    int result, ndigits;
    sscanf(arr, "%d%n", &result, &ndigits);
    printf("%d digits parsed, got: %d\n", ndigits, result);
    return 0;
}

输出是（两种实现）：

$ gcc test.c && ./a.out
4 digits parsed, got: 2342

在一次传递中从字符串解析 int 的算法

Algorithm to parse an int from a string in one pass

c

algorithm

parsing