explications sur notation polonaise, postfixe

Bonjour a tous,

Je dois réaliser une calculatrice et je pars du principe de me débarrasser des parenthèses. J'ai donc l'idée d'utiliser la notation polonaise inversée (NPI) ou (RPN) et d'utiliser un arbre binaire.

Mon souchis est la compréhension totale de la NPI.8O

- Une fois qu'on a converti en NPI comment repasse-t-on en décimal pour arriver au même calcul (résultat) de départ ?

- Pourrais-je avoir un exemple sur un calcul avec parenthèses et plusieurs opérandes : ((8 / (3 - 2 + 4 - 5)) * (3 - 1) * 6)

J'ai bien évidemment passe du temps sur google et je n'ai pas mes reponses alors je demande ici.

Merci de votre aide et conseils.

La NPI est juste une représentation postfixe d'un arbre, et peut s'évaluer avec une pile.

Code:

---

((8 / (3 - 2 + 4 - 5)) * (3 - 1) * 6)

---

Traduit en NPI, donne:

Code:

---

8 3 2 - 4 + 5 - / 3 1 - * 6 *

---

si je ne suis pas trop rouillé.

Heu....

Tu m'explique comment tu as fait, la réponse c'est sympa, mais l'explication est ce que je recherche.

Merci

Pour faire ça de tête, c'est simple:
Tu dresses l'arbre de calcul, et tu en fais un parcours postfixe.

Pour convertir informatiquement, il y a un algo, que j'ai oublié, mais qui a dû être posté plusieurs fois sur le forum. Il implique d'utiliser une pile pour la transformation.
Je ne peux pas confirmer car mon proxy fait des siennes, mais il me semble que cet algo est disponible quelque part sur Wikipédia.

Citation:

---

Envoyé par Inh[Star]Noz

Heu....

Tu m'explique comment tu as fait, la réponse c'est sympa, mais l'explication est ce que je recherche.

Merci

---

Il suffit de representer l'expression sous forme d'arbre et de faire un parcours suffixe (aka postorder).

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

infixe: (8 / (3 - 2))*4   (*) / \ (/) 4 / \ 8 (-) / \ 3 2   RPN: 8 3 2 - / 4 *

---

Il y a également des algorithmes pour transformer une expression mathématique usuelle (infixe) en représentation RPN, par exemple l'algo "Shunting yard".

Qu'entends-tu par "je pars du principe de me débarrasser des parenthèses"?

Veux-tu que ta calculette prenne en entrée des expressions infixe avec parenthèses, et qu'elle stocke ça en interne avec un format à la NPI? ou que l'utilisateur de la calculette tape ses calculs en NPI?

*LeGEC*

oui c'est bien sa.

Je reçois en paramètre un char * (chaine de caractères) en infixe et je dois en trouver le résultat.

Je vais donc essayer de convertir infixe -> postfixe et ensuite retrouver le résultat avec un système de pile.

Je vois mal comment gérer les opérateurs unaires mais je n'y suis pas encore. Je me lance dans le code, vu que j'ai un début d'algorithme.

bonjour,

trouve donc une petite grammaire qui définit ce qu'est une expression arithmétique. Cela te permettra de vérifier que l'expression est juste et ensuite de construire l'arbre automatiquement.
Fais une recherche dans ce forum, le sujet a déjà été traité.

...moué.
Disons que je ne m'occupe pas de savoir si l'expression est juste ou non pour l'instant.

Je n'ai peut etre pas compris ce que tu as dit :/

bonjour,

en ayant une grammaire (très simple pour tout ce qui est expression arithmétiques) et en remplaçant chaque élément de la grammaire par une simple fonction (cinq ligne max par fonction), cela te permet de :
- vérifier que l'expression est juste.
- construire l'arbre.
- calculer la valeur de l'expression.

Bonjour,

J'ai avance mon projet. Je n'ai pas utilise d'arbre en fait, mais une liste doublement chainee.

J'ai actuellement un soucis pour free un element de ma pile :

Code:

---

1 2 3 4 5 6 7 8 9

void del_elem_stack(t_elem_stack **begin) { t_elem_stack *tmp;   tmp = (*begin)->next; free(*debut); (*debut)->next = 0; }

---

Mon insertion dans la stack (pile) fonctionne tres bien.

Je ne comprends pas pourquoi ...
Si on pouvait me mettre sur la voie, je continue a chercher.

Code:

---

1 2	free(*debut); (*debut)->next = 0;

---

Ça ne te choque pas, ça ?

Code:

---

1 2 3 4 5 6 7 8 9 10

void del_elem_stack(t_elem_stack **ppTop) { /* Détacher l'élément */ t_elem_stack *pDel = *ppTop; *ppTop = pDel->pNext; pDel->pNext = NULL;   /* Supprimer l'élément détaché */ free(pDel); }

---

'lol'

En fait mon probleme venait de mon parametre passe a ma fonction.
J'ai resolu le probleme donc presque tout va bien.

Il me reste un soucis sur l'expression qui est envoye en parametre.
J'essaie de trouver sinon je poste, je vous remercie d'etre la a repondre, sa pousse a la reflexion ^^

Bonjour,

J'ai une liste doublement chainee et j'ai un probleme :

Lorsque j'empile des element tout se passe bien, pour depiler pareil.
Mais lorsque je depile le dernier element et que je me retrouve avec une pile vide j'ai un segmentation fault.