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 :

evaluation d'une chaine de caractere (2+3)*4/5%8


Sujet :

Algorithmes et structures de données

  1. #1
    Membre confirmé
    Profil pro
    Inscrit en
    Novembre 2004
    Messages
    57
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2004
    Messages : 57
    Par défaut evaluation d'une chaine de caractere (2+3)*4/5%8
    bonjour
    jaurai aimer savoir commen je pouvai evaluer une chaine de caractere du type: (2+3)*4/5%8
    merci davance

  2. #2
    Membre chevronné Avatar de Jack_serious
    Profil pro
    Inscrit en
    Septembre 2005
    Messages
    350
    Détails du profil
    Informations personnelles :
    Âge : 39
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 350
    Par défaut
    Tu pourrais etre encore moins precis stp ?

    Bon, serieusement, l'evaluer comment ? La calculer ?

    Si c'est ca, la reponse ne tient pas en une seule ligne :

    Il faut que tu parcours ta chaine, que tu mette les chiffres dans des variables que tu stocke dans une pile, que tu evalue tes operateurs d'apres une base d'operateurs, que tu extraie tes nombres de ta pile pour les calculer quand tu croise des operateurs prioritaires, etc...

    Enfin bon je m'emporte...

    Essaie d'etre un (gros) poil plus precis si tu veux qu'on puisse t'aider.

  3. #3
    Membre confirmé
    Profil pro
    Inscrit en
    Novembre 2004
    Messages
    57
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2004
    Messages : 57
    Par défaut
    excuse moi mai pr moi c ete clair
    jai pas penser aux autres
    oui en fait il faut que je le calcul cette expression
    jai compris le principe que tu vien dexpliquer avec la pile
    mai jai encore js fait de simulation de pile...peut mexpliquer??
    merci

  4. #4
    Expert éminent
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 385
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 385
    Par défaut
    Je suis justement sur un exercice la-dessus, trouvé dans un bouquin de c++.

    Il y a plusieurs étapes:
    1) Séparer les nombres, opérateurs etc. Si les nombres sont garantis faire un chiffre au plus, c'est comme si c'était déjà fait.

    2) Pour évaluer l'expression, c'est assez dur dans ce sens: Il peut être utile de la convertir en notation postfixée (Notation Polonaise Inverse)
    (l'algorithme est dans le bouquin, mais je ne l'ai pas ici)

    3) Quand tu as une expression en NPI, il est facile de l'évaluer, avec une pile.
    [U]SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.[/U]

    [I]"Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.[/I] -- [URL="http://blogs.msdn.com/oldnewthing/archive/2004/01/15/58973.aspx"]Raymond[/url] [url=http://blogs.msdn.com/b/oldnewthing/archive/2011/05/06/10161590.aspx]Chen[/URL].
    [SIZE="1"][URL="http://club.developpez.com/regles/#LIII-A"]Traduction obligatoire:[/URL] "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.[/SIZE]

  5. #5
    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
    Par défaut
    Il faut écrire une grammaire des expressions arithmétiques, un analyseur lexical qui te fournira des lexèmes (nombre, opérateur), , que tu analyseras dans un analyseur syntaxique qui construira l'arbre syntaxique (si je ne me trompe pas). Ensuite il ne reste plus qu'à évaluer.
    Direction forum algo.
    "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

  6. #6
    Membre expérimenté
    Homme Profil pro
    Inscrit en
    Avril 2002
    Messages
    290
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Secteur : Industrie

    Informations forums :
    Inscription : Avril 2002
    Messages : 290
    Par défaut
    les outils pour faire celà c'est Yacc et Lex (ou Bison et flex)...

  7. #7
    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
    Par défaut
    Ouaih, ça fait le travail à la place de l'étudiant, est-ce qu'il cherche ?
    "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

  8. #8
    Membre confirmé
    Profil pro
    Inscrit en
    Novembre 2004
    Messages
    57
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2004
    Messages : 57
    Par défaut
    javai une petite ide avec la NPI mais jai l'algo correspondant
    si tu peu me le filer des que tu peux??
    et pour lex et yacc je suis au courant mais cest ds un projet de C dc impossible...

  9. #9
    Expert éminent
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 385
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 385
    Par défaut
    Citation Envoyé par ricardvince
    javai une petite ide avec la NPI mais jai l'algo correspondant
    si tu peu me le filer des que tu peux??
    OK, Je te file l'algo de conversion dès que possible.
    En attendant, tu peux toujours faire l'algo de décomposition de la chaîne en nombres, ops, etc (si les nombres peuvent avoir deux chiffres ou plus, ce sera nécessaire) et l'algorithme d'exécution à partir de la NPI...

    et pour lex et yacc je suis au courant mais cest ds un projet de C dc impossible...
    Qu'est-ce que cette phrase veut dire? Si c'est que tu n'as pas le droit, OK. Mais si elle veut dire que lex et yacc ne marchent pas avec le C, elle est fausse à un point proche de l'infini.
    [U]SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.[/U]

    [I]"Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.[/I] -- [URL="http://blogs.msdn.com/oldnewthing/archive/2004/01/15/58973.aspx"]Raymond[/url] [url=http://blogs.msdn.com/b/oldnewthing/archive/2011/05/06/10161590.aspx]Chen[/URL].
    [SIZE="1"][URL="http://club.developpez.com/regles/#LIII-A"]Traduction obligatoire:[/URL] "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.[/SIZE]

  10. #10
    Membre confirmé
    Profil pro
    Inscrit en
    Novembre 2004
    Messages
    57
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2004
    Messages : 57
    Par défaut
    pour etre clair je cherche un algo C qui me permettrai de faire une analyse lexicale et syntaxique de cette expression
    comment je peut effectuer une priorite d'operateur () avant * et /
    avant +et -...

  11. #11
    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
    Par défaut
    Je réitère, écris la grammaire associée, cherche sur Google, "Grammaire des expressions arithmétiques".
    "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

  12. #12
    Membre confirmé
    Profil pro
    Inscrit en
    Novembre 2004
    Messages
    57
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2004
    Messages : 57
    Par défaut
    et pour lex et yacc je suis au courant mais cest ds un projet de C dc impossible...

    je voulai dire que je navai pa le droit...je c bien que lex et yacc genere du code C.

  13. #13
    Expert éminent
    Avatar de Emmanuel Delahaye
    Profil pro
    Retraité
    Inscrit en
    Décembre 2003
    Messages
    14 512
    Détails du profil
    Informations personnelles :
    Âge : 68
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Retraité

    Informations forums :
    Inscription : Décembre 2003
    Messages : 14 512
    Par défaut
    Citation Envoyé par ricardvince
    et pour lex et yacc je suis au courant mais cest ds un projet de C dc impossible...

    je voulai dire que je navai pa le droit...je c bien que lex et yacc genere du code C.
    Tu px ecrire en F avc des mts entiers, ou t'es trop fénéant pour ça ? Et les regles du forum, tu les a lues ?

  14. #14
    Membre chevronné Avatar de Jack_serious
    Profil pro
    Inscrit en
    Septembre 2005
    Messages
    350
    Détails du profil
    Informations personnelles :
    Âge : 39
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 350
    Par défaut
    Pour la priorite et les operateurs, avec la NPI ca marche tout seul.

    Vu que sur ton ami qui te renvoie vers un super article de la Wikipedia quand tu tape "Notation polonaise inversee" c'est super bien explique, je vais faire bref :

    Une methode simple et efficace que j'ai deja mise en oeuvre dans un projet similaire est la suivante :

    Tu te cree deux piles :
    1_ Une pile d'operateurs
    2_ Une pile de nombres
    Des listes chainees s'imposent. Ca marche tout seul ou presque.
    Empiler = poser au dessus de la pile.
    Depiler = retirer l'element du dessus de la pile.

    Ensuite tu parse ta chaine.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
    si (tu croises un nombre) 
      tu l'empiles();
    Pour ce qui suit, depiler() = depiler deux nombres, un operateur et empiler le resultat dans la pile de nombre.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
     
    si (tu croises un operateur)
    {
      Si (c'est une parentheses fermante)
         tu depiles() jusqu'a croiser une parenthese ouvrante;
      Si ((c'est *, / ou %) et que (au sommet de la pile tu n'as ni un + ni un -) )
         tu depiles();
      Si (c'est un + ou un -)
         tant que (tu n'as pas une parenthese ouvrante au sommet de ta pile)
           tu depiles();
      Si (ton operateur que tu viens de croiser n'est pas une parenthese fermante)
           tu empiles() ton operateur;
    }

  15. #15
    Membre émérite Avatar de 10_GOTO_10
    Profil pro
    Inscrit en
    Juillet 2004
    Messages
    887
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2004
    Messages : 887
    Par défaut
    Citation Envoyé par Médinoc
    1) Séparer les nombres, opérateurs etc. Si les nombres sont garantis faire un chiffre au plus, c'est comme si c'était déjà fait.
    Attention, j'ai déjà eu à faire ça, et c'est pas si simple que ça, avec les nombres négatifs surtout:

    3 * -2 doit être interprété comme (3) * (-2) alors que si on recherche les opérateurs de priorité minimum (ici le "-"), on va obtenir (3 *) - (2) qui va générer ensuite une erreur de syntaxe ou de calcul.

  16. #16
    Membre chevronné Avatar de Jack_serious
    Profil pro
    Inscrit en
    Septembre 2005
    Messages
    350
    Détails du profil
    Informations personnelles :
    Âge : 39
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 350
    Par défaut
    Citation Envoyé par 10_GOTO_10
    Attention, j'ai déjà eu à faire ça, et c'est pas si simple que ça, avec les nombres négatifs surtout:

    3 * -2 doit être interprété comme (3) * (-2) alors que si on recherche les opérateurs de priorité minimum (ici le "-"), on va obtenir (3 *) - (2) qui va générer ensuite une erreur de syntaxe ou de calcul.
    Les nombres negatifs sont la partie la plus drole du probleme.

    Une solution consiste pendant le parsing a reperer le debut d'un nombre negatif :
    soit: un operateur suivi d'un - (ou d'un plus si on doit gerer des cas tordus)
    soit: (-

    Avec la solution que j'ai exposee plus haut :

    Citation Envoyé par jack_serious
    quand tu croises un nombre
    comprend le fait de croiser un cas similaire.

    Ensuite la fonction qui empile le nombre en question doit empiler un nombre negatif. (ou pas).

  17. #17
    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
    Par défaut
    Citation Envoyé par 10_GOTO_10
    Citation Envoyé par Médinoc
    1) Séparer les nombres, opérateurs etc. Si les nombres sont garantis faire un chiffre au plus, c'est comme si c'était déjà fait.
    Attention, j'ai déjà eu à faire ça, et c'est pas si simple que ça, avec les nombres négatifs surtout:

    3 * -2 doit être interprété comme (3) * (-2) alors que si on recherche les opérateurs de priorité minimum (ici le "-"), on va obtenir (3 *) - (2) qui va générer ensuite une erreur de syntaxe ou de calcul.
    3 * -2 est une écriture incorrecte, normalement une erreur devrait être signalée, à mon avis si l'évaluateur autorise cette écriture il est incorrect.
    "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

  18. #18
    Expert éminent
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 385
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 385
    Par défaut
    C'est mathématiquement tout à fait correct, et le fait de l'accepter ou non dépend de la fonction de séparation (analyse lexicale), pas de la conversion en postfixe.

    Au passage, voici l'algorithme tant attendu: Utilise un ensemble de jetons d'entrée (infix), un ensemble de jetons en sortie (postfix) et une pile (pile).
    On peut considérer infix et postfix comme deux files FIFO.
    Types de jetons: nombre, parenthèse ouvrante, parenthèse fermante, opérateur.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    1.Pousser une parenthèse ouvrante '(' sur la pile.
    2.Ajouter une parenthèse fermante '(' à la fin de infix.
    3.Tant que la pile n'est pas vide:
    	Prendre un jeton de infix.
    	Si c'est un nombre
    		l'ajouter à la fin de postfix.
    	Si c'est une parenthèse ouvrante
    		La pousser sur la pile.
    	Si c'est un opérateur
    		Tant que le sommet de la pile est un opérateur de priorité supérieure ou égale à l'opérateur en cours
    			Dépiler l'opérateur de la pile et l'ajouter à la fin de postfix.
    		Pousser l'opérateur en cours sur la pile.
    	Si c'est une parenthèse fermante
    		Tant que le sommet de la pile n'est PAS une parenthèse ouvrante
    			Dépiler l'opérateur de la pile et l'ajouter à la fin de postfix.
    		Dépiler la parenthèse ouvrante de la pile et l'oublier.
    (Penser à remercier Deitel et Deitel pour le livre de C++)

    Donc, si on résume, au début, infix contient toutes sortes de jetons.
    La pile, elle, ne peut contenir que des opérateurs et des parenthèses ouvrantes
    postfix ne peut contenir que des nombres et des opérateurs.
    [U]SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.[/U]

    [I]"Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.[/I] -- [URL="http://blogs.msdn.com/oldnewthing/archive/2004/01/15/58973.aspx"]Raymond[/url] [url=http://blogs.msdn.com/b/oldnewthing/archive/2011/05/06/10161590.aspx]Chen[/URL].
    [SIZE="1"][URL="http://club.developpez.com/regles/#LIII-A"]Traduction obligatoire:[/URL] "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.[/SIZE]

  19. #19
    Membre confirmé
    Profil pro
    Inscrit en
    Novembre 2004
    Messages
    57
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2004
    Messages : 57
    Par défaut
    ok ba merci pour cet algorithme...
    je teste ca demain et jespere afficher ce probleme comme
    resolu...
    merci

  20. #20
    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
    Par défaut
    En infixe, 3*-2 devrait être rejeté.
    "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

+ Répondre à la discussion
Cette discussion est résolue.
Page 1 sur 2 12 DernièreDernière

Discussions similaires

  1. [XL-2010] Evaluer la valeur d'une variable à partir d'une chaine de caracteres
    Par batseb dans le forum Macros et VBA Excel
    Réponses: 1
    Dernier message: 02/11/2013, 10h43
  2. Evaluation d'une chaine de caractere
    Par kiwikiwi1 dans le forum Général Java
    Réponses: 2
    Dernier message: 18/04/2008, 11h46
  3. Réponses: 9
    Dernier message: 06/11/2007, 13h36
  4. evaluation d'une chaine de caracteres
    Par nath8050 dans le forum Langage
    Réponses: 1
    Dernier message: 26/04/2007, 15h49
  5. Controler une chaine de caracteres ou d'entiers?
    Par Le druide dans le forum C
    Réponses: 6
    Dernier message: 25/09/2003, 09h48

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