Salut tout le monde ,
je vous demande de m'expliquer comment faire pour représenter une expression arithmétique du genre ((5*2)+8) par exemple sous forme d'un arbre binaire , en fait je voudrai écrire une fonction qui reçoit une expression arithmétique en paramètres( une chaîne de char )et qui renvoie l'arbre binaire correspondant . j'espère que j'ai été clair

Bon, suis allé m'instruire sur wikipédia pour savoir ce qu'était un arbre binaire, j'espère avoir compris.

En clair, tu veux traduire :

(5*2)+8

Par :

_____________________

          +

       *     8

     5   2
_____________________

Un truc de ce genre non ?
Va falloir parser ta chaine de caractères donc, et utiliser une belle et douce PILE dans laquelle tu place un par un les caractères spéciaux (parenthèses, crochets), et tu dépiles pour savoir dans quel niveau de parenthèse tu te trouves (plus tu rencontres de parentheses ouvrantes, plus ca veut dire que tu es bas dans l'arbre). A méditer, tiens, je vais essayer de faire ton projet, ca m'a l'air tres intéressant, je te dirai au fur et à mesure...

Pour ce qui est de l'arbre lui même, une liste chainée fera l'affaire, avec l'accès au noeud suivant mais aussi à deux filles.


Notions à chercher donc :

- pile
- liste chainée

Tiens, je l'ai fait ce TP, il y a déja quelques années a la fac Un classique je pense !

Souvenirs, souvenirs !

oui Fvirtman tu as raison ^^, il s'agit d'un tp .

"oui Fvirtman tu as raison "

Article 1 :
- Fvirtman a toujours raison
Article 2 :
- Si Fvirtman a tort, l'article 1 rentre immédiatement en vigueur.

y'a moyen de faire ce TP sans passer par la pile et les listes chaînées ? mais avec une classe arbre bin avec accès aux sous-arbres !!

Tu peux te servir de la pile des appels des fonctions : autrement dit, si tu es adroit en récursivité, tu peux te débrouiller sans refaire derriere de structures de piles

Ben un arbre avec accès aux sous arbres, ça s'appelle une liste chainée...(enfin, une sorte de)

hum, pas vraiment. Mais bon, c'est un détail.

Disons juste que tu n'es pas obligé de créer une structure de liste, ou une structure de pile explicite pour construire un tel arbre. Une fonction récursive avec des return asticieusement placés peut permettre de se passer de structures de listes par exemple.

Non, la définition récursive d'un arbre c'est pas la même que celle d'une liste, bien que ça ressemble.

Sinon, avec une structure d'arbre binaire, c'est clairement plus simple, c'est plus adapté vu qu'une expression arithmétique est naturellement arborescente... Dès lors, les algorithmes récursifs coulent de source, tu ne fais qu'écrire des équations dans ton code.

Pour avoir pas mal codé des parseurs(bien plus compliqués que cela), je trouve que la méthode la plus clair c'est d'abord de faire une description de la grammaire du langage très détaillée puis de faire une analyse récursive comme l'as dis Fvirtman.
Voilà une idée:

// pour gérer des expression avec +,-,/,*,()
expression_mathméatiques::=expression_plus

expression_plus::=expression_mult
                 |expression_plus '+' expression_mult
                 |expression_plus '-' expression_mult
expression_mult::=expression_simple
                 |expression_mult '*' expression_simple
                 |expression_mult '/' expression_simple
expression_simple::=constante
                 | '(' expression_mathméatiques ')'

C'est vrai que c'est un peu formel mais du coup la récursivité apparait. Il suffit en gros de coder trois fonctions récursives. Après cela dépend énormemmement de ce que tu veux faire:
-juste calculer la valeur
-la stocker dans un arbre
...
Si tu veux du code, je peux en poster pour être plus clair.

Slt Pamaury ,c'est pour stocker dans un arbre oui, sinon pour calculer ,ça j'ai une petite idée sur la méthode...
ehh oui je voudrai bien un petit exemple de code ça m'aidrait vraiment et merci d'avance.

Tu peux également faire ce genre de choses en passant par la notation polonaise inversee (NPI).

expression normale -> NPI -> evaluation de la NPI

La deuxieme partie se fait de manière triviale avec une pile. La premiere est plus complexe si tu comptes utiliser des fonctions à plusieurs variables ou si tu comptes laisser l'utilisateur créer ses propres fonctions.

Dans tous les cas et quelque soit la méthode choisie, c'est un excellent exercice de programmation et d'algorithme. Je n'aurais qu'un conseil: Papier et crayon avant de coder.

Comme le but n'est pas de te donner le code prémaché je vais donner l'algo détaillé pour que tu comprenne l'idée.
La première étape à mon avis de faire une analyse lexical(qui ici est presque triviale): en gros tu code une fonction, disons Lex de ce type:

struct Token
{
   enum Type
   {
      Floatv,// une valeur flottante constante
      Add,Min,Mul,Div,// les opérateurs +,-,*,/
      LParent,RParen,// ()
      Eof,// fin de l'entrée
   };
   Type type;
   float v_float;// la valeur si besoin est
};

Token NextToken();// renvoie le prochain jeton
Token CurToken();// pratique pour éviter d'avoir sans cesse à stocker le retour de NextToken()

L'idée en fait de se débarrasser des inconvénient de la représentation sous forme de chaîne de caractères: les espaces, les retour à la lignes, ... Comme çà on accède directement aux élément lexicaux importants du langage comme les mot-clés ou les opérateurs ou les constantes.
Peut-être que dans ton cas cette fonction prendra un paramètre comme la chaîne de caratcère, ou autre. Moi j'aime bien la mettre dans une classe:

class Lexer
{
   public:
   Lexer(const std::string& expr);
   ~Lexer();
   Token NextToken();
   protected:
   std::string m_expr;
   size_t cur_index;
};

Après il faut la coder bien sûr mais je te laisse en exercice, en gros elle aura cette structure:

Token Lexer::NextToken()
{
   if(is_digit(m_expr[cur_index]))
   {
      // lire et retourner la constante
   }
   else if(m_expr[cur_index]=='+')
   {
      // mettre à jour cur_index et retourner le jeton '+'
   }
   ..
   else if(m_expr[cur_index]==0)
   {
      // retourner eof
   }
   else if(is_space(m_expr[cur_index])
   {
      // soit tu rappèle NextToken() récursivement pour ignoer l'espace soit tu me l'ensemble de ces tests dans une boucle while
   }
   else
      // erreur: élément lexicale non reconnu
}

Ensuite tu code une fonction récursive par élément de grammaire et des classes qui vont avec.
Comme c'es assez fastidieux, je fais l'exemple avec +,* et () et le - unaire
Voilà sa grammaire:

// pour gérer des expression avec +,-,/,*,()
expression_mathméatiques::=expression_plus

expression_plus::=expression_mult
                 |expression_plus '+' expression_mult
expression_mult::=expression_simple
                 |expression_mult '*' expression_simple
expression_simple::=constante
                 | '(' expression_mathméatiques ')'
                 | '-' expression_simple

// une expression générale
class Expression
{
   public:
   Expression();
   virtual ~Expression();
   // tu ajoutes sûrement des méthodes virtuelles pour manipuler l'arbre
   protected:
};
// un opérteur unaire
class UnaryExpression : public Expression
{
   public:
   UnaryExpression(Expression *e);
   virtual ~UnaryExpression();
   protected:
   Expression *e;
};
// une constante
class ValueExpression : public Expression
{
   public:
   ValueExpression(float val);
   virtual ~ValueExpression();
   protected:
   float value;
};
// le moins unaire
class NegExpression : public UnaryExpression 
{
   public:
   NegExpression(Expression *e);
   virtual ~NegExpression();
};
// un opérateur binaire
class BinaryExpression : public Expression
{
   public:
   BinaryExpression(Expression *e1,Expression *e2);
   virtual ~BinaryExpression();
   protected:
   Expression *e1,*e2;
};
// le plus
class AddExpression : public BinaryExpression
{
   public:
   AddExpression(Expression *e1,Expression *e2);
   virtual ~AddExpression();
};
// le multiplier
class MulExpression : public BinaryExpression
{
   public:
   MulExpression(Expression *e1,Expression *e2);
   virtual ~MulExpression();
};

Ensuite tu code l'analyse:

Expression *ParseSimpleExpression()
{
   // dans ce cas on s'attends soit à une constante, soit -une_expression soit (expression)
   switch(CurToken().type)
   {
      case Token::Floatv:
          {
             // on créé l'expression
             Expression *e=new ValueExpression(CurToken().v_float);
             // on saute passe au jeton suivant et on retourne
             NextToken();
             return e;
           }
      case Token::Min:
          NextToken();// on passe le '-'
          // ici c'est un moins unaire: on passe le - et on relance l'analyse
          return new NegExpression(ParseSimpleExpression());
      case Token::LParen:
          {
             // on passe la (
             NextToken();
             // on lit une expression
             Expression *e=ParseExpression();
             // on s'attends à trouver )
             if(CurToken().type!=Token::RParen)
                erreur_parenthèse_pas_bien_mise;
             NextToken();
             return e;
          }
      default:
            erreur_de_syntaxe
   }
}

Expression *ParseMulExpression()
{
   // d'abord on lit une expression contenant des (),...
   Expression *expr=ParseSimpleExpression();
   // puis tant qu'il y a des * on les gère
   while(CurToken().type==Token::Mul)
   {
      // on saute le '*'
      NextToken();
      // on lit une autre expression
      Expression *expr2=ParseSimpleExpression();
      // on les met ensemble
      expr=new MulExpression(expr1,expr2);
   }
   return expr;
}

Expression *ParseAddExpression()
{
   // d'abord on lit une expression contenant des *,(),..
   Expression *expr=ParseMulExpression();
   // puis tant qu'il y a des + on les gère
   while(CurToken().type==Token::Add)
   {
      // on saute le '+'
      NextToken();
      // on lit une autre expression
      Expression *expr2=ParseMulExpression();
      // on les additionne
      expr=new AddExpression(expr1,expr2);
   }
   return expr;
}

Expression *ParseExpression()
{
   return ParseAddExpression();
}

C'est vrai que ce code n'est pas évident à comprendre et c'est vrai que cette méthode d'analyse est un peu lourde mais elle l'avantage immense de très très bien se généraliser, si par exmeple tu veux ajouter le / ou le -, ce sera très simple.
Par contre, tu remarquera que l'écriture de la grammaire n'est pas facile sans expérience.
Il y a sûrement plein de détail dans ce code qui sont important.
Par exemple, on pourrait être tenter lors de l'analyse du + de faire:

Expression *ParseAddExpression()
{
   // d'abord on lit une expression contenant des *,(),..
   Expression *expr=ParseMulExpression();
   // s'il y a un '+' on le gère
   if(CurToken().type==Token::Add)
   {
      // on saute le '+'
      NextToken();
      // on lit une autre expression MAIS AVEC AUSSI DES +
      return new AddExpression(expr,ParseAddExpression());
   }
   else
       return expr;
}

C'est vrai qu'il a l'air plus simple et qu'il marche pour '+' mais il ne marche pas pour '-'.
Pourquoi, en fait c'est un problème d'associativité des opérateurs.
Par exemple en mathématiques, le + est associatif:
a+b+c=(a+b)+c=a+(b+c)
Mais par contre le - est seulement associatif à gauche:
a-b-c=(a-b)-c != a-(b-c)
Or et c'est mon point, on voit une méthode très astucieuse apparaître ici: si on code ParseAddExpression avec une boucle while, on code une associativité à gauche alors que si on le code avec une récursion on le code avec une associativité à droite. C'est pour çà que cette méthode est très puissante, parce qu'elle est très flexible.
De même elle gère la priorité des opérateurs.
Un exemple à la main pour comprendre:

*On analyse T="(-1+2)*3-4*6"
*e=ParseAddExpression("(-1+2)*3-4*6")
  *e1=ParseMulExpression("(-1+2)*3-4*6")
    *e=ParseSimpleExpression("(-1+2)*3-4*6")
     Oui: il y a une (
     e=ParseExpression("-1+2)*3-4*6")
      *e=ParseMulExpression("-1+2)*3-4*6")
        *e=ParseSimpleExpression("-1+2)*3-4*6")
         Oui: le moins unaire:
         *e=ParseSimpleSimpleExpression("1+2)*3-4*6")
          Oui: la constante: e=ValueExp(1)
         e=NegExp(ValueExp(1))
       Ici: T="+2)*3-4*6)" car le reste a été analyse.
     Oui: le +
     * e2=ParseMulExpression("2)*3-4*6")
       *e2=PaseSimpleExpression("2)*3-4*6")
        Oui: le 2
        e2=ValueExp(2)
     e=AddExp(NegExp(ValueExp(1)),ValueExp(2))
    Oui: il y a bien la )
    Ici: T="*3-4*6"
    e=AddExp(NegExp(ValueExp(1)),ValueExp(2))
   Oui: il y a le *
   *e2=ParseSimpleExpression("3-4*6)")
    Oui: le 3
    e2=ValueExp(3)
   e=MulExp(AddExp(NegExp(ValueExp(1)),ValueExp(2)),ValueExp(3))
...

En fait c'est une méthode extrêmmement récursive qui met toute la difficulté sur la bonne description de la grammaire à analyser. J'espère que ce code est clair mais si tu as des question n'hésite pas.
Si quelqu'un veut proposer une autre méthode ? Je sais qu'on peut aussi le faire avec des piles et la priorité des opérateurs mais je ne saurais pas l'écrire.

Ou si vraiment tu cherches la rolls-royce du parser de Regex :

boost.spirit

Salut tout le monde,
je suis en train de faire cet exercice , c'est vrai qu'il est pas facile du tout
voici ce que je compte faire :

construireArbre(expression arithmétique)
parcourir la chaine pour trouver le caractère qui sera dans racine().info
modification de l'info de la racine.
if (! condition d'arrêt - quand on'a inseré un nombre entier et non pas un symbole arithmetique, il faut s'arrêter)
{
sousArbreGauche = constuireArbre(...)
sousArbreDroit = constuireArbre(...)
}

bon j'espère que mon idée est clair