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

В теме Методы алгоритмов: углубление · Учебная карта
Главная мысль
В дереве выражения внутренний узел обозначает операцию, а его дети — операнды. Структура хранит группировку: одинаковые числа и знаки дают разные результаты при разных связях. Построение дерева само по себе не требует выполнения произвольного кода.
Корень — последняя операция объединения
В выражении 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. Называть его универсальным безопасным калькулятором было бы неверно; ограничения ресурсов нужны и при работе с литералами.
От чтения к действию
А теперь — вы
Частые вопросы
Как представить отрицательное число −3?
Грамматика может хранить знак как унарную операцию над числом 3. Это отличается от бинарного вычитания, у которого два операнда.
Совпадают ли разные деревья с одинаковым результатом?
Не обязательно. Выражения 2+3 и 1+4 равны по значению, но имеют разные листья. Для обучения порядку действий важно различать структуру и численный ответ.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как базовый случай останавливает рекурсию
Проверяем базовый случай и движение к нему на рекурсивной сумме, ограничиваем допустимый ввод и различаем доказательство завершения с ограничением глубины стека.
Открыть темуКак отличить данные с угловыми скобками от HTML-разметки
Отделяем текст от HTML-разметки, выбираем контекстное экранирование при выводе и объясняем, почему один способ замены не защищает произвольный JavaScript или URL.
Открыть тему