Discussion :

[jayfaze]

J'ai enfin compris le principe de l'arbre binaire. J'aimerais maintenant l'utiliser pour résoudre un exercice que je dois faire.
Ma fonction doit calculer des expressons du genre :
3+42*(1-2/(3+4)-1%21)+1

J'ai penser à ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
  (+)
  / \
(3) (42)
      \
     (*)
     / \
    (-)(+)
   /  \  \
 (1)  (2)(1)
         \
         (/)
         /  \
        (+) (-)
        /\    \
       (3)(4) (1)
              \
              (21)

J'espère que c'est compréhensible.
Je voudrais savoir si je suis sur la bonne piste. Mon programme doit s'exécuter le plus vite possible. Donc l'arbre me parait la meilleure solution.
J'ai aussi essayer passer par les listes chainées mais j'ai pas trouvé le moyen.

[Médinoc]

Salut,
Il y a plusieurs étapes différentes dans ce genre d'intérprétation.
D'abord, la lecture :

1. Séparer les jetons (nombre, opérateur, etc.)
2. Créer un arbre en tenant compte des priorités opératoires et des parenthèses.

Ensuite, c'est là que ça devient intéressant. Tu peux:

• soit évaluer l'opération en faisant un parcours postfixe de l'arbre,
• soit convertir l'arbre en liste (chaînée ou non) d'opérations en NPI (notation polonaise inverse), là encore avec un parcours suffixe, et évaluer cette opération à l'aide d'une pile (plus compliqué, mais plus pratique s'il faut évaluer l'opération plusieurs fois).

Pour le cas de "calculer chaque opération tapée", je pense qu'évaluer directement l'arbre est la meilleure solution.
Ou bien, tu triches en rentrant directement l'opération en NPI, et dans ce cas tu as juste à séparer les jetons et évaluer avec une pile. Imparable pour la vitesse.

Note: En NPI, ton opération 3+42*(1-2/(3+4)-1%21)+1 donnerait ceci:
3 42 1 2 3 4 + / - 1 21 % - * + 1 +

PS: Ton arbre est erroné: Les nombres sont forcément des feuilles de l'arbre, jamais des noeuds.

[jayfaze]

Les nombres ne sont jamais des feuilles ?
même si c'est un truc du genre
42*(2+3) ?

a moins que

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
 (*)
 /  \
(42)(+)
    / \
  (2)(3)

Sinon merci pour es conseils, je regarde si je peux le faire en NPI avec une pile, mais il faut que je l'étudie un peu plus (la NPI), parceque j'a regardé un peu et ça à l'air compliquée.

[Médinoc]

J'ai dit les nombres sont TOUJOURS des feuilles.

Et oui, ton arbre pour 42*(2+3) est correct.
Et en NPI, ça donnerait 42 2 3 + *