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.
Version imprimable
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 ?
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.
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 :
[/EDIT]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
Bon courage
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é
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
D'ailleurs, quel langage dois-tu utiliser ? As tu le droit d'utiliser un lexeur/parseur ou dois tu faire le tiens "à la main" ?Citation:
La gestion de l'arbre est fortement lié au langage utilisé
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
Ce sont les outils fondamentaux de la compilation, l'analyse lexicale et syntaxique sont la première étape de tout compilateur.Citation:
donc tout ça fait partie de la compilation! et pour compiler il y a toujours une analyse syntaxique, léxicale...etc
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.Citation:
pourquoi alex_pi a précisé si on a le droit ou non de l'utiliser?
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ï
Salut acacia
j'ai pensé a un ptit algo recursif, mais je l'ai pas encore implementé
donc, à toi de commencé a le codé, en attendant que je le fasse ^^Code:
1
2
3
4 convertir(<OperateurUnaire> <Expression>) = <OperateurUnaire> convertir(Expression) convertir(<OperateurBinaire> <Expression1> <Expression2>) = convertir(<Expression1>) <OperateurBinaire> convertir(<Expression2>)
:alerte: Troll detected :alerte:Citation:
Quel est le langage à utiliser ? Du pseudo-code, du C, un vrai langage comme du OCaml ???
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...
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)
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ï