弄清楚这段代码是怎么回事（递归下降案例研究）

Question

我正在读一本数据结构和算法的书，其中有一个关于递归的案例研究，特别是一个使用递归下降的解析器。我对 C++ 有点陌生（我在一边学习它，一边学习 Stanley B. Lippman 的 C++ 入门第 5 版）。

我有点卡在代码上了，我正在努力理解它。我在底部（项目符号点）写的内容是否准确描述了函数中发生的事情？我会 post header，但是它有点太长了，如果你搜索“数据结构”，你可能可以在网上找到它 Adam Drozdek 的 C++ 和算法 - interpreter.h".

double Statement::findValue(char* id) {
    IdNode tmp(id);
    list<IdNode>::iterator i = find(idList.begin(), idList.end(), tmp);
    if (i != idList.end())
        return i->value;
    else
        issueError("Unknown variable");
    return 0;
}

void Statement::processNode(char* id, double e) {
    IdNode tmp(id, e);
    list<IdNode>::iterator i = find(idList.begin(), idList.end(), tmp);
    if (i != idList.end())
        i->value = e;
    else
        idList.push_front(tmp);
}

findValue()

寻找某个变量的值
使用迭代器 i 以便它可以遍历列表
使用 find() 查找 tmp
如果 i 不等于列表末尾的值，return它
否则找不到变量

进程节点()

使用迭代器 i 处理节点
寻找匹配 tmp 的变量
找到变量并将其值设置为 e
否则，将变量存储到 idList 以供稍后评估

Answer 1

你的理解基本是对的。我会逐句描述它更准确地说。

double Statement::findValue(char* id) {
    IdNode tmp(id);

这会使用传入的字符串构造一个名为 tmp 的变量。（好吧，我假设 id 是一个字符串。在 C 中，通常传递一个指向零开头的指针- 当你想传递一个字符串时终止字符数组。在 C++ 中，同样的事情很常见，但现在我们在标准库中有更好的字符串和范围类型，它变得不那么常见了。但并不是每个 char * 都是一个字符串。它可能只是一个指向单个字符的指针。不过，这里的上下文强烈表明它是一个字符串。)

    list<IdNode>::iterator i = find(idList.begin(), idList.end(), tmp);

使用std::find算法搜索从idList开头到结尾的元素范围，寻找等于tmp.

的元素

请注意 idList.end() 是一个迭代器，指示列表的实际结尾而不是列表中的最后一项。您可以将其视为列表中最后一个元素之后的一个元素。 C 和 C++ 中的迭代器范围（和数组索引）通常包含第一个值，不包含第二个值。因此 find 将从第一个元素开始并继续向上到（但不通过）列表的末尾。

此处未显示，但我假设 operator==(const idNode &, const idNode &) 有一个重载，如果两个 idNodes 的名称匹配，则 return 为真，无论值字段是否匹配.

如果范围内没有匹配项，则 std::find 将转到 return 结束迭代器。如果有匹配项，它将 return 一个引用匹配元素的迭代器。所以...

    if (i != idList.end())
        return i->value;
    else
      issueError("Unknown variable");

这 return 是匹配项的值字段（如果有的话），如果没有则调用 issueError。

    return 0;
}

在后一种情况下，假设 issueError returns 并且没有终止程序或抛出异常，函数将 return 值为 0（这，因为return 类型是双精度型，将隐式转换为 0.0)。

processNode 几乎相同，除了它在找到的节点中设置值而不是 returning 它。

Answer 2

定义一个接受指向 char 的指针（可能是一个数组）和 returns a double:

的函数

double Statement::findValue(char* id) {

根据该指针创建类型为 IdNode 的临时对象（将在 'return' 结束）：

IdNode tmp(id);

使用（std:: 我猜，但它可以是具有相同功能的任何函数）在容器 idList 内查找 tmp 的函数。结果是一个 interator i，它必须与容器使用的类型相同：

list<IdNode>::iterator i = find(idList.begin(), idList.end(), tmp);

检查是否找到了东西。 idList.end() 表示 "one past end"，beyond 容器中的最后一项：

if (i != idList.end())

Return 找到的项目的成员 value（属于 IdNode 的一部分）。如果 value 不是 double 则转换为它。

    return i->value;

否则，调用issueError函数。

else
    issueError("Unknown variable");

退出函数，返回值=0的double:

return 0;
}

相同，但是：此函数接受两个参数并且 returns 什么都不接受：

void Statement::processNode(char* id, double e) {

相同，但是：IdNode 构造函数使用两个参数：

IdNode tmp(id, e);

相同

list<IdNode>::iterator i = find(idList.begin(), idList.end(), tmp);

相同

if (i != idList.end())

现在，修改找到的项目。只需更新 value 成员：

    i->value = e;

否则，添加 tmp，将其插入idList容器的最开始。

else
    idList.push_front(tmp);

退出函数：

弄清楚这段代码是怎么回事（递归下降案例研究）

Figuring Out What's Going on This Code (Recursive Descent Case Study)

c++

iterator

stl-algorithm