IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

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


Sujet :

Algorithmes et structures de données

  1. #1
    En attente de confirmation mail
    Étudiant
    Inscrit en
    Août 2007
    Messages
    419
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2007
    Messages : 419
    Points : 263
    Points
    263
    Par défaut 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.

  2. #2
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Points : 6 498
    Points
    6 498
    Par défaut
    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

  3. #3
    En attente de confirmation mail
    Étudiant
    Inscrit en
    Août 2007
    Messages
    419
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2007
    Messages : 419
    Points : 263
    Points
    263
    Par défaut
    je n'ai pas pensé à ça

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

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

  4. #4
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Points : 6 498
    Points
    6 498
    Par défaut
    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

  5. #5
    En attente de confirmation mail
    Étudiant
    Inscrit en
    Août 2007
    Messages
    419
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2007
    Messages : 419
    Points : 263
    Points
    263
    Par défaut
    Citation Envoyé par Trap D Voir le message
    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?

  6. #6
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Points : 6 498
    Points
    6 498
    Par défaut
    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

  7. #7
    En attente de confirmation mail
    Étudiant
    Inscrit en
    Août 2007
    Messages
    419
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2007
    Messages : 419
    Points : 263
    Points
    263
    Par défaut
    d'accord merci je vais commencer comme ça.

  8. #8
    alex_pi
    Invité(e)
    Par défaut
    Citation Envoyé par acacia Voir le message
    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
    Dernière modification par alex_pi ; 30/12/2007 à 17h13.

  9. #9
    En attente de confirmation mail
    Étudiant
    Inscrit en
    Août 2007
    Messages
    419
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2007
    Messages : 419
    Points : 263
    Points
    263
    Par défaut
    Citation Envoyé par alex_pi Voir le message
    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

  10. #10
    Membre du Club
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    62
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 62
    Points : 64
    Points
    64
    Par défaut
    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é

  11. #11
    alex_pi
    Invité(e)
    Par défaut
    Citation Envoyé par jarko Voir le message
    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" ?

  12. #12
    En attente de confirmation mail
    Étudiant
    Inscrit en
    Août 2007
    Messages
    419
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2007
    Messages : 419
    Points : 263
    Points
    263
    Par défaut
    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

  13. #13
    Expert éminent
    Avatar de PRomu@ld
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    Avril 2005
    Messages
    4 155
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Vienne (Poitou Charente)

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2005
    Messages : 4 155
    Points : 6 486
    Points
    6 486
    Par défaut
    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

  14. #14
    En attente de confirmation mail
    Étudiant
    Inscrit en
    Août 2007
    Messages
    419
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2007
    Messages : 419
    Points : 263
    Points
    263
    Par défaut
    Citation Envoyé par PRomu@ld Voir le message
    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?

  15. #15
    Expert éminent
    Avatar de PRomu@ld
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    Avril 2005
    Messages
    4 155
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Vienne (Poitou Charente)

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2005
    Messages : 4 155
    Points : 6 486
    Points
    6 486
    Par défaut
    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.

    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.

  16. #16
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Citation Envoyé par PRomu@ld Voir le message
    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ï

  17. #17
    En attente de confirmation mail
    Étudiant
    Inscrit en
    Août 2007
    Messages
    419
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2007
    Messages : 419
    Points : 263
    Points
    263
    Par défaut
    Merci

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

    Citation Envoyé par Jedai Voir le message
    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

  18. #18
    Membre éprouvé
    Avatar de LinkinSelim
    Profil pro
    Enseignant Chercheur
    Inscrit en
    Mars 2006
    Messages
    365
    Détails du profil
    Informations personnelles :
    Localisation : Algérie

    Informations professionnelles :
    Activité : Enseignant Chercheur

    Informations forums :
    Inscription : Mars 2006
    Messages : 365
    Points : 1 034
    Points
    1 034
    Par défaut
    Salut acacia

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

    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>)
    donc, à toi de commencé a le codé, en attendant que je le fasse ^^

  19. #19
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Quel est le langage à utiliser ? Du pseudo-code, du C, un vrai langage comme du OCaml ???
    Troll detected

    Citation Envoyé par Jedai Voir le message
    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...
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  20. #20
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    Troll detected
    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)

    Citation Envoyé par pseudocode Voir le message
    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ï

Discussions similaires

  1. Algorithme de geolocalisation d'un objet dans une image
    Par EmilieTech dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 15/11/2009, 13h15
  2. Réponses: 42
    Dernier message: 07/08/2009, 22h11
  3. Algorithme de calcul de l'inverse d'une matrice carrée (nxn)
    Par mobi_bil dans le forum Mathématiques
    Réponses: 5
    Dernier message: 20/03/2009, 00h53
  4. Notation préfixée à infixée
    Par jmi23 dans le forum Scheme
    Réponses: 5
    Dernier message: 04/03/2008, 00h56
  5. Réponses: 28
    Dernier message: 02/03/2008, 01h28

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo