Discussion :

[acacia]

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.

[Trap D]

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

[acacia]

je n'ai pas pensé à ça

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

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

[Trap D]

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

[acacia]

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?

[Trap D]

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.

[alex_pi]

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 :

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

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

[acacia]

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 :

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

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

[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
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é

[alex_pi]

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 :

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

1
2
3
4
5
6
7
 
ex : => v a b c
    =>
   /  \
  v    c
 / \
a  b

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" ?

[acacia]

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