Arbre binaire pour expression opératorielle

Version imprimable

Bonjour,
Je ne sais pas trop sur quel forum poster mon sujet, donc je le poste ici puisque je programme en C++.

Je cherche à écrire un code capable de lire et évaluer non pas une expression arithmétique (ça je sais faire), mais une expression opératorielle, c'est à dire une expression du genre

Code:

H=Sum{i,1,3}(4*(C[i]+A[i])*(C[i]+3*A[i])+5)

dans laquelle la notation "Sum{i,1,3}" représente la somme sur l'indice i de 1 à 3, et C[i] et A[i] sont respectivement des operateurs d'incrémentation et de décrémentation de la composante i d'un vecteur. H est donc un opérateur destiné à agir sur un vecteur.

Ce que je voudrais faire, c'est un programme qui affiche le développement de l'expression, c'est à dire pour notre example:
Code:

1 2 3 4 5 H = Sum{i,1,3}(4*(C[i]+A[i])*(C[i]+3*A[i])+5) = 4*C[1]C[1]+12*C[1]A[1]+4*A[1]C[1]+12*A[1]A[1] + 4*C[2]C[2]+12*C[2]A[2]+4*A[2]C[2]+12*A[2]A[2] + 4*C[3]C[3]+12*C[3]A[3]+4*A[3]C[3]+12*A[3]A[3]+15
J'ai réussi à écrire un code qui construit un arbre binaire pour cette expression, c'est quasiment pareil que pour les arbres arithmétiques. Ce qui me manque c'est une méthode de lecture de l'arbre qui me permette d'afficher le développement de l'expression.

Quelqu'un a-t-il une idée?

(Si vous vous demandez à quoi ça sert, c'est pour écrire un algorithme de résolution de l'équation de Schrödinger pour la Mécanique Quantique).

12/02/2009, 09h25
white_tentacle

Normalement, l'évaluation de ton arbre binaire, ça doit être assez trivial, si la structure de ton arbre est bonne.

On pourra plus facilement t'aider si tu la donnes ;).
12/02/2009, 12h45
ValyGator
Citation:

Envoyé par white_tentacle

Normalement, l'évaluation de ton arbre binaire, ça doit être assez trivial, si la structure de ton arbre est bonne.

On pourra plus facilement t'aider si tu la donnes ;).

Ok, voici la grammaire que j'ai utilisée (oublions pour simplifier l'opération de somme "Sum{i,1,3}"):
Code:

1 2 3 4 5 E -> E + T | E - T | T T -> T * F | T / F | F F -> N | I | Op | (E) Op-> I [E]
Traduction: Une expression est soit une expression plus un terme, soit une expression moins un terme, soit un terme. Un terme est soit un terme multiplié par un facteur, soit un terme divisé par un facteur, soit un facteur. Un facteur est soit un nombre, soit un identifiant (qui a une valeur associée), soit un opérateur, soit une expression entre parenthèses. Finalement un opérateur est un identifiant suivi d'une expression entre crochets.

Les feuilles sont donc les nombres N et les identifiants I. Les noeuds sont les operations +-*/ qui ont deux fils (oublions les + et - unaires), ou les operateurs Op qui ont un seul fils. L'expression est analysée de droite à gauche afin d'assurer les priorités de calcul correctes.

Ainsi, si l'on oublie les opérateurs, l'expression s'évalue très simplement par récurrence. Le problème est donc le suivant: Etant donné l'arbre obtenu par cette grammaire, comment le lire de manière à afficher l'expression développée?
12/02/2009, 14h18
white_tentacle

Citation:

Ainsi, si l'on oublie les opérateurs, l'expression s'évalue très simplement par récurrence.

Oui, c'est bien pour ça que je ne voyais pas où était ton problème.

Citation:

Le problème est donc le suivant: Etant donné l'arbre obtenu par cette grammaire, comment le lire de manière à afficher l'expression développée?

Donc je n'avais encore rien compris :).

Si tu parenthèses tout, c'est très simple. Tu affiches une parenthèse ouvrante, puis tu affiches l'expression de gauche, puis la prenthèse fermante, etc...

Si tu ne veux pas de parenthèses surnuméraire, il faut voir dans quel cas tu peux te passer de parenthèses. Je ne vois pas de solution systématique, autre qu'isoler les cas (tu as besoin de l'opérateur courant et de l'opérateur gauche pour savoir s'il faut parenthéser à gauche, et de l'opérateur courant et de l'opérateur droit pour parenthéser à droite), en sachant que tu peux te limiter à cette profondeur (flemme de faire la démonstration, mais il me semble bien que c'est le cas).
12/02/2009, 14h47
ValyGator

Je ne vois pas très bien... Si je fais ce que tu dis, le résultat sera l'affichage de l'expression telle quelle, c'est à dire sous forme factorisée. Ce que je veux c'est l'affichage sous forme développée.

Oublions les opérateurs, qui finalement ne sont pas la cause du problème. Si je donne l'expression 3*(4+5)*(7-2)+25, je veux que l'affichage donne 3*4*7-3*4*2+3*5*7-3*5*2+25.
12/02/2009, 15h00
HanLee

Citation:

Envoyé par ValyGator

Je ne vois pas très bien... Si je fais ce que tu dis, le résultat sera l'affichage de l'expression telle quelle, c'est à dire sous forme factorisée. Ce que je veux c'est l'affichage sous forme développée.

Oublions les opérateurs, qui finalement ne sont pas la cause du problème. Si je donne l'expression 3*(4+5)*(7-2)+25, je veux que l'affichage donne 3*4*7-3*4*2+3*5*7-3*5*2+25.

Je comprends pas. Si tu as l'arbre, et que tu veux développer, tu fais comme on t'a appris à l'école.

Dans un langage comme Caml, c'est assez concis à faire. De manière simple, tu procèdes itérativement. Tant qu'il est possible de développer, c'est à dire qu'il y a une sous-expression de type Produit d'une Somme avec une Expression, alors tu peux développer.