Задачи модуля "Выражения": от ОПЗ до прошивки дерева

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

Описание алгоритма:

Допустим, нам дана строка: "T F & T |". Операнды: T (True, 1) и F (False, 0). Операторы: & (И), | (ИЛИ), ! (НЕ).

1. Читаем строку слева направо посимвольно. Используем Стек операндов.
2. Если встретили операнд (T или F): переводим в 1 или 0 и кладем в стек.
3. Если встретили бинарный оператор (& или |): извлекаем со стека ДВА числа, применяем логическую операцию и кладем результат обратно.
4. Если встретили унарный оператор (!): извлекаем ОДНО число, инвертируем его и кладем обратно.
5. В стеке останется ровно одно число - ответ.

#include <stdio.h>
#include <string.h>

#define MAX_STACK 100
int stack[MAX_STACK];
int top = -1;

void Push(int val) { stack[++top] = val; }
int Pop() { return stack[top--]; }

int EvaluateBooleanPostfix(const char* expr) {
    int len = strlen(expr);
    top = -1;

    for (int i = 0; i < len; i++) {
        char ch = expr[i];
        if (ch == ' ') continue;

        if (ch == 'T') Push(1);
        else if (ch == 'F') Push(0);
        else if (ch == '&') {
            int op2 = Pop();
            int op1 = Pop();
            Push(op1 & op2);
        } else if (ch == '|') {
            int op2 = Pop();
            int op1 = Pop();
            Push(op1 | op2);
        } else if (ch == '!') {
            int op = Pop();
            Push(!op);
        }
    }
    
    return Pop(); // Итоговый ответ
}

Так как числа многозначные, посимвольное чтение не подойдет. Воспользуйтесь функцией `strtok` для разбиения строки по пробелам и `atoi` для преобразования строк в числа.

Описание алгоритма:

Арифметическое выражение может содержать многозначные числа (например, "15 3 +"). Читать посимвольно нельзя, нужно разбивать строку на токены (слова).

1. Используем strtok, чтобы получить токены по пробелу.
2. Если токен - число (проверяем isdigit или через первый минус), преобразуем его atoi() и кладем в стек.
3. Если токен - оператор (+, -, *, /): извлекаем два верхних числа. Внимание: первый извлеченный - это правый операнд!
4. Вычисляем и кладем результат в стек.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_STACK 100
int stack[MAX_STACK];
int top = -1;

void Push(int val) { stack[++top] = val; }
int Pop() { return stack[top--]; }

int EvaluateMathPostfix(char* expr) {
    top = -1;
    char* token = strtok(expr, " ");
    
    while (token != NULL) {
        if (isdigit(token[0]) || (token[0] == '-' && isdigit(token[1]))) {
            Push(atoi(token));
        } else {
            int right = Pop();
            int left = Pop();
            
            switch (token[0]) {
                case '+': Push(left + right); break;
                case '-': Push(left - right); break;
                case '*': Push(left * right); break;
                case '/': Push(left / right); break;
            }
        }
        token = strtok(NULL, " ");
    }
    
    return Pop();
}

Используйте концевой обход дерева (ЛПК): сначала оптимизируйте потомков, а затем проверяйте текущий узел. Не забудьте освободить память удаляемых узлов.

Описание алгоритма:

Оптимизирующие компиляторы "схлопывают" ветки Абстрактного Синтаксического Дерева (AST). Если мы видим X + 0, можно заменить узел сложения на просто X. Используем концевой обход (ЛПК):

1. Рекурсивно оптимизируем левое и правое поддеревья.
2. Если текущий корень это +: проверяем сыновей. Если правый (или левый) равен 0, освобождаем узел нуля и корень +, а возвращаем оставшуюся непустую ветку.
3. Аналогично для операции * и сыновей, равных 1.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    char op;       // '+' или '*'
    int value;     // Число
    struct Node *left, *right;
} Node;

int IsLeafNumber(Node* node, int target_val) {
    if (node == NULL) return 0;
    if (node->left == NULL && node->right == NULL && node->op == '\0') {
        if (node->value == target_val) return 1;
    }
    return 0;
}

Node* OptimizeExpressionTree(Node* root) {
    if (root == NULL) return NULL;

    // 1. Сначала оптимизируем детей
    root->left = OptimizeExpressionTree(root->left);
    root->right = OptimizeExpressionTree(root->right);

    // 2. Обработка сложения с нулем
    if (root->op == '+') {
        if (IsLeafNumber(root->right, 0)) {
            Node* surviving = root->left;
            free(root->right);
            free(root);
            return surviving; // X + 0 => X
        }
        if (IsLeafNumber(root->left, 0)) {
            Node* surviving = root->right;
            free(root->left);
            free(root);
            return surviving;
        }
    }

    // 3. Обработка умножения на единицу
    if (root->op == '*') {
        if (IsLeafNumber(root->right, 1)) {
            Node* surviving = root->left;
            free(root->right);
            free(root);
            return surviving; // X * 1 => X
        }
        /* аналогично для левого 1 */
    }

    return root;
}

Совершайте симметричный обход и храните указатель на предыдущий посещенный узел. Если правый потомок предыдущего узла пуст, направьте его на текущий узел и выставьте флаг нити.

Описание алгоритма:

Мы заменяем пустые NULL указатели в листьях дерева на нити (указатели на следующий узел при симметричном обходе). Для этого нужен флаг isThreaded.

1. В рекурсии ЛКП передаем двойной указатель на prev (предыдущий посещенный узел).
2. Если у prev не было правого сына, делаем prev->right = current и prev->isThreaded = 1.
3. Обновляем prev = current и идем направо только если это настоящая ветвь (не нить).

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    char data; 
    struct Node* left;
    struct Node* right;
    int isThreaded; 
} Node;

// Передаем prev через двойной указатель
void CreateThreads(Node* root, Node** prev) {
    if (root == NULL) return;

    CreateThreads(root->left, prev);

    // Устанавливаем нить от предыдущего узла к текущему
    if (*prev != NULL && (*prev)->right == NULL) {
        (*prev)->right = root;
        (*prev)->isThreaded = 1;
    }
    
    *prev = root;

    // В правое поддерево идем, только если это не нить
    if (root->isThreaded == 0) {
        CreateThreads(root->right, prev);
    }
}