My Lab

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

struct tree{                // Дерево в котором информационные поля - число или знак
    char sign;
    int num;
    struct tree *left, *right;
};

struct stack{               // Стек нужен для построения обратной польской записи
    char c;
    struct stack* next;
};

char* polish(const char*, struct stack**);                  // Прототипы функций
char pop(struct stack**);
struct stack* push(struct stack**, char);
int priority(char);
struct tree* add(struct tree*, char, int);
int calc(struct tree*);
int isCorrect(char* string);
int flag = 1;

char* polish(const char* str, struct stack** node){         // Функция, строящая обратную польскую запись
    int i = 0, point = 0;
    char* out;
    if (!(out = (char*)malloc(50))) {
        puts("Ошибка при работе с памятью!");
        return 0;
    }
    printf("Исходное выражение %s\n", str);
    while (*(str + i) != '\0' && *(str + i) != '='){        // Цикл пока не закончится строка или пока не встретим равно.
        while (*(str + i) == ' ') i++;                      // Пропуск пробелов.
        if (*(str + i) == ')'){                             // Если встречаем закрывающуюся скобку, то удаляем
            while ((*node)->c != '(')
                *(out + point++) = pop(node);               // из стека все элементы до открывающейся скобки
            pop(node);                                      // включительно и записываем в строку.
        }
        if (*(str + i) >= '0' && *(str + i) <= '9'){        // Если встречаем цифру, то записываем в строку все число
            while (*(str + i) >= '0' && *(str + i) <= '9'){
                *(out + point++) = *(str + i);
                i++;
            }
            *(out + point++) = ' ';
            i--;
        }
        if (*(str + i) == '(') {                            // Если встречаем открывающуюся скобку, то заносим в стек
            *node = push(node, '(');                     // эту скобку
        }
        if (*(str + i) == '+' || *(str + i) == '-' || *(str + i) == '*' || *(str + i) == '/'){
            while ((*node != NULL) && (priority((*node)->c) >= priority(*(str + i))))
                *(out + point++) = pop(node);               // Если встречаем оператор, то удаляем из стека все элементы
            *node = push(node, *(str + i));              // с более низким приоритетом и записываем их в строку.
        }                                                   // После этого записываем текущий знак в стек.
        i++;
    }
    while (*node != NULL)                                   // Возможна такая ситуация, что в стеке остаются элементы,
        *(out + point++) = pop(node);                       // поэтому их нужно записать в строку
    *(out + point) = '\0';
    printf("\nОбратная польская запись: %s\n", out);
    return out;
}

struct stack* push(struct stack** node, char c){            // Функция занесения узла в стек,
    struct stack* s;
    s = (struct stack*)malloc(sizeof(struct stack));
    s -> c = c;
    s -> next = *node;                                      // Установка указателя на следующий элемент на голову стека,
    return s;                                               // тем самым, делая текущий узел головой стека
}

char pop(struct stack** node){                              // Функция удаления узла из стека,
    char c;                                                 // возвращает удаляемое значение
    struct stack* ptr;
    if (!*node) return '\0';                                // Если стек пустой возвращает \0
    ptr = *node;
    c = ptr -> c;                                           // смещение головы стека
    if (ptr -> c == '(' || ptr -> c == '+' || ptr -> c == '-' || ptr -> c == '*' || ptr -> c == '/') {
        *node = ptr -> next;
    }
    else *node = NULL;
    free(ptr);                                              // Удаление узла
    return c;
}

int priority(char c){                                       // Возвращает приоритет операции.
    switch (c){                                             // У умножения и деления наивысший приоритет - 3
        case '*': case '/': return 3;                       // У сложения и вычитания - 2
        case '+': case '-': return 2;                       // У закрывающейся скобки - 1
        case ')': return 1;
        default: return 0;
    }
}

struct tree* add(struct tree* node, char symbol, int number){               // Функция добавления узлов в дерево
    if (!node){                                                             // Если дерево пустое - просто заносим все значения в корень
        if (!(node = (struct tree*)malloc(sizeof(struct tree)))) {
            puts("Ошибка при работе с памятью!");
            return 0;
        }
        node -> num = number;
        node -> sign = symbol;
        node -> left = node -> right = NULL;
        flag = 1;                                                           // Сброс флага для принудительного
        return node;                                                        // занесения в левую ветвь
    }
    if (node -> sign == ' ') {                                              // Если записано число в узле, возвращаем этот узел
        return node;
    }
    if (!node -> right){                                                    // Если в правой ветки нет,
        node -> right = add(node -> right, symbol, number);           // создаем ее и заносим значения туда
        return node;
    }
    if (node -> right){                                                     // Если правая ветка есть и там записан оператор,
        if (node -> right -> sign != ' ') {                                 // то спускаемся к этому оператору
            node -> right = add(node -> right, symbol, number);
        } else {                                                            // Если записано число, то ставим флаг для принудительного
            flag = 0;                                                       // перехода на левую ветку и спускаемся влево
            node -> left = add(node -> left, symbol, number);
        }
    }
    if (node -> right && flag == 0) {                                       // Принудительный спуск влево
        node -> left = add(node -> left, symbol, number);
    }
    return node;
}

int calc(struct tree* node){                                                // Функция, считающая выражения (обход дерева)
    if (node){
        if (node -> left) {
            node -> num = calc(node -> left);                         // Спускаемся до конца влево
        }
        if (node -> right) {
            switch (node -> sign) {                                         // Смотрим, что за знак в текущем узле
                case '+':                                                   // и в зависимости от знака делаем
                    node -> num += calc(node -> right);               // операцию с числом из правой ветки
                    break;
                case '-':
                    node -> num -= calc(node -> right);
                    break;
                case '*':
                    node -> num *= calc(node -> right);
                    break;
                case '/':
                    node -> num /= calc(node -> right);
                    break;
            }
        }
    }
    return node -> num;
}

void showTree(struct tree* node, int depth){                                // Функция - вывод дерева
    if (node) {                                                             // Пока node не пустой, идем вправо
        showTree(node->right, depth + 1);
    }
    for (int i = 0; i < depth; i++) {                                       // Поскольку дерево лежит на боку,
        printf("      ");                                                   // то depth сдвигает узел-потомок
    }                                                                       // на несколько уровней вправо
    if (node){
        if (node -> sign == '+' || node -> sign == '*' || node -> sign == '-' || node -> sign == '/'){
            printf("%c\n", node -> sign);
        } else if (node -> num != 0){                                       // Если в узле знак - выводим знак
            printf("%d\n", node -> num);                                    // Если в узле число - выводим число
        }
    } else {                                                                // Если узел пуст - выводим решетку
        printf("#\n");
    }
    if (node){                                                              // Заходим до конца влево
        showTree(node -> left, depth + 1);
    }                                                                       // Поскольку дерево лежит на боку,
}                                                                           // то логично, что первым будет самый правый элемент,
                                                                            // а самым последним - самый левый
int checkBrackets(char *string){
    int bool = 0;                                                           // Проверка скобок
    for (int i = 0; i < strlen(string); ++i) {                           // Если при проходе по строке
        if (string[i] == '('){                                              // в какой-то момент bool станет < 0
            bool++;                                                         // то функция выведет ложь
        } else if (string[i] == ')'){                                       // Если же функция закончит проход по строке
            bool--;                                                         // а bool не равен нулю то это тоже ложь
        }                                                                   // Очевидно, что если bool == 0, то функция
        if (bool < 0){                                                      // выведет истину
            return bool;
        }
    }
    return bool;
}

int isCorrect(char* string){                                                // Функция проверяет расстановку операторов и чисел в строке
    if (string[0] == '*' || string[0] == '/'){
        printf("Выражение не может начинаться с оператора умножения или деления\n");
        return 0;                                                           // В арифметическом выражении первыми
    }                                                                       // операторы / и * не могут быть первыми
    for (int i = 1; i < strlen(string); ++i) {
        char c = string[i - 1];
        if (c == '(' || c == '+' || c == '-' || c == '*' || c == '/'){      // Проверка на расстановку
            while (i < strlen(string) && string[i] == ' ') i++;          // (следует ли за оператором еще один оператор)
            if ((string[i] < '0' || string[i] > '9') && string[i] != '\0' && string[i] != '('){
                printf("После оператора не может идти еще один оператор\n");
                return 0;
            }
        }
    }
    return 1;
}

int main(){
    struct tree* node = NULL;
    struct stack* elem = NULL;
    char* str;
    system("clear");                                                // Очистка консольного экрана
    int i, number;
    if (!(str = (char*)malloc(50))) {
        puts("Ошибка при работе с памятью!");
        return 0;
    }
    puts("Введите выражение");
    fflush(stdin);
    fgets(str, 100, stdin);
    if (!isCorrect(str)){                                    // Проверка на расстановку операторов и чисел
        return 1;
    }
    char *exp = (char*) malloc (200 * sizeof(char));
    strcpy(exp, str);
    exp[strlen(exp) - 1] = '\0';
    if (checkBrackets(exp) != 0){                            // Проверка скобок
        printf("Ошибка при расставлении скобок\n");
        return 1;
    }
    str = polish(str, &elem);                                // Обратная польская запись
    i = (int) strlen(str);
    i--;
    while (i >= 0){
        if (*(str + i) == '/' || *(str + i) == '*' || *(str + i) == '-' || *(str + i) == '+'){ // Если знак записываем в дерево
            node = add(node, *(str + i), 0);
            i--;
        }
        if (*(str + i) == ' ') i--;                                // Пропуск пробелов

        if (*(str + i) >= '0' && *(str + i) <= '9')                // Встречаем цифру, идем дальше по строке пока число
        {                                                          // не закончится. Записываем число в дерево
            number = 0; int mn = 1;
            while (*(str + i) >= '0' && *(str + i) <= '9')
            {
                number += (*(str + i) - '0') * mn;
                mn *= 10;
                i--;
            }
            node = add(node, ' ', number);
        }
    }
    printf("\nРешение: %s = %d\n", exp, calc(node));                    // Вывод/подсчет результатов
    printf("\nВывод дерева:\n# - пустые узлы дерева\n");
    showTree(node, 0);
    puts("Хотите продолжить\n yes/any key");                            // Рекурсивное меню
    char *userAnswer = (char*) malloc(10 * sizeof(char));
    fflush(stdin);
    fgets(userAnswer, 100, stdin);
    userAnswer[strlen(userAnswer) - 1] = '\0';
    if (strcmp(userAnswer, "yes") == 0) {
        main();
    }
    system("clear");
    return 0;
}