Le forum (ô combien francophone) des utilisateurs de Powerbuilder.
Pages: 1
Bonjour,
voici un évaluateur d'expressions basé sur l'algorithme Shunting-yard (triage) de Dijkstra permettant de transformer des expressions infixes (notation algébrique courante) en expressions postfixées (comme la "notation polonaise" sur les calculatrices HP; par exemple "2 + 2" devient "2 2 +").
Pas de panique, cette notation est seulement intermédiaire, elle sert à faciliter l’évaluation finale et éviter les ambigüités. Voici en 2 mots comment ça fonctionne :
- On commence par "tokeniser" l'expression en transformant la suite de caractères en items, les chiffres consécutifs en nombres, les lettres en identifiants, on zappe les espaces (premier nettoyage),
- puis on applique le "triage" aux tokens pour obtenir une notation "postfixée". L'avantage de la transformation est qu'elle permet de faire disparaître les parenthèses tout respectant la priorité des opérateurs. Le triage permet aussi d'obtenir un résultat "préfixé" commen en lisp (+ 2 2) mais la partie évaluation sait seulement traiter du postfixé (2 2 +).
- L'évaluation de l'expression est ensuite très simple : en utilisant une pile, il suffit d'empiler les termes de l'expression les uns après les autres et lorsqu'on rencontre un opérateur (+, - , *, /) ou une fonction, on dépile le nombre d'arguments nécessaires à l'opérateur ou à la fonction, on empile le résultat et on continue.
L'évaluateur supporte les opérations de base ainsi que l'utilisation de fonctions. J'ai implémenté une variante de l'algo permettant d'avoir des fonctions avec un nombre de de paramètres variables. L'algo original suppose que pour chaque fonction rencontrée on sait à priori combien elle prend de paramètres. Ici, le nombre de paramètres à dépiler est fonction du nombre de paramètres rencontrés entre les parenthèses lors du parsing.
Le parseur est facilement extensible : si on veut rajouter des fonctions, il suffit de patcher à 2 endroits dans isFunc() et dans evalFunc(). Le support des chaînes n'est pas fait mais est envisagé. Le support des variables est quasi fait (il manque le renseignement de la valeur des variables à l'évaluation).
C'est fait en pur PB (version 9) sans dépendance externe : il y a un objet nv_parser, une structure pour les tokens, 3 userobjects outil pour simuler une pile et une queue (à partir de tableaux), et une fenêtre de test.
(au passage : pour afficher la doc, le RichEdit en PB c'est de la m... où je ne sais pas m'y prendre ?)
Je joue pas mal dans les grammaires, parseurs, interpéteurs et compilateurs en ce moment et je voulais faire une petite expérimentation sur un langage de formules. Je publie ça sous demerdensiesich licence, mais je serai content de répondre à toute question, suggestion ou rapport de bug
C'est dispo chez moi, il n'y a pas vraiment de doc , mais le code est commenté.
Merci d'avoir lu jusque là
Edit: correction de typos + lien.
Dernière modification par seki (15-01-2013 10:56:32)
Hors ligne
Toujours aussi fort, le seki
Hors ligne
Merci La connaissance est l'une des rares choses qui augmente en la partageant...
Hors ligne
Bonjour,
merci pour cette mise à disposition.
Nous avons développé un évaluateur en C++ (objet COM) et pour comparer, j'ai regardé le tien.
J'ai un message "Cannot insert a document into rich text edit when the DisplayOnly property is set to true" à l'InsertDocument() (Booléen DisplayOnly à TRUE dans l'onglet Document du RTE, en le décochant plus de message). Pour info, je suis en PB 11.5.
Hors ligne
Geo a écrit:
J'ai un message "Cannot insert a document into rich text edit when the DisplayOnly property is set to true" à l'InsertDocument() (Booléen DisplayOnly à TRUE dans l'onglet Document du RTE, en le décochant plus de message). Pour info, je suis en PB 11.5.
Oui, pendant le dev j'ai ouvert brièvement une copie du projet avec PB11.5 et j'ai aussi eu ce message. Je ne sais pas d'où ça vient, c'est la première fois que j'utilise le rich edit.
Je pensait utiliser un .rtf pour pouvoir afficher une doc propre avec un peu de mise en forme mais c'est une mauvaise idée. Apparemment ça ne fonctionne pas pareil entre 9 et 11.5, et je n'ai pas exactement ce que je voulais à l'écran je que j'ai mis dans le rtf. En plus j'ai ouvert un coup le rtf avec word par erreur et ce sagouin m'a pourri le code rtf de la même manière qu'il fait un code de m... quand on s'en sert pour faire du html
Hors ligne
Geo a écrit:
Nous avons développé un évaluateur en C++ (objet COM) et pour comparer, j'ai regardé le tien.
Merci Il est possible qu'il y ait des différences dans l'évaluation des expressions sans parenthèses si vous n'avez pas les mêmes précédences d'opérateurs.
Et je n'ai quasiment pas codé de fonctions avant de publier, on pourrait en ajouter plein : min(), max(), les fonctions de trigo, ou des fonctions financières, il suffit de les mapper dans evalFunc()...
Si ça vous intéresse, je pourrais toujours publier des mises à jour.
Hors ligne
Juste pour dire : j'ai ajouté ce petit projet sur GitHub si vous souhaitez suivre les évolutions et / ou proposer des choses.
Depuis la première publication, j'ai ajouté le support des chaînes de caractères (délimitées par guillement simple, double ou backquote ``), des booléens, de quelques opérateurs et fonctions supplémentaires comme min(), max(), len() ou encore and, or, not.
J'ai une idée pour utiliser cet évaluateur sur une de nos applications, donc il est probable qu'il évolue encore, à commencer par une ré-écriture en objet des opérateurs et fonctions pour permettre une extension facile du moteur.
Hors ligne
Histoire de donner quelques nouvelles : la recherche avance et j'arrive à des résultats intéressants comme celui-ci :
Depuis la version initiale qui utilisait une machine à pile pour traiter l'expression une fois découpée en items
- je lis '2', j'empile '2'
- je lis '3', j'empile '3'
- je lis '+', je dépile '3' et '2', j'additionne et j'empile '5'
Maintenant le parcours de l'expression fabrique un arbre (arbre de syntaxe abraite) représentant complètement l'expression, puis le parcourt en évaluant chaque noeud mais en conservant la structure. Cela peut permettre d'afficher le détail du calcul et aussi de ne pas évaluer des branches non nécessaires. Par exemple la syntaxe
if(1=1, msgbox('vrai'), msgbox('faux'))
avant affichait 2 messages (car les arguments à if() étaient évalué avant le if(), comme pour toute autre fonction) et maintenant n'en affiche qu'un seul (on sait en évaluant '1=1' que seul la partie "vraie" est à évaluer)
Exemple d'expressions que je sais traiter:
- 33+42*2.5/(0.1-5)^2^3 -> 33,00031595167263415
- len(`string`) -> 6
- 2 - 1 <= 1 + 1 -> True
- +1 + --+1 -> 2
- min(len('a string')+7,-len("another"),4.2)+42 -> 35
- 'aa' + 42 -> 'aa42'
- 40 + '2' -> 42 (conversion magique si possible)
- '40' + '2' -> 402
- à cause de la conversion magique len('aa'+42) -> 4 mais len(40+'2') -> "len() can only take string argument at 1"
- 'aa'='bb' = false -> True
- 'aa'='bb' = vrai (vrai est une variable qui vaut le boolean true) -> False
- msgbox('length = ' + len("message")) -> affiche un message et retourne 1 (le n° du bouton cliqué)
- msgbox(if(true, 'true', 'false')) -> affiche 'true'
- if(true, msgbox('true'), msgbox('false')) -> affiche un seul 'true' (évaluation fénéante du if)
Edit:màj de la copie d'écran
Dernière modification par seki (19-03-2013 19:11:51)
Hors ligne
le vieux flashback, ça me rappelle mes cours de "compilation" : grammaire et cie...
Hors ligne
En effet je réutilise quelques notions présentes dans tous les cours de compilation (ça doit être du niveau license mais je ne suis pas allé jusque là).
Ça me sert à faire quelques expérimentations en vue d'appliquer des trucs que je lis par-ci par-là et de peut-être refondre un "langage" d'expressions interne d'un produit au taf. Et plus si affinités (en stock j'ai une grammaire powerscript presque complète avec plein d'idées pour aller avec).
Et c'est du pur PBScript en quelques objets : un userobject pour le parseur/évaluateur (19 méthodes), un userobject pour stocker chaque élément des expressions (8 méthodes presques pas utilisées - au début c'était une structure) et un dernier userobject pour simuler une pile (à base de tableau dynamique - 7 méthodes). Le reste est brodé autour des 3 premiers, sans pbni pour le moment, ça doit être réutilisable dans n'importe quel programme PB (le proto est fait en PB9).
Bref, c'est fun
Hors ligne
Pages: 1