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.
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 ?
"La haine seule fait des choix" - Koan Zen
"Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
"Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
Faites du Prolog, ça vous changera les idées !
Ma page Prolog
Mes codes sources commentés
Mon avatar : La Madeleine à la veilleuse de Georges de La Tour
je n'ai pas pensé à ça
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 ?
"La haine seule fait des choix" - Koan Zen
"Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
"Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
Faites du Prolog, ça vous changera les idées !
Ma page Prolog
Mes codes sources commentés
Mon avatar : La Madeleine à la veilleuse de Georges de La Tour
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.
"La haine seule fait des choix" - Koan Zen
"Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
"Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
Faites du Prolog, ça vous changera les idées !
Ma page Prolog
Mes codes sources commentés
Mon avatar : La Madeleine à la veilleuse de Georges de La Tour
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 : 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
Bon courage
Dernière modification par alex_pi ; 30/12/2007 à 17h13.
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 : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7 ex : => v a b c => / \ v c / \ a bD'ailleurs, quel langage dois-tu utiliser ? As tu le droit d'utiliser un lexeur/parseur ou dois tu faire le tiens "à la main" ?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
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.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.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 : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4 convertir(<OperateurUnaire> <Expression>) = <OperateurUnaire> convertir(Expression) convertir(<OperateurBinaire> <Expression1> <Expression2>) = convertir(<Expression1>) <OperateurBinaire> convertir(<Expression2>)
Mon site :
ici
Mes articles :
Prise en main de Ant
Administration des ressources avec JMX
Programmation orientée aspect en Java avec AspectJ
Mon CV :
ici
Troll detectedQuel 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...
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
Pas pu m'en empêcher.
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ï
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager