Информатика · объяснение и практика

Как дерево выражения сохраняет приоритет без выполнения кода

Строим дерево арифметического выражения, отличаем группировку от порядка записи и задаём ограниченный набор узлов без выполнения пользовательского кода.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Методы алгоритмов: углубление · Учебная карта

Главная мысль

В дереве выражения внутренний узел обозначает операцию, а его дети — операнды. Структура хранит группировку: одинаковые числа и знаки дают разные результаты при разных связях. Построение дерева само по себе не требует выполнения произвольного кода.

Корень — последняя операция объединения

В выражении 5+2×6 сначала умножают 2 на 6, затем прибавляют 5. Корнем дерева будет сложение, его левым ребёнком — число 5, правым — узел умножения с детьми 2 и 6. Корень не обязан соответствовать первому или последнему символу в строке: он соединяет главные части выражения.

Для (5+2)×6 корнем станет умножение, слева от него расположится сложение 5 и 2. Первый вариант даёт 17, второй — 42. Скобки уже отразились в структуре, поэтому отдельный лист для каждой скобки в простом абстрактном дереве не нужен. Важно сохранить именно отношения операций, а не только список встреченных токенов.

Пример

У 18−7−2 обычная левая группировка даёт (18−7)−2=9.

Дерево с корнем «минус» и правым поддеревом 7−2 означает другое выражение 18−(7−2)=13. Вычитание не позволяет свободно переставлять скобки.

Разбор и вычисление — отдельные этапы

Сначала текст разбивают на допустимые токены, затем по грамматике строят дерево. После этого можно проверить, что каждый узел относится к разрешённому набору: например, число, сложение, вычитание, умножение и скобочная группировка. Имена функций, обращения к объектам и произвольные команды такой учебной грамматике не нужны.

Для получения значения узел вычисляют по значениям детей, а число возвращает само себя. Но дерево можно использовать и без подсчёта: показать порядок действий, сравнить группировку или сформировать подсказку. Использовать выполнение общего программного кода вместо разбора арифметики не следует: это даёт вводу несоразмерно широкие возможности.

Проверяйте допустимость даже после успешного разбора

Синтаксически правильное деление может иметь нулевой знаменатель. Если разрешено возведение в степень, даже короткая запись способна задавать чрезмерно большое вычисление. Поэтому кроме перечня узлов ограничивают длину строки, глубину дерева и допустимые размеры чисел. Разбор без исполнения ещё не означает бесплатную обработку любого объёма.

В Python AST представляет структуру программы, но его наличие само по себе не ограничивает язык школьной арифметикой. Отдельно выбранный обход обязан отклонять ненужные типы узлов. А literal_eval предназначен для литералов и контейнеров, не для произвольной арифметики вроде 5+2×6. Называть его универсальным безопасным калькулятором было бы неверно; ограничения ресурсов нужны и при работе с литералами.

От чтения к действию

А теперь — вы

Какой узел будет корнем дерева выражения 8×(4−1)+2 при обычном приоритете операций?

Частые вопросы

Как представить отрицательное число −3?

Грамматика может хранить знак как унарную операцию над числом 3. Это отличается от бинарного вычитания, у которого два операнда.

Совпадают ли разные деревья с одинаковым результатом?

Не обязательно. Выражения 2+3 и 1+4 равны по значению, но имеют разные листья. Для обучения порядку действий важно различать структуру и численный ответ.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться