Sujet Précédent Sujet Suivant

Langage C et expression arithmétique

Fermé
XRev - 9 oct. 2010 à 18:51
Vicking54 Messages postés 89 Date d'inscription lundi 11 octobre 2010 Statut Membre Dernière intervention 17 mai 2011 - 11 oct. 2010 à 19:30
Bonjour,

Je suis à la conquête d'un projet en langage C dans lequel je dois transformer une expression arithmétique exprimée en notation infixée, en une notation préfixée.

Ainsi (a+b)*(c+d) se transforme en *+ab+cd
Pour cela il faut utiliser les arbres binaires.

J'ai bien passé deux heures là dessus, désormais j'ai compris le sujet, cependant je bloque sur la conception. Je manque de notion en C (je débute).


Exemple de ce que j'imagine
----

Si j'entre dans mon terminal :

combien de valeur dans l'expression = 3 /* il va donc me demander trois valeur a,b,c) */
valeur de a = 2
valeur de b = 6
valeur de c = 2

que souhaitez vous faire : (a+b)*c /* ca pourrait être bien d'autres forme... */

Ainsi (a+b)*c se transforme en * c + a b ...
Soit (2+6)*2 se transforme en * 2 + 2 6

----

Enfin je suis pas sûr de ma démarche vis à vis du sujet, et d'autre part je ne sais pas comment m'y prendre... u_u

Merci de votre lecture, j'attends avec impatience vos réponses !

Cordialement,

M. XR


A voir également:

5 réponses

Réponse 1 / 5
Xrev
11 oct. 2010 à 13:30
Merci à KX et ydurce pour l'initiation, voir même le developpement de l'idée. Je ne m'était pas rendu compte de la complexité de la tâche. Oui il s'agit bien entendu de le réaliser en C.

Je posterais d'autre commentaire si j'en ai l'occasion sur ce que vous m'avez dit. Mais avant tout je tenais à vous remercier pour la rapidité de vos réponses. (je suis en cours)

Donc je m'y attarderais en soirée !

Bonne journée à vous !
1
Réponse 2 / 5
KX Messages postés 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 3 019
Modifié par KX le 9/10/2010 à 20:03
Salut !

Comme ça je dirai qu'un arbre binaire permet facilement de résoudre le problème :
Les opérateurs seront sur les noeuds
Les opérandes seront sur les feuilles.
Les expressions entre parenthèses donneront des sous arbres (remarque : les parenthèses sont inutiles en notation préfixée)

Ici tu sembles te limiter au cas simple où tous tes opérateurs sont binaires, mais si tu voulais avoir des opérateurs unaires tu aurais ta feuille de droite vide, et pour des opérateurs n-aires bonne chance ;-)

Une fois l'arbre construit, il suffit de le lire en ordre préfixe (opérateur, opérande ou sous-arbre de gauche, puis opérande ou sous-arbre de droit) et le tour est joué.

Il te faudra bien sûr avoir une méthode d'analyse de ta formule pour identifier où sont les opérateurs, les opérandes, et les parenthèses (attention à bien distinguer les parenthèses ouvrantes et fermantes).

Le plus simple est surement de te limiter à des opérateurs atomiques comme + - * / ( ) et de les analyser dans un tableau de caractères avec la propriété suivante : si un caractère n'est pas un opérateur alors il constitue une opérande.

Le parenthésage va te poser beaucoup de problèmes de même que la priorité des opérateurs (exemple a*b+c donne + * a b c et non * a + b c)
J'espère que tu connais la récursivité car tu ne t'en sortiras pas sans !

Je pense que tu as compris maintenant qu'il te faudra plus de 2 heures pour terminer, alors persévère, et bonne continuation !
La confiance n'exclut pas le contrôle
0
Réponse 3 / 5
ydurce Messages postés 78 Date d'inscription samedi 9 octobre 2010 Statut Membre Dernière intervention 12 décembre 2010 18
10 oct. 2010 à 02:15
une solution (simplifiée) à améliorer bien sur!

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

typedef struct
{
int chiffre_gauche;
int chiffre_droite;
void *Gauche;
void *Droite;
char Op[2];
int A_gauche;
} type_expression;

void PrintArbre(type_expression *Ptr);
type_expression *Sweep(int *Ind, char Chaine[]);

int _tmain(int argc, _TCHAR* argv[])
{
char Chaine[128];
type_expression *Arbre;
printf("entrer l'expression\n");
scanf("%s",Chaine);
int Ind=0;
Arbre=Sweep(&Ind,Chaine);
PrintArbre(Arbre);
scanf("%s",Chaine);
return 0;
}





void PrintArbre(type_expression *Ptr)
{
printf(Ptr->Op);
if(Ptr->Gauche!=NULL) PrintArbre((type_expression *)Ptr->Gauche);
else printf("%d",Ptr->chiffre_gauche);
if(Ptr->Droite!=NULL) PrintArbre((type_expression *)Ptr->Droite);
else printf("%d",Ptr->chiffre_droite);
}

type_expression *Sweep(int *Ind, char Chaine[])
{
type_expression *New;
New=new type_expression; //malloc(sizeof(type_expression)); en C
New->Gauche=New->Droite=NULL;
New->chiffre_gauche=New->chiffre_droite=0;
New->A_gauche=0;
while(1)
{
switch(Chaine[(*Ind)++])
{
case '(':
if(New->Gauche==NULL && New->A_gauche==0) New->Gauche=Sweep(Ind,Chaine);
else New->Droite=Sweep(Ind,Chaine);
break;
case ')':
case '\n':
case '\0':
return New;
break;
case '+':
case '-':
case '*':
case '/':
New->Op[0]=Chaine[*Ind-1];New->Op[1]='\0';
break;
default:
if(Chaine[*Ind-1]>=0x30 && Chaine[*Ind-1]<=0x39)
{
if(New->Gauche==NULL && New->A_gauche==0) {New->chiffre_gauche=Chaine[*Ind-1]-0x30;New->A_gauche=-1;}
else {New->chiffre_droite=Chaine[*Ind-1]-0x30;}
}
break;
}
}
}
0
KX Messages postés 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 3 019
10 oct. 2010 à 13:15
Je n'ai pas regardé ton code en détail ydurce, mais je l'ai testé.
Comme tu l'as dit c'est une solution simplifiée, voici donc pour XRev les points à améliorer :

1) Utiliser des opérandes de plusieurs caractères. Exemple : "12+5"
2) Utiliser plusieurs opérateurs dans la même parenthèse. Exemple : "(1+2+3)+4"
3) Gérer les cas particuliers de parenthésage. Exemple : "(1+2)"
4) Ne pas se limiter aux améliorations 1 à 3 !

Sinon concernant ton code ydurce, il m'apparaît évident que l'utilisation d'un langage objet (C++ par exemple) est plus appropriée, même si la question de XRev portait effectivement sur le langage C.

PS. Pour mettre du code dans un poste utilisez les balises code faites pour ça.
0
Réponse 4 / 5
ydurce Messages postés 78 Date d'inscription samedi 9 octobre 2010 Statut Membre Dernière intervention 12 décembre 2010 18
10 oct. 2010 à 15:09
tout à fait d'accord avec toi pour le C++, KX.
laissons quand même un peu de travail à notre ami XRev qui, pour améliorer le code, devra l'analyser un peu !
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Réponse 5 / 5
Viking54
11 oct. 2010 à 16:19
je te donne la structure de donné d'un arbre syntaxique avec les primitives d'accès

Le .h : 

#ifndef _PRIMITIVEARBRESYNT_
#define _PRIMITIVEARBRESYNT_

typedef enum {Constante , Variable , Binaire , Fonction} TNature;
typedef struct NoeudSynt    {    TNature Nature ;
                                double ValConst;
                                char OpOuFonct;
                                struct NoeudSynt *fg;
                                struct NoeudSynt *fd;
                            } TNoeudSynt , *TArbreSynt;
                            


// Primitive sur les Arbres Syntaxique

// Création

extern TArbreSynt CreerArbreSyntVide ();
extern TArbreSynt CreerVariable ();
extern TArbreSynt CreerConstante (double Val);
extern TArbreSynt CreerOperateurBinaire (char OpFonct, TArbreSynt fg , TArbreSynt fd);
extern TArbreSynt CreerFonction (char OpFonct, TArbreSynt fg);

// Consultation

extern bool EstArbreSyntVide (TArbreSynt a);
extern TArbreSynt FG(TArbreSynt a);
extern TArbreSynt FD(TArbreSynt a);
extern TNature Nature (TArbreSynt a);
extern double ValConst (TArbreSynt a);
extern char OpOuFonct (TArbreSynt a);

// Modification

extern void    ModifFD(TArbreSynt a, TArbreSynt fd);
extern void ModifFG(TArbreSynt a, TArbreSynt fg);
extern void ModifNature(TArbreSynt a, TNature Nature);
extern void ModifValConst(TArbreSynt a, double Val);
extern void ModifOpOuFonct(TArbreSynt a, char OpFonct);

// Destruction

extern void Libérer(TArbreSynt a);

#endif


Le .cpp 

// Primitive sur les Arbres Syntaxique

// Création

TArbreSynt CreerArbreSyntVide ()
{
    return NULL;
}

TArbreSynt CreerVariable ()
{
    TArbreSynt NvM = (TArbreSynt) malloc (sizeof (TNoeudSynt));
    NvM->Nature = Variable;
    return NvM;
}

TArbreSynt CreerConstante (double Val)
{
    TArbreSynt NvM = (TArbreSynt) malloc (sizeof (TNoeudSynt));
    NvM->Nature = Constante;
    NvM->ValConst = Val;
    return NvM;
}

TArbreSynt CreerOperateurBinaire (char OpFonct, TArbreSynt fg , TArbreSynt fd)
{
    TArbreSynt NvM = (TArbreSynt) malloc (sizeof (TNoeudSynt));
    NvM->Nature = Operateur_Binaire;
    NvM->OpOuFonct = OpFonct;
    NvM->fg = fg;
    NvM->fd = fd;
    return NvM;
}

TArbreSynt CreerFonction (char OpFonct, TArbreSynt fg)
{
    TArbreSynt NvM = (TArbreSynt) malloc (sizeof (TNoeudSynt));
    NvM->Nature = Fonction;
    NvM->OpOuFonct = OpFonct;
    NvM->fg = fg;
    return NvM;
}

// Consultation

bool EstArbreSyntVide (TArbreSynt a)
{
    if(a == NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}

TArbreSynt FG(TArbreSynt a)
{
    return a->fg;
}

TArbreSynt FD(TArbreSynt a)
{
    return a->fd;
}

TNature Nature (TArbreSynt a)
{
    return a->Nature;
}

double ValConst (TArbreSynt a)
{
    return a->ValConst;
}

char OpOuFonct (TArbreSynt a)
{
    return a->OpOuFonct;
}

// Modification

void    ModifFD(TArbreSynt a, TArbreSynt fd)
{
    a->fd = fd
}

void     ModifFG(TArbreSynt a, TArbreSynt fg)
{
    a->fg = fg;
}

void     ModifNature(TArbreSynt a, TNature Nature)
{
    a->Nature = Nature;
}

void     ModifValConst(TArbreSynt a, double Val)
{
    a->ValConst = Val;
}

void     ModifOpOuFonct(TArbreSynt a, char OpFonct)
{
    a->OpOuFonct = OpFonct;
}

// Destruction

void Libérer(TArbreSynt a)
{
    if (!EstVide(a))
    {
        Libérer(FG(a))
        Libérer(FD(a))
        free(a)
    }
}


Avec cela ca te permettra d'avancer

cordialement
0
KX Messages postés 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 3 019
11 oct. 2010 à 18:36
Je vais regarder plus attentivement ta contribution Viking54 mais il me semble à première vue qu'il y ait plusieurs erreurs, en particulier si on considère que le problème est en C !
De plus je pense que la solution, certes incomplète, de ydurce était une base largement suffisante pour résoudre ce problème, même si j'aurai fait encore plus simple !

Personnellement ma structure d'arbre serait tout simplement : 

typedef struct 
{ 
    char *expression; // opérateur si un noeud - opérande si une feuille
    void *gauche; // sous-arbre gauche
    void *droite; // sous-arbre droit
}
arbreSyntaxique;
0
KX Messages postés 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 3 019
11 oct. 2010 à 19:19
Je pense que quelques commentaires seraient mieux pour expliquer ce que tu as fait, pour mieux juger si nécessaire la qualité de ton code. J'ai juste corrigé ton code pour qu'il compile : 

#ifndef _PRIMITIVEARBRESYNT_
#define _PRIMITIVEARBRESYNT_

#include <stdlib.h>

typedef enum
{
	Constante,
	Variable,
	Binaire,
	Fonction
}
TNature;

typedef struct NoeudSynt
{
	TNature Nature;
	double ValConst;
	char OpOuFonct;
	struct NoeudSynt *fg;
	struct NoeudSynt *fd;
}
TNoeudSynt, *TArbreSynt;
                 
// Primitives sur les Arbres Syntaxiques

// Création

TArbreSynt CreerArbreSyntVide()
{
    return NULL;
}

TArbreSynt CreerVariable()
{
    TArbreSynt NvM = (TArbreSynt) malloc(sizeof (TNoeudSynt));
    NvM->Nature = Variable;
    return NvM;
}

TArbreSynt CreerConstante(double Val)
{
    TArbreSynt NvM = (TArbreSynt) malloc(sizeof (TNoeudSynt));
    NvM->Nature = Constante;
    NvM->ValConst = Val;
    return NvM;
}

TArbreSynt CreerOperateurBinaire(char OpFonct, TArbreSynt fg, TArbreSynt fd)
{
    TArbreSynt NvM = (TArbreSynt) malloc(sizeof (TNoeudSynt));
    NvM->Nature = Binaire;
    NvM->OpOuFonct = OpFonct;
    NvM->fg = fg;
    NvM->fd = fd;
    return NvM;
}

TArbreSynt CreerFonction(char OpFonct, TArbreSynt fg)
{
    TArbreSynt NvM = (TArbreSynt) malloc(sizeof (TNoeudSynt));
    NvM->Nature = Fonction;
    NvM->OpOuFonct = OpFonct;
    NvM->fg = fg;
    return NvM;
}

// Consultation

int EstArbreSyntVide(TArbreSynt a)
{
	return (a == NULL);
}

TArbreSynt FG(TArbreSynt a)
{
    return a->fg;
}

TArbreSynt FD(TArbreSynt a)
{
    return a->fd;
}

TNature Nature(TArbreSynt a)
{
    return a->Nature;
}

double ValConst(TArbreSynt a)
{
    return a->ValConst;
}

char OpOuFonct(TArbreSynt a)
{
    return a->OpOuFonct;
}

// Modification

void ModifFD(TArbreSynt a, TArbreSynt fd)
{
    a->fd = fd;
}

void ModifFG(TArbreSynt a, TArbreSynt fg)
{
    a->fg = fg;
}

void ModifNature(TArbreSynt a, TNature Nature)
{
    a->Nature = Nature;
}

void ModifValConst(TArbreSynt a, double Val)
{
    a->ValConst = Val;
}

void ModifOpOuFonct(TArbreSynt a, char OpFonct)
{
    a->OpOuFonct = OpFonct;
}

// Destruction

void Liberer(TArbreSynt a)
{
    if (!EstArbreSyntVide(a))
    {
        Liberer(FG(a));
        Liberer(FD(a));
        free(a);
    }
}

#endif
0
Vicking54 Messages postés 89 Date d'inscription lundi 11 octobre 2010 Statut Membre Dernière intervention 17 mai 2011 26
11 oct. 2010 à 19:19
Dans ma contribution se sont les primitives d'accès d'un arbre syntaxique avec une structure assez complète elle est testé et fonctionne parfaitement c'est bien en C qu'elle est écrite
0
Vicking54 Messages postés 89 Date d'inscription lundi 11 octobre 2010 Statut Membre Dernière intervention 17 mai 2011 26
11 oct. 2010 à 19:20
erf ben je refais cela
0
KX Messages postés 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 3 019
11 oct. 2010 à 19:24
Elle ne pouvait pas fonctionner en C, regarde Libérer, déjà un nom de fonction avec un accent c'est incorrect et puis il manquait des ";"
De plus en C, les fichiers .cpp ne sont pas reconnus, de même que bool, true, ou false !
Et puis les extern, je n'ai pas trop compris à quoi ils servaient... Je trouve ça plus clair de tout mettre au même endroit !
0

Discussions similaires

Que veut dire "Susu" ?
Merciiiix) -
Hakuna Matata -

2 réponses
Extraire le contenu de plusieurs fichiers
politicus -
Syl_tls1 -

11 réponses
définition de ping
mac_mic -
alb -

18 réponses
que signifie les petits rectangles blancs à la fin de mes sms ?
krystina1207 -
Arman -

6 réponses
Ça veut dire quoi tu es un amour ?
TheEnglishBoyzAreHereGuyz -
Utilisateur anonyme -

2 réponses