Деревья выражений

Модуль "Выражения" • урок 2 из 7 • ~8 минут

Что такое дерево выражения

Дерево выражения - это двоичное дерево. Главное правило его построения:

• Листья - всегда содержат операнды (константы или переменные, например A, 2, X).
• Внутренние узлы (и корень) - всегда содержат операции (например, +, -, *, /).

Дерево автоматически хранит приоритет операций своей структурой: операции на нижних ярусах дерева (глубже) должны быть вычислены в первую очередь! Это позволяет полностью отказаться от использования скобок при вычислениях.

Почему дерево именно двоичное? Это наследие архитектуры: базовые машинные операции двуместны - процессор складывает, вычитает и умножает ровно два числа. У любой операции не больше двух операндов, поэтому и у любого узла не больше двух сыновей.

Обходы дерева дают формы записи

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

• Прямой обход (КЛП - корень, левое, правое) генерирует префиксную форму: + A * B C.
• Симметричный обход (ЛКП - левое, корень, правое) генерирует привычную инфиксную форму. Чтобы приоритеты не сбились, при обходе приходится восстанавливать скобки вокруг поддеревьев: (A + (B * C)).
• Обратный обход (ЛПК - левое, правое, корень) генерирует постфиксную форму (ОПЗ): A B C * +. Именно так компиляторы получают из дерева готовую программу для стека.

Деревья выражений в коде

Опишем узел дерева на языке C. В узле-операции заполнено поле op, в узле-листе - поле value:

#include <stdio.h>

// Узел дерева выражения
typedef struct Node {
    char op;       // Операция ('+', '-', '*') или '\0', если это операнд
    int value;     // Значение числа (если это лист)
    struct Node *left, *right;
} Node;

Насколько тесно обходы связаны с формами записи, лучше всего видно по коду. Чтобы перевести дерево в ОПЗ, достаточно распечатать его концевым обходом (ЛПК) - вся "трансляция" умещается в несколько строк:

// Концевой обход (ЛПК) печатает выражение в обратной польской записи
void PrintPostfix(Node* root) {
    if (root == NULL) return;
    PrintPostfix(root->left);        // сначала левое поддерево
    PrintPostfix(root->right);       // затем правое
    if (root->left == NULL && root->right == NULL)
        printf("%d ", root->value);  // лист - печатаем операнд
    else
        printf("%c ", root->op);     // внутренний узел - операцию
}

Вычисляется готовое дерево так же просто - рекурсивно "снизу вверх". По сути это тот же концевой обход (ЛПК): сначала узнаем значения поддеревьев, затем применяем операцию корня.

// Рекурсивное вычисление (снизу вверх)
int Evaluate(Node* root) {
    if (root->left == NULL && root->right == NULL) {
        return root->value; // Если лист - просто возвращаем число
    }

    // Сначала считаем левое и правое поддеревья (спускаемся в глубину)
    int left_val = Evaluate(root->left);
    int right_val = Evaluate(root->right);

    // Затем применяем операцию корня к результатам
    switch(root->op) {
        case '+': return left_val + right_val;
        case '*': return left_val * right_val;
        case '-': return left_val - right_val;
        case '/': return left_val / right_val;
    }
    return 0;
}

Как получить дерево из строки?

Мы научились обходить и вычислять готовое дерево. Но компилятор получает выражение обычной строкой в инфиксной форме - и должен разобрать ее сам. Этому посвящена вся вторая половина модуля: алгоритм Рутисхаузера (урок 3), алгоритм Бауэра-Замельзона (урок 4) и сортировочная станция Дейкстры (урок 5).

Есть и еще один путь, любимый современными компиляторами, - разбор по формальной грамматике. Он выходит за рамки экзаменационных билетов, поэтому спрятан под кат.

expr -> term   | expr + term | expr - term
term -> fact   | term * fact | term / fact
fact -> (expr) | цифра | буква

typedef struct TNode {
    char data;                        // литера: операнд или знак операции
    struct TNode *left, *right;
} TNode;

TNode* makenode(char data, TNode* l, TNode* r) {
    TNode* t = malloc(sizeof(TNode));
    t->data = data;
    t->left = l;
    t->right = r;
    return t;
}

int ch;                               // текущая литера выражения
void next(void) { ch = getchar(); }

TNode* expr(void);                    // прототип: expr -> term -> fact -> expr

TNode* fact(void) {                   // множитель: операнд или (expr)
    TNode* t;
    if (ch == '(') {
        next();                       // пропускаем '('
        t = expr();                   // внутри скобок - целое подвыражение
        next();                       // пропускаем ')'
    } else {
        t = makenode(ch, NULL, NULL); // лист: цифра или переменная
        next();
    }
    return t;
}

TNode* term(void) {                   // слагаемое: цепочка множителей
    TNode* t = fact();
    while (ch == '*' || ch == '/') {
        char op = ch;
        next();
        t = makenode(op, t, fact());  // накопленное уходит в левое поддерево
    }
    return t;
}

TNode* expr(void) {                   // выражение: цепочка слагаемых
    TNode* t = term();
    while (ch == '+' || ch == '-') {
        char op = ch;
        next();
        t = makenode(op, t, term());
    }
    return t;
}

TNode* parse(void) { next(); return expr(); }