Как обходить дерево и разбирать арифметическое выражение?

Дерево — связный ациклический граф с выделенным корнем, если рассматривается иерархия. Каждый узел, кроме корня, имеет единственного родителя; листья не имеют детей. Рекурсивная структура делает дерево естественным представлением каталогов, вызовов и вложенных выражений.

Обходы

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

Высота и размер

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

Дерево выражения

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

Разбор записи

Для полностью скобочной формы можно рекурсивно читать «скобка — левое выражение — операция — правое выражение — скобка». Для обычной инфиксной записи применяют стек операторов или грамматику с уровнями приоритета. Ошибка в ассоциативности особенно заметна для вычитания и деления.

Контрольная задача

Постройте дерево для выражения a + b · (c − d), выпишите три порядка обхода и вычислите значение для конкретных чисел. Затем измените скобки и сравните деревья. Такое упражнение связывает синтаксис, структуру данных и рекурсивный алгоритм в одной модели.

Обход выражает место оператора относительно поддеревьев

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

def evaluate_postfix(tokens: list[str]) -> int:
    stack: list[int] = []
    for token in tokens:
        if token.lstrip("-").isdigit():
            stack.append(int(token))
            continue
        right = stack.pop()
        left = stack.pop()
        stack.append({"+": left + right, "*": left * right}[token])
    if len(stack) != 1:
        raise ValueError("invalid expression")
    return stack[0]

assert evaluate_postfix("2 3 4 * +".split()) == 14

Для полного парсера нельзя вычислять словарь результатов заранее: деление на ноль в невыбранной ветке всё равно выполнится. Лучше хранить функции операций и проверять арность и допустимость непосредственно при применении.

Практика: из инфиксной записи в дерево

Разберите выражение (2 + 3) × (7 − 4) в дерево и выпишите три обхода. Реализуйте постфиксный вычислитель для +, −, × и целочисленного деления с диагностикой нехватки операндов, неизвестной операции и лишних значений в стеке. Затем вычислите высоту и число узлов дерева рекурсивно. Объясните, почему порядок вычитания требует сначала снять правый, а потом левый операнд.