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

Question

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

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

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

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

我不是在寻找库函数，而是在“纯 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

正如一些评论和答案所建议的那样，也许更清楚一点:在添加新数字之前，您必须在每次迭代中将结果“左移”乘以 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