From 4db12b8121c0b32df8b8671045013c857beb191f Mon Sep 17 00:00:00 2001 From: biouman Date: Fri, 27 Apr 2001 04:12:25 +0000 Subject: --- Makefile | 4 + exceptions.c | 81 +++++++++++++++++ exceptions.h | 13 +++ hash.c | 196 ++++++++++++++++++++++++++++++++++++++++ hash.h | 45 +++++++++ interface.c | 234 +++++++++++++++++++++++++++++++++++++++++++++++ interface.h | 22 +++++ main.c | 34 +++++++ main.h | 9 ++ numbers.c | 101 +++++++++++++++++++++ numbers.h | 7 ++ pile.c | 291 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ pile.h | 36 ++++++++ polynom.c | 276 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ polynom.h | 37 ++++++++ scalaires.c | 95 +++++++++++++++++++ scalaires.h | 24 +++++ 17 files changed, 1505 insertions(+) create mode 100644 Makefile create mode 100644 exceptions.c create mode 100644 exceptions.h create mode 100644 hash.c create mode 100644 hash.h create mode 100644 interface.c create mode 100644 interface.h create mode 100644 main.c create mode 100644 main.h create mode 100644 numbers.c create mode 100644 numbers.h create mode 100644 pile.c create mode 100644 pile.h create mode 100644 polynom.c create mode 100644 polynom.h create mode 100644 scalaires.c create mode 100644 scalaires.h diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..c188edd --- /dev/null +++ b/Makefile @@ -0,0 +1,4 @@ +all: polynom + +polynom: exceptions.c hash.c interface.c main.c numbers.c pile.c polynom.c scalaires.c + gcc -o polynom exceptions.c hash.c interface.c main.c numbers.c pile.c polynom.c scalaires.c -lm \ No newline at end of file diff --git a/exceptions.c b/exceptions.c new file mode 100644 index 0000000..8333b82 --- /dev/null +++ b/exceptions.c @@ -0,0 +1,81 @@ +/* + * + * Gestionnaire d'exceptions + * + */ + +#include +#include +#include +#ifdef HAVE_CONFIG_H +#include "config.h" +#else +#define _(x) x +#endif +#include "exceptions.h" + +char *contexts[128]; +int clevel = 0; + +char *Estrdup(char *o) +{ + char *r; + + if (o) { + if (!(r = strdup(o))) { + exception(1, _("Out of memory.")); + } + } else { + return NULL; + } + return r; +} + +void *Emalloc(size_t s) +{ + void *r; + + if (s) { + if (!(r = malloc(s))) { + exception(1, _("Out of memory.")); + } + } else { + return NULL; + } + return r; +} + +void pushcontext(char *c) +{ + if (clevel == 128) { + exception(1, _("Too much error contexts during pushcontext().")); + } + contexts[clevel++] = Estrdup(c); +} + +void popcontext(void) +{ + if (clevel == 0) { + exception(1, _("Error context empty, but popcontext() called.")); + } + free(contexts[--clevel]); +} + +void flushcontext(void) +{ + while (clevel) { + popcontext(); + } +} + +void exception(int level, char *msg) +{ + int i; + + fprintf(stderr, "Error detected. Showing context.\n"); + for (i = 0; i < clevel; i++) { + fprintf(stderr, " (%i) - %s\n", i, contexts[i]); + } + fprintf(stderr, " Error description: %s\n", msg); + exit(level); +} diff --git a/exceptions.h b/exceptions.h new file mode 100644 index 0000000..6f6e8c4 --- /dev/null +++ b/exceptions.h @@ -0,0 +1,13 @@ +#ifndef __EXCEPTIONS_H__ +#define __EXCEPTIONS_H__ + +#include + +char *Estrdup(char *); +void *Emalloc(size_t); +void exception(int, char *); +void pushcontext(char *); +void popcontext(void); +void flushcontext(void); + +#endif diff --git a/hash.c b/hash.c new file mode 100644 index 0000000..adbc142 --- /dev/null +++ b/hash.c @@ -0,0 +1,196 @@ +/* + * + * Tables de hachage + * + */ + + + + + +#include +#include +#include +#include "hash.h" +#include "exceptions.h" +#ifdef HAVE_CONFIG_H +#include "config.h" +#else +#define _(x) x +#endif + + +static char *CHAINEHACHAGE = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_"; + +static int FonctionHachage(char *clef) +{ + unsigned int i; + + if (!clef) { + exception(1, _("Internal error into hashing")); + } + + for (i = 0; i < strlen(CHAINEHACHAGE); i++) { + if (clef[0] == CHAINEHACHAGE[i]) { + return (i); + } + } + return strlen(CHAINEHACHAGE); +} + +_Element CreerElement(char *Nom, _TypeVariable Var) +{ + _Element e; + + e.NomVar = Estrdup(Nom); + + e.Variable = Var; + return (e); +} + +static _ListeChaine InserTete(_ListeChaine l, _Element e) +{ + _ListeChaine aux; + unsigned int i; + + aux = (_ListeChaine) Emalloc(sizeof(struct _LstChn)); + aux->Elem.NomVar = (char *) Emalloc(sizeof(char) * (strlen(e.NomVar) + 1)); + + for (i = 0; i <= strlen(e.NomVar); i++) { + aux->Elem.NomVar[i] = e.NomVar[i]; + } + aux->Elem.Variable = e.Variable; + aux->Suivant = l; + return (aux); +} + +static int EgaliteChaine(char *ch1, char *ch2) +{ + unsigned int i; + + if (strlen(ch1) != strlen(ch2)) { + return (0); + } + for (i = 0; i < strlen(ch1); i++) { + if (ch1[i] != ch2[i]) { + return (0); + } + } + return (1); + /* return (1-strcmp(ch1,ch2)); */ +} + +static void Supprimer(_ListeChaine * l, char *Nom) +{ + _ListeChaine l_aux = NULL; + + if ((*l) != NULL) { + if (EgaliteChaine((*l)->Elem.NomVar, Nom)) { + l_aux = *l; + *l = (*l)->Suivant; + free(l_aux->Elem.NomVar); + free(l_aux); + } else { + Supprimer(&((*l)->Suivant), Nom); + } + } +} + +static void Detruit(_ListeChaine * l) +{ + _ListeChaine l_aux = NULL; + + while (*l) { + l_aux = (*l)->Suivant; + free((*l)->Elem.NomVar); + free(*l); + *l = l_aux; + } +} + +char SupprimerDansTab(_TableauVariable * t, char *Nom) +{ + int index = FonctionHachage(Nom); + + if (0 <= index && index <= strlen(CHAINEHACHAGE)) { + Supprimer(&((*t)[index]), Nom); + } else { + return (0); + } + return (1); +} + +char InsererVarDansTab(_TableauVariable * t, _Element e) +{ + int index = FonctionHachage(e.NomVar); + + if (0 <= index && index <= strlen(CHAINEHACHAGE)) { + (*t)[index] = InserTete((*t)[index], e); + } else { + return (0); + } + return (1); +} + +static _TypeVariable NomVarToVarListe(char *Nom, _ListeChaine l, char *trouve) +{ + *trouve = 0; + while (l != NULL) { + if (EgaliteChaine(Nom, (l->Elem).NomVar)) { + *trouve = 1; + return (l->Elem.Variable); + } + l = l->Suivant; + } +#ifdef HAVE_CONFIG_H + return (NULL); +#else + return 0; +#endif +} + +_TypeVariable NomVarToVar(char *Nom, _TableauVariable t, char *trouve) +{ + return (NomVarToVarListe(Nom, t[FonctionHachage(Nom)], trouve)); +} + +void AfficheListe(_ListeChaine l) +{ + while (l != NULL) { + fprintf(stderr, "%s\n", l->Elem.NomVar); + l = l->Suivant; + } +} + +void AfficheTableau(_TableauVariable t) +{ + unsigned int i; + + for (i = 0; i < TAILLECHAINEHACHAGE; i++) { + AfficheListe(t[i]); + } +} + +int Initialise(_TableauVariable * t) +{ + unsigned int i; + + + (*t) = (_TableauVariable) Emalloc(sizeof(_ListeChaine) * (strlen(CHAINEHACHAGE) + 1)); + for (i = 0; i <= strlen(CHAINEHACHAGE); i++) { + (*t)[i] = NULL; + } + return (i); +} + +void DetruitTab(_TableauVariable * t) +{ + int i; + + for (i = 0; i <= strlen(CHAINEHACHAGE); i++) { + Detruit(&((*t)[i])); + } + + free(*t); + *t = NULL; +} diff --git a/hash.h b/hash.h new file mode 100644 index 0000000..a7948a1 --- /dev/null +++ b/hash.h @@ -0,0 +1,45 @@ +#ifndef __HASH_H__ +#define __HASH_H__ + +#define TAILLECHAINEHACHAGE (26*2+1) + +#ifdef HAVE_CONFIG_H +typedef void *_TypeVariable; +#else +typedef int _TypeVariable; +#endif + +typedef struct { + char *NomVar; + _TypeVariable Variable; +} _Element; + +typedef struct _LstChn { + _Element Elem; + struct _LstChn *Suivant; +} *_ListeChaine; + +typedef _ListeChaine *_TableauVariable; + +/* Initialise une table de hachage */ +int Initialise(_TableauVariable * t); + +/* Crée un élement à insérer dans la table de hachage */ +_Element CreerElement(char *Nom, _TypeVariable Var); + +/* Insert un element(Nom de la variable,variable) dans une table de hachage + la fonction renvoit 0 en cas d'erreur */ +char InsererVarDansTab(_TableauVariable * t, _Element e); + +/* Renvoie la variable de la table de hachage qui porte le nom Nom + si la variable n'existe pas trouve est égal à 0 */ +_TypeVariable NomVarToVar(char *Nom, _TableauVariable t, char *trouve); + +/* Supprime la variable de nom Nom + la fonction renvoit 0 en cas d'erreur */ +char SupprimerDansTab(_TableauVariable * t, char *Nom); + +/* Detruit le tableau */ +void DetruitTab(_TableauVariable * t); + +#endif diff --git a/interface.c b/interface.c new file mode 100644 index 0000000..419e624 --- /dev/null +++ b/interface.c @@ -0,0 +1,234 @@ +/* + * + * Interpreteur de ligne de commande + * + */ + +#include +#include +#ifdef HAVE_CONFIG_H +#include "config.h" +#else +#define _(x) x +#endif +#include "interface.h" +#include "exceptions.h" +#include "pile.h" + + + +typedef unsigned char op_t; + +typedef struct operator_t { + op_t op; + int pri, func; +} operator_t; + +op_t pile_operators[PILEOP_MAX]; +int pile_nestedcall[PILECALL_MAX]; + +int pileop_pos = 0, pilecall_pos = 0; + +operator_t operators[] = { + {',', 0, OP_NEST}, + {'+', 2, OP_PLUS}, + {'-', 2, OP_MOINS}, + {'*', 3, OP_MUL}, + {'/', 3, OP_DIV}, + {'%', 3, OP_MOD}, + {'^', 4, OP_EXP}, + {'+' + 128, 5, OP_PLUS_UNARY}, + {'-' + 128, 5, OP_MOINS_UNARY}, + {'=', 1, OP_ASSIGN}, + {'(', 6, OP_FUNC_CALL}, + {'(' + 128, 6, OP_LPAREN}, + {255, -1, -1} +}; + +operator_t get_op(op_t op) +{ + int i; + + for (i = 0; operators[i].op != 255; i++) { + if (operators[i].op == op) + return operators[i]; + } + + return operators[i]; +} + +int get_pri(op_t op) +{ + return get_op(op).pri; +} + +int get_func(op_t op) +{ + return get_op(op).func; +} + +op_t get_last_op(void) +{ + if (pileop_pos) + return pile_operators[pileop_pos - 1]; + else + return -1; +} + +op_t pop_op(void) +{ + if (pileop_pos) + return pile_operators[--pileop_pos]; + return -1; +} + +void push_op(op_t op) +{ + if (pileop_pos != PILEOP_MAX) + pile_operators[pileop_pos++] = op; + else + exception(-1, _("Too many nested operators in expression.\n")); + +} + +int pop_call(void) +{ + if (pilecall_pos) + fprintf(stderr, "Dépilement du dernier appel de fonction: %i\n", + pile_nestedcall[pilecall_pos - 1]); + return pile_nestedcall[--pilecall_pos]; + return -1; +} + +void increment_call(void) +{ + if (pilecall_pos) { + fprintf(stderr, "Incrément du dernier appel de fonction: %i\n", + pile_nestedcall[pilecall_pos - 1]); + if (pile_nestedcall[pilecall_pos - 1] != -1) + pile_nestedcall[pilecall_pos - 1]++; + } +} + +int get_last_call(void) +{ + if (pilecall_pos) + return pile_nestedcall[pilecall_pos - 1]; + return -1; +} + +void push_call(int call) +{ + fprintf(stderr, "Empilement d'un appel de fonction: %i\n", call); + if (pilecall_pos != PILECALL_MAX) + pile_nestedcall[pilecall_pos++] = call; + else + exception(-1, _("Too many nested functions calls in expression.\n")); +} + +char *getword(char *line, char *p) +{ + char o; + + do { + if (*(line) != ' ') { + o = *(p++) = *line; + fprintf(stderr, "getword(): a trouvé le caractère '%c'\n", o); + } + line++; + } while ((*line) && (*line != ')') && (*line != ';') && (get_func(*line) == -1) + && (get_func(o) == -1)); + *p = '\0'; + return line; +} + +int parse_line(char *line) +{ + char buffer[BUFSIZ]; + op_t op; + int got_unary = 128, nbrargs; + + fprintf(stderr, "Analyse de: \"%s\"...\n\n", line); + while (*line) { + line = getword(line, buffer); + fprintf(stderr, "parse_line(): getword a trouvé le mot \"%s\"\n", buffer); + if (get_func(buffer[0]) != -1) { + fprintf(stderr, "Il s'agit d'un opérateur.\n"); + buffer[0] += got_unary; + if (got_unary) { + fprintf(stderr, "Opérateur de type unaire\n"); + } + if (get_pri(buffer[0]) == -1) { + if (got_unary) { + exception(-1, _("Invalid unary operator")); + } else { + exception(-1, _("Invalid binary operator")); + } + } + fprintf(stderr, "Priorité du dernier op: %i, priorité actu: %i\n", + get_pri(get_last_op()), get_pri(buffer[0])); + while (get_pri(get_last_op()) >= get_pri(buffer[0]) + && ((get_last_op() & 127) != '(')) { + fprintf(stderr, + "Il y a un opérateur plus important sur la file.\n"); + act_pile(get_func(pop_op())); + got_unary = 0; + fprintf(stderr, "Priorité du dernier op: %i, priorité actu: %i\n", + get_pri(get_last_op()), get_pri(buffer[0])); + } + fprintf(stderr, "Mise sur la file\n"); + if (buffer[0] == '(') { + push_call(0); + } + if (buffer[0] == ',') { + increment_call(); + } else + push_op(buffer[0]); + got_unary = 128; + } else if ((buffer[0] == ';') || (buffer[0] == ')')) { + fprintf(stderr, "Caractère spécial\n"); + switch (buffer[0]) { + case ';': + fprintf(stderr, "Vidage complet de la file (fin de commande).\n"); + while (pileop_pos) { + op = pop_op(); + if (op == '(') + exception(-1, + _ + ("Parse error: too much left parenthesis")); + act_pile(get_func(op)); + } + break; + case ')': + fprintf(stderr, "Vidage de la file jusqu'à '(' car ')' trouvée.\n"); + while (1) { + if (!pileop_pos) + exception(-1, + _ + ("Parse error: too much right parenthesis")); + op = pop_op(); + if (((op & 127) == '(')) + break; + act_pile(get_func(op)); + } + if (op == '(') { + nbrargs = pop_call(); + push_pile_int(nbrargs); + act_pile(get_func(op)); + } + got_unary = 0; + break; + } + } else if (((buffer[0] >= 'A') && (buffer[0] <= 'Z')) + || ((buffer[0] >= 'a') && (buffer[0] <= 'z')) + || ((buffer[0] >= '0') && (buffer[0] <= '9')) || (buffer[0] == '_')) { + fprintf(stderr, "Symbole.\n"); + push_pile(buffer); + got_unary = 0; + if (!get_last_call()) + increment_call(); + } else if (buffer[0]) { + exception(-1, _("Invalid character")); + } + } +} diff --git a/interface.h b/interface.h new file mode 100644 index 0000000..546eddd --- /dev/null +++ b/interface.h @@ -0,0 +1,22 @@ +#ifndef __INTERFACE_H__ +#define __INTERFACE_H__ + +#define PILEOP_MAX 50 +#define PILECALL_MAX 50 + +enum { + OP_NEST, + OP_PLUS, + OP_MOINS, + OP_EXP, + OP_PLUS_UNARY, + OP_MOINS_UNARY, + OP_DIV, + OP_MOD, + OP_MUL, + OP_ASSIGN, + OP_LPAREN, + OP_FUNC_CALL +}; + +#endif diff --git a/main.c b/main.c new file mode 100644 index 0000000..8f451e4 --- /dev/null +++ b/main.c @@ -0,0 +1,34 @@ +/* + * + * Programme principal + * + */ + +#include "main.h" +#include "hash.h" +#include "interface.h" +#include "polynom.h" +#include "pile.h" +#ifdef HAVE_CONFIG_H +#include "config.h" +#else +#define _(x) x +#endif + +int main(void) +{ + _TableauVariable variables; + char mute; + + Initialise(&variables); + mute = 'x'; /* nom de la variable utilisee pour la saisie des polynomes, a recuperer en argv eventuellt */ + parse_line("P = x^2+x+1;"); + parse_line("P(2);"); + printf("%s\n", affichage_level_1()); + return 0; + + +/* destruction de ts les polynomes stockes dans la table de hh */ +/* appel a la fonction de vidage de pile */ +/* vraiment utile? on quitte le prog, ttes les donnes dynamiques seront detruites ... */ +} diff --git a/main.h b/main.h new file mode 100644 index 0000000..e7a730b --- /dev/null +++ b/main.h @@ -0,0 +1,9 @@ +#ifndef __MAIN_H__ +#define __MAIN_H__ +#include "hash.h" + +extern _TableauVariable variables; +extern char mute; + + +#endif diff --git a/numbers.c b/numbers.c new file mode 100644 index 0000000..9beeb82 --- /dev/null +++ b/numbers.c @@ -0,0 +1,101 @@ +/* + * + * Conversion de chaines en nombres ( entier ou flottant ) + * + */ + + +#include "numbers.h" + + +/* Cette fonction lit un nombre. Elle va chercher absolument à traduire la chaîne passée en argument en un nombre. Si +ce nombre n'est pas valide, alors l'int valid est mis à faux. Cette fonction reconnais les nombres en décimaux, les nombres +en octal préfixés avec 0 et les nombres en hexadécimal préfixés avec 0x. +*/ + +int char_to_number(char *st, int *valid) +{ + int whattype = 0, result = 0; + + *valid = 0; + + if (*st == '0') { + st++; + if (*st == 'x') { + whattype = 1; + st++; + } else if (*st) { + whattype = 2; + } else { + *valid = 1; + return 0; + } + } + + while (*st) { + switch (whattype) { + case 0: + if ((*st < '0') || (*st > '9')) { + return 0; + } + result *= 10; + result += *st - '0'; + break; + case 1: + if (((*st < '0') || (*st > '9')) + && ((*st < 'A') || (*st > 'F')) + && ((*st < 'a') || (*st > 'f'))) { + return 0; + } + result *= 16; + if ((*st >= '0') && (*st <= '9')) { + result += *st - '0'; + } else if ((*st >= 'A') && (*st <= 'F')) { + result += *st - 'A' + 10; + } else { + result += *st - 'a' + 10; + } + break; + case 2: + if ((*st < '0') || (*st > '7')) { + return 0; + } + result *= 8; + result += *st - '0'; + break; + } + st++; + } + + *valid = 1; + return result; +} + + + +double char_to_double(char *st, int *valid) /* cette fonction tente de traduire une chaine en flottant */ +{ + unsigned int dotnum = 0; + unsigned int deci = 1; + double result = 0; + + while (*st) { + if (*st == '.') { + dotnum++; + } else { + if ((*st < '0') || (*st > '9') || (dotnum > 1)) { + *valid = 0; + return 0; + } else { + result *= 10; + result += *st - '0'; + if (dotnum == 1) + deci *= 10; + } + } + result = result / deci; + *valid = 1; + return result; + + } +} diff --git a/numbers.h b/numbers.h new file mode 100644 index 0000000..343ca0e --- /dev/null +++ b/numbers.h @@ -0,0 +1,7 @@ +#ifndef __NUMBERS_H__ +#define __NUMBERS_H__ + +int char_to_number(char *st, int *valid); +double char_to_double(char *st, int *valid); + +#endif diff --git a/pile.c b/pile.c new file mode 100644 index 0000000..294b402 --- /dev/null +++ b/pile.c @@ -0,0 +1,291 @@ +/* + * + * Gestion de la pile des operandes + * + */ + +#include "pile.h" +#include "exceptions.h" +#include "numbers.h" +#include "main.h" +#include "interface.h" +#ifdef HAVE_CONFIG_H +#include "config.h" +#else +#define _(x) x +#endif + +/* FIXME manque procedure vidage de pile en fin de prog */ + +pile_elem pile[PILE_MAX]; +unsigned int pile_ptr = 0; + +void push_pile(char *st) +{ + int valid1, valid2, valid3, valid4; + int i_number; + double d_number; + polynome poly; + char *buf; + + i_number = char_to_number(st, &valid1); + d_number = char_to_double(st, &valid2); + valid3 = is_mute(st); + poly = (polynome) NomVarToVar(st, variables, (char *) valid4); + + if (valid1) { /* il s agit d un entier */ + push_pile_poly(ply_constr(rat_constr(i_number, 1), 0)); + } else if (valid2) { /* il s agit d un flottant */ + push_pile_poly(ply_constr(rat_constr_from_double(d_number), 0)); + } else if (valid3) { /* il s agit de x */ + push_pile_poly(ply_constr(rat_constr(1, 1), 0)); + } else if (valid4) { /* il s agit d une variable */ + push_pile_poly(ply_copy(poly)); + } else { /* il s agit d un nom */ + push_pile_string(Estrdup(st)); + } +} + + +void push_pile_poly(polynome poly) +{ + if (pile_ptr != PILE_MAX) { + pile[pile_ptr].type = T_POLY; + pile[pile_ptr].poly = poly; + pile_ptr++; + } else { + exception(1, _("push_pile_poly: Stack Overflow")); + } + +} + +void push_pile_int(int val) +{ + if (pile_ptr != PILE_MAX) { + pile[pile_ptr].type = T_INT; + pile[pile_ptr].val = val; + pile_ptr++; + } else { + exception(1, _("push_pile_int: Stack Overflow")); + } + +} + +void push_pile_string(char *st) +{ + if (pile_ptr != PILE_MAX) { + pile[pile_ptr].type = T_STRING; + pile[pile_ptr].label = Estrdup(st); + pile_ptr++; + } else { + exception(1, _("push_pile_string: Stack Overflow")); + } + +} + +pile_elem pop_pile(unsigned int count) +{ + char buf[50]; + + if ((int) (pile_ptr - count) >= 0) { + pile_ptr -= count; + } else { + sprintf(buf, _("pop_pile: Can't pop %u elements"), count); + exception(1, buf); + } + return pile[pile_ptr]; +} + +char *affichage_level_1(void) +{ + char *result; + + if (!pile_ptr) { + switch (pile[pile_ptr - 1].type) { + case T_POLY: + result = ply_affichage(pile[pile_ptr - 1].poly); + break; + case T_STRING: + result = pile[pile_ptr - 1].label; + break; + case T_INT: + result = (char *) Emalloc(11 * sizeof(char)); + + sprintf(result, "%10d", pile[pile_ptr - 1].val); + break; + } + } +} + +int is_mute(char *st) +{ /* FIXME: test lowercase / uppercase */ + char buf[2]; + + sprintf(buf, "%c", mute); + return strcmp(st, buf); +} + + +void act_pile(int func) +{ + pile_elem operande1, operande2; + char buf[50]; + + sprintf(buf, _("Calling act_pile(%i)\n"), func); + pushcontext(buf); + switch (func) { + case OP_PLUS: + operande1 = pop_pile(1); + operande2 = pop_pile(1); + if ((operande1.type == T_POLY) && (operande2.type == T_POLY)) { + push_pile_poly(ply_addition(operande1.poly, operande2.poly)); + if (operande1.poly) + ply_destruct(operande1.poly); + if (operande2.poly) + ply_destruct(operande2.poly); + } else { + exception(1, _("act_pile: OP_PLUS invalid arguments")); + } + break; + case OP_MOINS: + operande1 = pop_pile(1); + operande2 = pop_pile(1); + if ((operande1.type == T_POLY) && (operande2.type == T_POLY)) { + push_pile_poly(ply_soustraction(operande1.poly, operande2.poly)); + if (operande1.poly) + ply_destruct(operande1.poly); + if (operande2.poly) + ply_destruct(operande2.poly); + } else { + exception(1, _("act_pile: OP_MOINS invalid arguments")); + } + break; + case OP_MUL: + operande1 = pop_pile(1); + operande2 = pop_pile(1); + if ((operande1.type == T_POLY) && (operande2.type == T_POLY)) { + push_pile_poly(ply_multiplication(operande1.poly, operande2.poly)); + if (operande1.poly) + ply_destruct(operande1.poly); + if (operande2.poly) + ply_destruct(operande2.poly); + } else { + exception(1, _("act_pile: OP_MUL invalid arguments")); + } + break; + case OP_DIV: + operande1 = pop_pile(1); + operande2 = pop_pile(1); + if ((operande1.type == T_POLY) && (operande2.type == T_POLY)) { + push_pile_poly(ply_division(operande1.poly, operande2.poly)); + if (operande1.poly) + ply_destruct(operande1.poly); + if (operande2.poly) + ply_destruct(operande2.poly); + } else { + exception(1, _("act_pile: OP_DIV invalid arguments")); + } + break; + case OP_MOD: + operande1 = pop_pile(1); + operande2 = pop_pile(1); + if ((operande1.type == T_POLY) && (operande2.type == T_POLY)) { + push_pile_poly(ply_modulo(operande1.poly, operande2.poly)); + if (operande1.poly) + ply_destruct(operande1.poly); + if (operande2.poly) + ply_destruct(operande2.poly); + } else { + exception(1, _("act_pile: OP_MOD invalid arguments")); + } + break; + case OP_EXP: + operande1 = pop_pile(1); + operande2 = pop_pile(1); + if ((operande1.type == T_POLY) && (operande2.type == T_POLY)) { + if (operande2.poly) { + if ((operande2.poly->coef.denom == 1) + && (operande2.poly->coef.num >= 0)) { + push_pile_poly(ply_exposant + (operande1.poly, operande2.poly->coef.num)); + if (operande1.poly) + ply_destruct(operande1.poly); + ply_destruct(operande2.poly); + } else { + exception(1, _("act_pile: OP_EXP invalid arguments")); + } + } else { + exception(1, _("act_pile: OP_EXP invalid arguments")); + } + } else { + exception(1, _("act_pile: OP_EXP invalid arguments")); + } + break; + case OP_ASSIGN: /* FIXME: sens de l evaluation ? poly label sto ou label poly sto */ + operande1 = pop_pile(1); + operande2 = pop_pile(1); + if ((operande1.type == T_POLY) && (operande2.type == T_STRING)) { + if (operande2.label) { + InsererVarDansTab(&variables, + CreerElement(operande2.label, + (void *) operande1.poly)); + if (operande1.poly) + ply_destruct(operande1.poly); + free(operande2.label); + } else { + exception(1, _("act_pile: OP_ASSIGN empty string")); + } + } else { + exception(1, _("act_pile: OP_ASSIGN invalid arguments")); + } + break; + case OP_PLUS_UNARY: + break; + case OP_MOINS_UNARY: + operande1 = pop_pile(1); + if (operande1.type == T_POLY) { + push_pile_poly(ply_soustraction + (ply_constr(rat_constr_zero(), 0), operande1.poly)); + if (operande1.poly) + ply_destruct(operande1.poly); + } else { + exception(1, _("act_pile: OP_MOINS_UNARY invalid argument")); + } + break; + case OP_FUNC_CALL: + operande1 = pop_pile(1); + if ((operande1.type == T_INT) && (operande1.val == 1)) { + operande1 = pop_pile(1); + operande2 = pop_pile(1); + if ((operande1.type == T_POLY) && (operande2.type == T_POLY)) { + if (operande2.poly) { + if (operande2.poly->degre == 0) { + push_pile_poly(ply_constr + (rat_constr_from_double + (ply_valuation + (operande1.poly, + rat_to_double(operande2.poly-> + coef))), 1)); + if (operande1.poly) + ply_destruct(operande1.poly); + ply_destruct(operande2.poly); + } else { + exception(1, + _ + ("act_pile: OP_FUNC_CALL invalid arguments")); + } + } else { + exception(1, _("act_pile: OP_FUNC_CALL invalid arguments")); + } + } else { + exception(1, _("act_pile: OP_FUNC_CALL invalid arguments")); + } + } else { + exception(1, _("act_pile: OP_FUNC_CALL incorrect argument number")); + } + break; + default: + exception(1, _("act_pile: Unknown operator")); + } + popcontext(); +} diff --git a/pile.h b/pile.h new file mode 100644 index 0000000..02ad149 --- /dev/null +++ b/pile.h @@ -0,0 +1,36 @@ +#ifndef __PILE_H__ +#define __PILE_H__ +#include "polynom.h" + +#define PILE_MAX 100 + +typedef enum type_elem { + T_POLY, + T_STRING, + T_INT +} type_elem; + +typedef struct pile_elem { + type_elem type; + polynome poly; + char *label; + int val; +} pile_elem; + +void push_pile(char *st); + +void push_pile_poly(polynome poly); + +void push_pile_int(int val); + +void push_pile_string(char *st); + +pile_elem pop_pile(unsigned int count); + +char *affichage_level_1(void); + +int is_mute(char *st); + +void act_pile(int func); + +#endif diff --git a/polynom.c b/polynom.c new file mode 100644 index 0000000..33834ef --- /dev/null +++ b/polynom.c @@ -0,0 +1,276 @@ +/* + * + * Operations sur les polynomes + * + */ + +#include "polynom.h" +#include "scalaires.h" +#include "exceptions.h" +#include "main.h" +#include +#include +#ifdef HAVE_CONFIG_H +#include "config.h" +#else +#define _(x) x +#endif + +/* FIXME: manque div et mod et poly_to_string */ + +polynome ply_constr(rationnel coef, int degre) +{ /* constructeur monome */ + polynome temp; + + if (!coef.num) + return NULL; + + temp = (monome *) Emalloc(sizeof(monome)); + + temp->coef = coef; + temp->degre = degre; + temp->suiv = NULL; + + return temp; +} + +polynome ply_vide(void) +{ /* cree un polynome */ + + return NULL; +} + +void ply_destruct(polynome poly) +{ /* destructeur */ + if (poly) { + ply_destruct(poly->suiv); + free(poly); + } +} + + +polynome ply_copy(polynome poly) +{ /* recopie */ + polynome result = NULL, temp, t; + + while (poly) { + t = ply_constr(poly->coef, poly->degre); + if (result) { + temp->suiv = t; + temp = t; + } else { + result = t; + temp = t; + } + poly = poly->suiv; + } + return result; +} + + + + +polynome ply_addition(polynome poly1, polynome poly2) +{ /* addition de deux polynomes */ + polynome resultat = NULL, temp, t; + rationnel newrat; + int degre; + + while (poly1 && poly2) { + if (poly1->degre > poly2->degre) { + t = ply_constr(poly1->coef, poly1->degre); + poly1 = poly1->suiv; + } else if (poly1->degre < poly2->degre) { + t = ply_constr(poly2->coef, poly2->degre); + poly2 = poly2->suiv; + } else { + newrat = rat_addition(poly1->coef, poly2->coef); + degre = poly1->degre; + t = ply_constr(newrat, degre); + poly1 = poly1->suiv; + poly2 = poly2->suiv; + } + if (t) { + if (resultat) { + temp->suiv = t; + temp = t; + } else { + resultat = t; + temp = t; + } + } + } + + while (poly1) { + t = ply_constr(poly1->coef, poly1->degre); + if (resultat) { + temp->suiv = t; + temp = t; + } else { + resultat = t; + temp = t; + } + poly1 = poly1->suiv; + } + + while (poly2) { + t = ply_constr(poly2->coef, poly2->degre); + if (resultat) { + temp->suiv = t; + temp = t; + } else { + resultat = t; + temp = t; + } + poly2 = poly2->suiv; + } + + return resultat; +} + +polynome ply_soustraction(polynome poly1, polynome poly2) +{ /* soustraction de deux polynomes */ + + polynome resultat = NULL, temp, t; + rationnel newrat; + int degre; + + while (poly1 && poly2) { + if (poly1->degre > poly2->degre) { + t = ply_constr(poly1->coef, poly1->degre); + poly1 = poly1->suiv; + } else if (poly1->degre < poly2->degre) { + t = ply_constr(rat_moinsunaire(poly2->coef), poly2->degre); + poly2 = poly2->suiv; + } else { + newrat = rat_soustraction(poly1->coef, poly2->coef); + degre = poly1->degre; + t = ply_constr(newrat, degre); + poly1 = poly1->suiv; + poly2 = poly2->suiv; + } + if (t) { + if (resultat) { + temp->suiv = t; + temp = t; + } else { + resultat = t; + temp = t; + } + } + } + + while (poly1) { + t = ply_constr(poly1->coef, poly1->degre); + if (resultat) { + temp->suiv = t; + temp = t; + } else { + resultat = t; + temp = t; + } + poly1 = poly1->suiv; + } + + while (poly2) { + t = ply_constr(rat_moinsunaire(poly2->coef), poly2->degre); + if (resultat) { + temp->suiv = t; + temp = t; + } else { + resultat = t; + temp = t; + } + poly2 = poly2->suiv; + } + + return resultat; +} + + +polynome ply_multiplication(polynome poly1, polynome poly2) +{ /* multiplication de deux polynomes */ + polynome temp, t, resultat = NULL; + + while (poly1) { + while (poly2) { + t = + ply_constr(rat_multiplication(poly1->coef, poly2->coef), + poly1->degre + poly2->degre); + if (t) { + if (resultat) { + temp->suiv = t; + temp = t; + } else { + resultat = t; + temp = t; + } + } + poly2 = poly2->suiv; + } + poly1 = poly1->suiv; + } + + return resultat; +} + +polynome ply_division(polynome poly1, polynome poly2) +{ /* division de deux polynomes */ + polynome result; + + return result; + + +} + +polynome ply_modulo(polynome poly1, polynome poly2) +{ /* reste de la division de deux polynomes */ + polynome result; + + return result; +} + +polynome ply_exposant(polynome poly, unsigned int exp) +{ /* exponentiation d'un polynome */ + int i; + polynome result, temp; + + if (poly) { + result = ply_constr(rat_constr(1, 1), 0); + for (i = 0; i < exp; i++) { + temp = ply_multiplication(result, poly); + ply_destruct(result); + result = temp; + } + } else { + result = NULL; + } + return result; + +} + +double ply_valuation(polynome poly, double point) +{ /* valuation d'un polynome en un point */ + double result = 0; + + while (poly) { + result += rat_to_double(poly->coef) * pow(point, (double) (poly->degre)); + } + return result; +} + +char *ply_affichage(polynome poly) +{ /* routine d'affichage d'un polynome */ + char buf[512], temp[32]; /* FIXME: pas glop comme routine, malloquer tout ca ? */ + char debut = 1; + + while (poly) { + if (poly->degre != 0) { + sprintf(temp, "%+f*%c^%u", rat_to_double(poly->coef), mute, poly->degre); + } else { + sprintf(temp, "%+f", rat_to_double(poly->coef)); + } + strcat(buf, temp); /* FIXME: gerer le depassement de buf si po malloc */ + return Estrdup(buf); + } +} diff --git a/polynom.h b/polynom.h new file mode 100644 index 0000000..64a9273 --- /dev/null +++ b/polynom.h @@ -0,0 +1,37 @@ +#ifndef __POLYNOM_H__ +#define __POLYNOM_H__ +#include "scalaires.h" + +typedef struct monome { + rationnel coef; + unsigned int degre; + struct monome *suiv; +} monome; + +typedef monome *polynome; + +polynome ply_constr(rationnel coef, int degre); /* constructeur monome */ + +polynome ply_vide(void); /* cree un polynome */ + +void ply_destruct(polynome poly); /* destructeur */ + +polynome ply_copy(polynome poly); /* recopie */ + +polynome ply_addition(polynome poly1, polynome poly2); /* addition de deux polynomes */ + +polynome ply_soustraction(polynome poly1, polynome poly2); /* soustraction de deux polynomes */ + +polynome ply_multiplication(polynome poly1, polynome poly2); /* multiplication de deux polynomes */ + +polynome ply_division(polynome poly1, polynome poly2); /* division de deux polynomes */ + +polynome ply_modulo(polynome poly1, polynome poly2); /* reste de la division de deux polynomes */ + +polynome ply_exposant(polynome poly, unsigned int exp); /* exponentiation d'un polynome */ + +double ply_valuation(polynome poly, double point); /* valuation d'un polynome en un point */ + +char *ply_affichage(polynome poly); /* routine d'affichage d'un polynome */ + +#endif diff --git a/scalaires.c b/scalaires.c new file mode 100644 index 0000000..71a106d --- /dev/null +++ b/scalaires.c @@ -0,0 +1,95 @@ +/* + * + * Operations sur les scalaires ( rationnels ) + * + */ + +#include "scalaires.h" +#include + +#define PRECISION 1E6 +static int pgcd(int a, int b) +{ + if (!a) + return b; + if (a < b) + return pgcd(b, a); + return pgcd(b, a % b); +} + +rationnel rat_constr_zero(void) +{ /* renvoie 0 */ + rationnel temp; + + temp.num = 0; + temp.denom = 1; + return temp; +} + + +rationnel rat_constr(int num, int denom) +{ /* cree une fraction */ + rationnel temp; + + if (denom < 0) { + denom = -denom; + num = -num; + } + + temp.num = num / pgcd(num, denom); + temp.denom = denom / pgcd(num, denom); + return temp; + +} + +rationnel rat_constr_from_double(double flt) +{ /* cree une fraction a partir d un double */ + + return rat_constr(floor(flt * PRECISION), PRECISION); + + +} + +void rat_destruct(rationnel rat) +{ /* destructeur */ + +} + +double rat_to_double(rationnel rat) +{ /* obtention du double correspondant a un rationnel */ + return ((double) rat.num / (double) rat.denom); +} + +rationnel rat_addition(rationnel rat1, rationnel rat2) +{ /* addition */ + + return rat_constr(rat1.num * rat2.denom + rat2.num * rat1.denom, rat1.denom * rat2.denom); + +} + +rationnel rat_soustraction(rationnel rat1, rationnel rat2) +{ /* soustraction */ + + return rat_constr(rat1.num * rat2.denom - rat2.num * rat1.denom, rat1.denom * rat2.denom); + +} + +rationnel rat_moinsunaire(rationnel rat1) +{ /* moins unaire */ + + return rat_constr(-rat1.num, rat1.denom); + +} + +rationnel rat_multiplication(rationnel rat1, rationnel rat2) +{ /* multiplication */ + + return rat_constr(rat1.num * rat2.num, rat1.denom * rat2.denom); + +} + +rationnel rat_division(rationnel rat1, rationnel rat2) +{ /* division */ + + return rat_constr(rat1.num * rat2.denom, rat1.denom * rat2.num); +} diff --git a/scalaires.h b/scalaires.h new file mode 100644 index 0000000..a13b96a --- /dev/null +++ b/scalaires.h @@ -0,0 +1,24 @@ +#ifndef __SCALAIRES_H__ +#define __SCALAIRES_H__ + +typedef struct { + int num; + unsigned int denom; +} rationnel; + +rationnel rat_constr_zero(void); /* renvoie 0 */ + + +rationnel rat_constr(int num, int denom); /* cree une fraction */ + +rationnel rat_constr_from_double(double flt); /* cree une fraction a partir d un double */ + +void rat_destruct(rationnel rat); /* destructeur */ +double rat_to_double(rationnel rat); /* obtention du double correspondant a un rationnel */ +rationnel rat_addition(rationnel rat1, rationnel rat2); /* addition */ +rationnel rat_soustraction(rationnel rat1, rationnel rat2); /* soustraction */ +rationnel rat_moinsunaire(rationnel rat1); /* moins unaire */ +rationnel rat_multiplication(rationnel rat1, rationnel rat2); /* multiplication */ +rationnel rat_division(rationnel rat, rationnel rat2); /* division */ + +#endif -- cgit v1.2.3