Построение и сворачивание деревьев выражений

Поскольку Rust стал настолько популярным и собрал таких преданных поклонников, я решил отказаться от моего любимого JS и недавно изучить Rust. И должен сказать, это путешествие не для слабонервных. К счастью (хотя и вводит в заблуждение в некоторых редких случаях), компилятор - ваш лучший друг - он почти всегда скажет вам, что вы сделали неправильно, и даже предложит полезные решения. После того, как вы проведете с ним некоторое время и преодолеете крутой начальный этап обучения, вы начнете любить Rust - я люблю!

Сегодня я хотел бы реализовать мою любимую структуру данных в стиле Rust: двоичное дерево. Двоичное дерево - это типичное дерево - оно состоит из узлов, которые содержат его (потенциально глубоко) вложенные значения. Особенностью двоичного дерева является то, что его узлы имеют только два дочерних значения: Left и Right. Обычно двоичные деревья используются для представления таких вещей, как математические выражения, но могут использоваться для обработки упрощенных грамматик. Для нашей реализации нашим узлам также будет удобно знать, какой тип операции они представляют. Мы постараемся сделать его универсальным, чтобы базовая структура не зависела от типа. Вот простое представление двоичного дерева:

На этом изображении оконечные узлы имеют числа. Также хорошо отметить, что двоичные деревья смещены влево и по определению глубина превыше всего. Это означает, что когда вы сворачиваете двоичное дерево, оценка будет опускаться в первый левый узел настолько глубоко, насколько это возможно, прежде чем перейти к более правым узлам, а левые узлы этих узлов перед его более правыми узлами и т. Д. Рекурсивно. Я объясню немного больше по ходу дела.

Представим себе минимальную структуру для представления данных нашего узла:

… И компилятор сразу на нас злится. Структура не может содержать ссылки на себя напрямую (она становится рекурсивным типом, что недопустимо в Rust). Но для удобства мы можем поместить наши рекурсивные узлы в Box. Box - это просто причудливый способ сказать: «это указатель, который ссылается на объект в куче». Посмотрим, решит ли это нашу проблему:

Вот и все. Наш Box добавил уровень косвенности, сохранив только указатель на наш BTNode, что позволяет нам обойти рекурсивный тип. А что насчет Оп? Op будет enum, который представляет возможные операции, которые могут быть выполнены на наших узлах. В этом примере мы будем придерживаться простой арифметики:

Достаточно просто. У нас есть вариант для нескольких основных арифметических операций. Обратите внимание Id(T)? Это особенное. Поскольку нам нужно, чтобы значения в нашем двоичном дереве были экземплярами структур BTNode, невозможно просто поместить i32 прямо в наше дерево. Это проблема, потому что необработанные числа - это то, что мы ожидаем от наших конечных значений. Представьте себе выражение (3 + 4) * (5 * 2). Мы можем думать об этом как о двоичном дереве с тремя узлами. Головной узел - это Mul Узел со значениями как левого, так и правого узла. Левый узел головы - это узел Add с левым и правым значениями 3 и 4 соответственно. Справа - Mul Узел 5 и 2. Эти необработанные числа - это то, что мы называем конечными значениями.

Это называется конечной ценностью, потому что находится в конце. Если обычный узел похож на ветвь, конечный узел - это лист. Когда вы дойдете до одного, больше нет уровней вложенности, по которым можно было бы спуститься по пути, выбранному вашим кодом, и значение в нем можно интерпретировать как необработанное значение вместо узла. Чтобы получить значения терминала от наших узлов, мы должны использовать наш Op::Id(T) вариант для хранения данных. Пока мы занимаемся этим, нам, вероятно, следует подумать о том, что наши левые и правые узлы в рамке могут быть не назначены в оконечном узле. Мы должны обернуть их каждый в Параметры, чтобы учесть это:

Теперь мы определили наши узлы так, что их дочерние узлы могут иметь значение Some boxed value или None. Хотя это определенно выглядит немного забавно. Однако мы можем сделать его немного лучше, используя псевдоним типа:

Мы можем поместить это в начало нашего кода и заменить длинную версию в наших BTNodes. Теперь, когда мы тщательно рассмотрели, как определить узел, давайте определим дерево:

Поскольку мы потратили время на то, чтобы хорошо определить узлы, эта часть проста. Наше дерево либо пусто , либо голова имеет значение Some node. Поскольку вложенные узлы являются значениями указателей на дочерние узлы, это все, что нам нужно для описания дерева. Теперь, когда мы обработали часть нашего дерева с данными, давайте перейдем к некоторой реализации. Начнем с наших узлов.

Достаточно просто. Я расширил его по вертикали, чтобы получилось. Теперь у нас есть способ создавать экземпляры нашей структуры узла. Но представьте, что вы объявляете «новый» для каждого узла - это много ввода! Давайте немного отвлечемся от этого и создадим несколько специализированных конструкторов.

Каждая из этих функций создает специализированную версию BTNode, которая позже упростит их объявление. Все они используют преимущества исходного BTNode::new конструктора, за исключением IdNode, который создает BTNode напрямую, потому что значения левого и правого узлов не важны, он заботится только о его i32 значении.

Теперь давайте подумаем о реализации некоторых функций для нашего двоичного дерева. У него должна быть одна основная функция - сворачивать свои узлы в одно значение. Теперь напишем эту функцию.

Я также включил простой конструктор. Давайте пройдемся по этому коду. Глядя на сигнатуру нашей реализации i32, мы видим, что она принимает указатель на узел и возвращает i32. Первое, что мы делаем, это объявляем пару изменяемых значений left и right Option<i32> и инициализируем их как None - мы можем переназначить их, когда сворачиваем наши дочерние узлы. Мы рекурсивно вызываем collapse для дочерних узлов, чтобы переназначить наши левые или правые значения тогда и только тогда, когда любое из этих значений является нетерминальным узлом (узлы, которые не являются IdNodes). Затем мы используем if let с нашими левыми и правыми значениями, чтобы извлечь значения в i32. В этом процессе мы переназначаем переменные l и r как неизменяемые (когда мы повторно объявляем их с let). Наконец, мы сопоставляем операцию узла, комбинируя и возвращая значения (или panic!ing, если мы случайно делим на ноль).

Давайте создадим дерево из этого изображения:

Это представляет собой выражение (10 - (2 * 2)) + (8 + (10 / 2)). Зеленые числа указывают порядок, в котором наш алгоритм достигает каждого узла. Красные символы - это то, что мы будем использовать в качестве значений нашего узла.

Консоль должна распечатать 19. Как и ожидалось, если бы мы прошли через это сами.

Вот ссылка на Rust Playground, которую вы можете взломать.

Это простой пример, но представьте, что наша Op enum представляет собой нечто иное. Мы могли бы реализовать двоичное дерево для чего-то другого, кроме i32, и использовать его для другой цели. Как разбор простой грамматики скриптов или накопление специальных эффектов в видеоигре. Они представляют собой особенно полезную структуру данных в мире информатики.

Надеюсь, вам понравилась еще одна статья о Rust. До следующего раза, читатель!