flex-bison-in-action/analyzers/polynomials/poly_calc/poly_calc.c

#include "poly_calc.h"
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

// Безопасное умножение с проверкой переполнения
int safe_mul(int a, int b) {
    if (a > 0) {
        if (b > 0 && a > INT_MAX / b) return 0; // Переполнение
        if (b < 0 && b < INT_MIN / a) return 0; // Переполнение
    } else if (a < 0) {
        if (b > 0 && a < INT_MIN / b) return 0; // Переполнение
        if (b < 0 && a < INT_MAX / b) return 0; // Переполнение
    }
    return a * b;
}

// Безопасное сложение с проверкой переполнения
int safe_add(int a, int b) {
    if ((b > 0 && a > INT_MAX - b) || (b < 0 && a < INT_MIN - b)) {
        return 0; // Переполнение
    }
    return a + b;
}

// Возведение полинома в целую степень
Polynomial deg_poly(Polynomial *p, int degree) {
    Polynomial result; init_polynomial(&result);
    Polynomial temp = copy_poly(p);
    for (int i = 1; i < degree; i++) {
        Polynomial new_result = mul_polynomials(&temp, p);
        free_polynomial(&temp);
        temp = new_result;
    }
    result = temp;
    return result;
}

// Возвращает копию полинома
Polynomial copy_poly(Polynomial *p) {
    Polynomial result; init_polynomial(&result);
    for (int i = 0; i < p->size; ++i) {
        add_term(&result, p->terms[i].coefficient, p->terms[i].exponent);
    }
    return result;
}

Polynomial mul_polynomials(Polynomial *p1, Polynomial *p2) {
    Polynomial result; init_polynomial(&result);

    for (int i = 0; i < p1->size; ++i) {
        for (int j = 0; j < p2->size; ++j) {
            Term t1 = p1->terms[i];
            Term t2 = p2->terms[j];

            // Безопасное умножение коэффициентов
            int safe_coeff = safe_mul(t1.coefficient, t2.coefficient);
            if (t1.coefficient != 0 && t2.coefficient != 0 && safe_coeff == 0) {
                fprintf(stderr, "Multiplication overflow detected!\n");
                free_polynomial(&result);
                exit(EXIT_FAILURE);
            }

            // Безопасное сложение степеней
            int safe_exp = safe_add(t1.exponent, t2.exponent);
            if (safe_exp == 0 && (t1.exponent != 0 || t2.exponent != 0)) {
                fprintf(stderr, "Exponent addition overflow detected!\n");
                free_polynomial(&result);
                exit(EXIT_FAILURE);
            }

            Term res_t;
            res_t.coefficient = safe_coeff;
            res_t.exponent = safe_exp;

            add_term_and_poly(&result, res_t);
        }
    }

    return result;
}

Polynomial sub_polynomials(Polynomial *p1, Polynomial *p2) {
    for (int i = 0; i < p2->size; ++i) {
        // Безопасное умножение на -1
        if (p2->terms[i].coefficient == INT_MIN) {
            fprintf(stderr, "Overflow when negating coefficient!\n");
            exit(EXIT_FAILURE);
        }
        p2->terms[i].coefficient *= -1;
    }
    return add_polynomials(p1, p2);
}

Polynomial add_polynomials(Polynomial *p1, Polynomial *p2) {
    Polynomial result; init_polynomial(&result);

    for (int i = 0; i < p1->size; ++i) {
        add_term_and_poly(&result, p1->terms[i]);
    }

    for (int i = 0; i < p2->size; ++i) {
        add_term_and_poly(&result, p2->terms[i]);
    }

    return result;
}

void add_term_and_poly(Polynomial *p, Term term) {
    Term* t = exist_incremental(p, term);
    if (t) {
        // Безопасное сложение коэффициентов
        int new_coeff = safe_add(t->coefficient, term.coefficient);
        if (new_coeff == 0 && ((t->coefficient > 0 && term.coefficient > 0) || 
                               (t->coefficient < 0 && term.coefficient < 0))) {
            fprintf(stderr, "Coefficient addition overflow detected!\n");
            exit(EXIT_FAILURE);
        }
        t->coefficient = new_coeff;
    } else {
        add_term(p, term.coefficient, term.exponent);
    }
}

// Остальные функции остаются без изменений
Term* exist_incremental(Polynomial *p, Term term) {
    for (int i = 0; i < p->size; ++i) {
        if (p->terms[i].exponent == term.exponent) {
            return &p->terms[i];
        }
    }
    return NULL;
}

void init_polynomial(Polynomial *p) {
    p->size = 0;
    p->capacity = 4;
    p->terms = (Term *)malloc(p->capacity * sizeof(Term));
    if (!p->terms) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }
}

void add_term(Polynomial *p, int coeff, int exp) {
    if (p->size >= p->capacity) {
        p->capacity *= 2;
        p->terms = (Term *)realloc(p->terms, p->capacity * sizeof(Term));
        if (!p->terms) {
            perror("Memory reallocation failed");
            exit(EXIT_FAILURE);
        }
    }
    
    p->terms[p->size].coefficient = coeff;
    p->terms[p->size].exponent = exp;
    p->size++;
}

void sort_polynomial(Polynomial *p) {
    for (int i = 0; i < p->size - 1; i++) {
        for (int j = 0; j < p->size - i - 1; j++) {
            if (p->terms[j].exponent < p->terms[j + 1].exponent) {
                Term temp = p->terms[j];
                p->terms[j] = p->terms[j + 1];
                p->terms[j + 1] = temp;
            }
        }
    }
}

void free_polynomial(Polynomial *p) {
    free(p->terms);
    p->terms = NULL;
    p->size = 0;
    p->capacity = 0;
}

void print_polynomial(Polynomial *p, char letter) {
    if (p->size == 0) {
        printf("0\n");
        return;
    }
    
    for (int i = 0; i < p->size; i++) {
        Term term = p->terms[i];
        
        if (term.coefficient == 0) continue;

        if (i != 0 || term.coefficient < 0) {
            printf("%c", term.coefficient > 0 ? '+' : '-');
        }
        
        if (abs(term.coefficient) != 1 || term.exponent == 0) {
            printf("%d", abs(term.coefficient));
        } else if (term.coefficient == -1 && term.exponent != 0) {
            printf("-");
        }
        
        if (term.exponent > 0) {
            printf("%c", letter);
            if (term.exponent > 1) {
                printf("^%d", term.exponent);
            }
        }
    }
    printf("\n");
}