Algorithme Notation préfixé -> notation infixée d'une formule

Bonjour,

sur un sujet d'examen de logique propositionnelle, on doit présenter un algorithme qui refait la notation infixée d'une formule en notation polonaise sans parenthèses.

une idée pour commencer s'il vous plait

Merci.

As-tu une idée de la grammaire des expressions en notation polonaise ?

je n'ai pas pensé à ça :oops:

EXPR -> OP | v EXPR EXPR | ^ EXPR EXPR | -> EXPR EXPR | <-> EXPR EXPR

OP -> a|b|c|d........|y|z

A partir de celà, tu dois pouvoir te débrouiller avec des règles de réécriture.
Tu n'as pas EXPR -> ! EXPR ?

Citation:

---

Envoyé par Trap D

A partir de celà, tu dois pouvoir te débrouiller avec des règles de réécriture.

---

merci,

c'est quoi les règles de réecriture? :oops:

Je pensais simplement à ceci
Si EXPR -> ^EXPR EXP donne par réécriture (EXPR ^ EXPR).

Comme c'est TREEEEEEEEEEEEES loin pour moi, j'appelle ça des règles de réécriture.

d'accord merci je vais commencer comme ça.

Citation:

---

Envoyé par acacia

sur un sujet d'examen de logique propositionnelle, on doit présenter un algorithme qui refait la notation infixée d'une formule en notation polonaise sans parenthèses.

---

Bonjour.

Est ce que tu dois fournir un affichage avec un minimum de parenthèse ?

De toutes façons, la solution générale est de parser ton expression pour en obtenir un arbre, puis de faire un pretty printer pour cet arbre. Là où ça se complique un peu, c'est pour la position des parenthèses si tu ne veux pas en mettre trop. Réussir à atteindre le nombre minimal de parenthèse n'est pas exactement trivial, mais ça se fait.
[EDIT]
J'ai ça :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

./a.out   <-> a -> b ! c a <-> (b -> !c)   -> v a b ^c d a v b -> c ^ d   -> ! v a b ^c d !(a v b) -> c ^ d

---

[/EDIT]

Bon courage

Citation:

---

Envoyé par alex_pi

Bonjour.

Est ce que tu dois fournir un affichage avec un minimum de parenthèse ?

De toutes façons, la solution générale est de parser ton expression pour en obtenir un arbre, puis de faire un pretty printer pour cet arbre. Là où ça se complique un peu, c'est pour la position des parenthèses si tu ne veux pas en mettre trop. Réussir à atteindre le nombre minimal de parenthèse n'est pas exactement trivial, mais ça se fait.
[EDIT]
J'ai ça :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

./a.out   <-> a -> b ! c a <-> (b -> !c)   -> v a b ^c d a v b -> c ^ d   -> ! v a b ^c d !(a v b) -> c ^ d

---

[/EDIT]

Bon courage

---

Bonjour,
merci de m'avoir répondu

je dois fournir le résultat avec les parenthèses si necessaire.

j'ai trouvé des solutions avec des piles et des tableaux mais je n'ai pas très bien compris comment ça fonctionne :(

il te faut construire un arbre avec pour noeud tes opérateurs et pour feuilles tes expressions. Les opérateurs ont entre 1 et n fils en fonctions du nombre d'argument, a chaque opérateur tu crées un nouveau noeuds a chaque expression tu crées une feuilles et tu remonte au premier fils droits non valorisés
ex : - + a b c
-
/ \
+ c
/ \
a b
pour la réécriture il suffit de reparcourir l'arbre, dans un premier temps un parenthésage amssifs permet d'être sur)
((a + b) - c)

La gestion de l'arbre est fortement lié au langage utilisé

Citation:

---

Envoyé par jarko

il te faut construire un arbre avec pour noeud tes opérateurs et pour feuilles tes expressions. Les opérateurs ont entre 1 et n fils en fonctions du nombre d'argument, a chaque opérateur tu crées un nouveau noeuds a chaque expression tu crées une feuilles et tu remonte au premier fils droits non valorisés

---

J'avoue n'avoir moi même pas bien compris la fin de ton explication... Je dirais surtout qu'à partir du moment où tu as un arbre, imprimer une expression, c'est imprimer la sous expression gauche, imprimer le symbole et imprimer la sous expression droite, en se débrouillant pour avoir un bon parenthésage.

Voilà une reproduction de ton arbre avec la balise CODE :

Code:

---

1 2 3 4 5 6 7

ex : => v a b c => / \ v c / \ a b

---

Citation:

---

La gestion de l'arbre est fortement lié au langage utilisé

---

D'ailleurs, quel langage dois-tu utiliser ? As tu le droit d'utiliser un lexeur/parseur ou dois tu faire le tiens "à la main" ?

Bonsoir :)

Merci pour vos réponses

au fait, qu'est ce qu'un lexeur/parseur?

je ne vois toujours pas comment faire l'algorithme de la création de cet arbre :oops:

Généralement :

lexer = analyseur lexical.
parser = analyser syntaxique.

l'analyseur lexical crée, à l'aide d'un code source une suite de token, si l'analyse lexicale est accomplie correctement, le code source est valide lexicalement (ie: il ne contient que des éléments lexicaux corrects).

Le parser prend la suite de token en entrée et crée généralement un arbre de syntaxe abstraite.

Les outils unix classiques pour ces analyses sont :

-> (f)lex
-> yacc/bison

Citation:

---

Envoyé par PRomu@ld

Généralement :

lexer = analyseur lexical.
parser = analyser syntaxique.

l'analyseur lexical crée, à l'aide d'un code source une suite de token, si l'analyse lexicale est accomplie correctement, le code source est valide lexicalement (ie: il ne contient que des éléments lexicaux corrects).

Le parser prend la suite de token en entrée et crée généralement un arbre de syntaxe abstraite.

Les outils unix classiques pour ces analyses sont :

-> (f)lex
-> yacc/bison

---

Merci :)

donc tout ça fait partie de la compilation! et pour compiler il y a toujours une analyse syntaxique, léxicale...etc

pourquoi alex_pi a précisé si on a le droit ou non de l'utiliser? :?

Citation:

---

donc tout ça fait partie de la compilation! et pour compiler il y a toujours une analyse syntaxique, léxicale...etc

---

Ce sont les outils fondamentaux de la compilation, l'analyse lexicale et syntaxique sont la première étape de tout compilateur.

Citation:

---

pourquoi alex_pi a précisé si on a le droit ou non de l'utiliser?

---

Parce que se sont des outils relativement simple à utiliser et qu'ils sont puissant. Ca permettrait de résoudre ton problème très simplement.

Quelques fois on ne peut pas (ou on ne veut pas) utiliser ces outils, d'où la question d'alex_pi.

Citation:

---

Envoyé par PRomu@ld

Ce sont les outils fondamentaux de la compilation, l'analyse lexicale et syntaxique sont la première étape de tout compilateur.

Parce que se sont des outils relativement simple à utiliser et qu'ils sont puissant. Ca permettrait de résoudre ton problème très simplement.

Quelques fois on ne peut pas (ou on ne veut pas) utiliser ces outils, d'où la question d'alex_pi.

---

D'un point de vue pédagogique, ces outils sont pratiquement "trop" puissant pour ce qu'il veut faire, une seule fonction récursive suffit. Les utiliser dans son cas reviendrait à utiliser un marteau pour casser une noix... ;) (et masquerait le fait que fondamentalement les lexeurs/parseurs n'ont rien de magique, objectif des premiers exercices dans le domaine avant de commencer à utiliser des outils)

Quel est le langage à utiliser ? Du pseudo-code, du C, un vrai langage comme du OCaml ???

--
Jedaï

Merci

comment je pourrai résoudre mon problème avec lex/yacc ? :oops:

Citation:

---

Envoyé par Jedai

D'un point de vue pédagogique, ces outils sont pratiquement "trop" puissant pour ce qu'il veut faire, une seule fonction récursive suffit. Les utiliser dans son cas reviendrait à utiliser un marteau pour casser une noix... ;) (et masquerait le fait que fondamentalement les lexeurs/parseurs n'ont rien de magique, objectif des premiers exercices dans le domaine avant de commencer à utiliser des outils)

Quel est le langage à utiliser ? Du pseudo-code, du C, un vrai langage comme du OCaml ???

--
Jedaï

---

Bonsoir

je comptais le coder en langage C mais je voulais d'abord faire l'algorithme :oops:

Salut acacia

j'ai pensé a un ptit algo recursif, mais je l'ai pas encore implementé

Code:

---

1 2 3 4

convertir(<OperateurUnaire> <Expression>) = <OperateurUnaire> convertir(Expression)   convertir(<OperateurBinaire> <Expression1> <Expression2>) = convertir(<Expression1>) <OperateurBinaire> convertir(<Expression2>)

---

donc, à toi de commencé a le codé, en attendant que je le fasse ^^

Citation:

---

Quel est le langage à utiliser ? Du pseudo-code, du C, un vrai langage comme du OCaml ???

---

:alerte: Troll detected :alerte:

Citation:

---

Envoyé par Jedai

D'un point de vue pédagogique, ces outils sont pratiquement "trop" puissant pour ce qu'il veut faire, une seule fonction récursive suffit.

---

Vu le PO, le problème "pédagogique" semble être surtout d'ecrire les règles de réécriture. Les problèmes "annexes" tels que les I/O et le parsing ne me semble pas important au point de ne pas utiliser les librairies et outils adéquats. A confirmer par acacia...

Citation:

---

Envoyé par pseudocode

:alerte: Troll detected :alerte:

---

Pas pu m'en empêcher. :D
D'un autre côté tu dois avouer que faire ça en C introduit d'emblée un certain nombre de problème annexes qui n'existent pas dans un langage de plus haut-niveau (pas forcément OCaml). (pas qu'on ne puisse pas faire de parser à la main en C, il n'y a qu'à regarder ce sujet, mon parser était au final assez complet, et le problème (parser du HTML pour en extraire les liens) était autrement plus hardu)

Citation:

---

Envoyé par pseudocode

Vu le PO, le problème "pédagogique" semble être surtout d'ecrire les règles de réécriture. Les problèmes "annexes" tels que les I/O et le parsing ne me semble pas important au point de ne pas utiliser les librairies et outils adéquats. A confirmer par acacia...

---

Vu que les règles de réécritures sont enfantines, je vois mal comment elles pourraient être d'un quelconque intérêt pédagogique... Eventuellement s'il s'agissait de mettre le moins de parenthèses possible, mais on ne sait toujours pas si c'est dans l'énoncé.

--
Jedaï

on doit utiliser des parenthèses pour passer d'une préfixée à l'infixée, non?

et du coup, je ne vois pas du tout comment je dois le faire :(

Bonjour,
Quelqu'un pourrait-il me donner l'algo d'obtention de la notation polonaise d'une expression arithmétique ?

Merci.

Citation:

---

Envoyé par kitim

Bonjour,
Quelqu'un pourrait-il me donner l'algo d'obtention de la notation polonaise d'une expression arithmétique ?

Merci.

---

Tu parses l'expression arithmétique, puis tu la réimprime en notation polonaise, inversée ou non, à ta convenance.

De rien.

Citation:

---

Envoyé par kitim

Bonjour,
Quelqu'un pourrait-il me donner l'algo d'obtention de la notation polonaise d'une expression arithmétique ?

Merci.

---

Essaye de voir avec le test de Lukasiewicz.

J'ai un code qui fait cette conversion écrit en java, je pourrai le retrouver après.

Bon courage