Выяснение того, что происходит с этим кодом (пример с рекурсивным спуском) - PullRequest
Новая
       37

Выяснение того, что происходит с этим кодом (пример с рекурсивным спуском)

0 голосов
/ 30 июня 2018

Я читаю книгу «Структуры данных и алгоритмы», и есть реальный пример, в частности анализатор, использующий рекурсивное спускание. Я немного новичок в C ++ (я изучаю его на стороне и, как я иду с C ++ Primer 5-го издания Стэнли Б. Липпмана).

Я немного застрял в коде и пытаюсь понять его. Является ли то, что я написал внизу (маркированные точки) точным описанием того, что происходит в функциях? Я бы опубликовал заголовок, но он слишком длинный, вы, вероятно, сможете найти его в Интернете, если поищете «Структуры данных». и алгоритмы в 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, чтобы он мог просматривать список
  • Ищет tmp, используя find ()
  • Если я не равен значению в конце списка, вернуть его
  • В противном случае переменная не может быть найдена

processNode ()

  • Обрабатывает узлы с помощью итератора i
  • Ищет переменную, которая соответствует tmp
  • Находит переменную и устанавливает ее значение равным значению e
  • В противном случае сохраните переменную в idList для последующего анализа

Ответы [ 2 ]

0 голосов
/ 30 июня 2018

Определите функцию, которая принимает указатель на символ (вероятно, это массив) и возвращает double: 

double Statement::findValue(char* id) {

Создать временный (умрет при возврате) тип IdNode на основе этого указателя: 

IdNode tmp(id);

Используйте функцию (std::, я думаю, но это может быть любая функция с теми же функциями), которая ищет tmp внутри контейнера idList. Результатом является целое число i, которое должно быть того же типа, что и контейнер: 

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

Проверьте, если что-то найдено. idList.end() означает «один конец», за последний элемент в контейнере: 

if (i != idList.end())

Верните элемент value (который является частью IdNode) для найденного предмета. Если value не является double, тогда конвертируйте в него. 

    return i->value;

В противном случае вызвать функцию issueError. 

else
    issueError("Unknown variable");

Функция выхода, возвращающая double со значением = 0: 

return 0;
}

То же самое, но: эта функция принимает два параметра и ничего не возвращает: 

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 member: 

    i->value = e;

В противном случае добавить tmp, вставить его в самом начале idList контейнера. 

else
    idList.push_front(tmp);

Функция выхода: 

}
0 голосов
/ 30 июня 2018

Ваше понимание в основном верно. Я опишу это утверждение за заявлением в несколько более точных терминах. 

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

Это создает переменную с именем tmp с использованием переданной строки. (Что ж, я предполагаю, что id - это строка. В Си обычно передают указатель на начало массива символов с нулевым символом в конце, когда Вы хотите передать строку. В 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 &), которая возвращает true, если имена двух idNodes совпадают, независимо от того, совпадают ли поля значений.

Если в диапазоне нет совпадений, то std::find вернет конечный итератор. Если есть совпадение, он вернет итератор, который ссылается на соответствующий элемент. Итак ... 

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

Возвращает поле значения совпадения (если оно есть) или вызывает issueError, если его нет. 

    return 0;
}

В последнем случае, если issueError возвращает и не завершает программу или не генерирует исключение, функция вернет значение 0 (которое, поскольку тип возвращаемого значения является двойным, будет неявно преобразовано в 0.0 ).

processNode практически идентичен, за исключением того, что он устанавливает значение в найденном узле, а не возвращает его.

...