Analyseur d’expression de calculateur Infix

La lecture sera longue, mais de toute façon, je vais partager avec vous l’algorithme que j’utilise pour parsingr une expression infixe et le stocker sous la forme d’un arbre binary. Pas stack, mais arbre binary. Analyser qui donnera facilement l’ordre postfix. Je ne dis pas que c’est le meilleur algorithme, mais cela fonctionne pour mon langage de script.

L’algorithme:

Nous avons une méthode qui fonctionne sur un “nœud actuel” d’un arbre binary et une “expression courante”. Les nœuds contiennent un champ “data” et un champ “type”.

Etape 1: Des choses simples, telles que “4”, vont directement dans le nœud, et nous spécifions que le type doit être “DATA”, c’est-à-dire. utiliser cette information telle quelle.

Étape 2: Maintenant, considérons l’expression suivante:

 a) 2 + 3 

cela sera transformé dans l’arbre binary suivant:

  + / \ 2 3 

Ainsi, les opérateurs vont dans les nœuds et les opérandes vont dans les feuilles. Transformer l’expression a) dans l’arborescence est assez simple: recherchez l’opérateur, insérez le nœud “actuel” de l’arborescence, spécifiez le type du nœud qui sera l’opérateur “PLUS”, et ce qu’il en rest ira dans l’arborescence. dans la partie gauche du noeud, ce qui est juste va dans l’arbre de droite. Sympa et simple, en utilisant les informations de la phase 1, les deux feuilles seront des feuilles “DONNEES” de valeur 2 et 3.

Étape 3: Mais pour une expression plus complexe:

 b) 2 * 3 + 4 

L’arbre sera:

  + / \ 4 * / \ 2 3 

Nous devons donc modifier l’algorithme ci-dessus comme suit: Trouvez le premier opérateur qui a la priorité la plus élevée (en considérant les directives c ++ … la priorité de + (plus) et – (moins) est égale à 6, alors que la priorité de * (multiplier), / (divide) et% (modulo est égal à 5) dans l’expression, divisez l’expression en deux parties (avant l’opérande ayant la priorité la plus élevée et après l’opérande ayant la priorité la plus élevée) et appelez récursivement la méthode des deux parties tout en plaçant l’opérateur avec la priorité la plus élevée dans le nœud actuel. Nous créons donc un arbre avec hdata comme:

  + / \ / call method with "4" call method with "2*3" 

et à ce stade, nous retombons à “Stage 2” pour l’appel (“2 * 3”) et à “Stage 1” pour l’appel “4”.

Étape 4: Que se passe-t-il s’il y a des parenthèses dans l’expression? Tel que

 c) 2 * (3 + 4) 

Cela nous donnera l’arbre:

  * / \ 2 + / \ 3 4 

Nous modifions l’algorithme pour qu’il ressemble à:

• pendant que l’expression courante est incluse dans une parenthèse, supprimez-la et redémarrez l’algorithme. Faites attention. (2 + 3 * 4 + 5) est considéré comme inclus dans une parnéthèse alors que (2 + 3) * (4 + 5) n’est PAS. Ainsi, il ne s’agit pas uniquement des caractères de début et de fin de l’expression, mais vous devez en fait compter les parantheses. (c’est une méthode récursive, n’ayez pas peur de la première étape …)

• Trouvez maintenant le premier opérateur avec la plus haute priorité en dehors des parenthèses de l’expression. Encore une fois, prenez les côtés gauche et droit de l’expression et appelez la méthode encore et encore jusqu’à ce que vous vous retrouviez au “Stage 1” c’est-à-dire. avec un seul élément de données.

  Il s’agit maintenant d’un algorithme pour une expression composée de nombres et d’opérateurs en clair. Pour des informations plus complexes, vous devrez peut-être les affiner pour répondre à vos besoins. Si vous le jugez utile, consultez https://sourceforge.net/p/nap-script/mercurial/ci/default/tree/comstackr/interpreter.cpp . Cela contient une implémentation complète (en C) de l’algorithme ci-dessus en ce qui concerne des notions plus complexes (variables, appels de méthodes, opérateurs postfix / prefix, etc.). La méthode est build_expr_tree, commence à la ligne 1327.

La méthode de descente récursive est le moyen le plus simple d’implémenter manuellement un parsingur d’expression correct. Ici, la stack de langages de programmation fait la même chose que la stack explicite que vous essayez d’utiliser. Il existe de nombreux exemples de RD avec Google, et tout bon livre de compilateur en contient.

La page Wikipedia liée montre un parsingur, mais pas comment append une évaluation. Vous trouverez ci-dessous un évaluateur d’expression rudimentaire complet en C. Il pourrait être facilement encapsulé dans une classe C ++, les globals devenant des variables d’instance. Il manque des fonctionnalités dont vous auriez besoin dans un système de production. Par exemple, lorsqu’il trouve une erreur, il se ferme. Les exceptions C ++ vous permettront facilement de décompresser et de continuer. Cela nécessite également des protections contre le dépassement numérique, la division par zéro, etc., ce que vous savez évidemment faire.

L’idée de descente récursive est de transformer la grammaire de la langue souhaitée en une forme appelée LL (1). Lorsque cela est fait, il existe des règles fixes – garanties de fonctionner à chaque fois – pour transformer les règles de grammaire en procédures. Je l’ai fait ci-dessous à la main. Il existe des outils pour le faire automatiquement.

Cet évaluateur est donc très facile à étendre. Ajoutez simplement la règle de grammaire nécessaire, puis implémentez les améliorations nécessaires dans l’parsingur, l’parsingur et le code d’évaluation. Par exemple, une règle de fonction intégrée serait unsigned_factor -> FUNCTION_NAME ( expr ) , où l’parsingur reconnaît tous les noms de fonctions sous le même jeton et la fonction unsigned_factor C est augmentée pour parsingr et calculer les valeurs.

Je devais inclure un petit scanner pour obtenir un programme de travail. Notez que plus de la moitié du code est le scanner. Les parsingurs syntaxiques de base RD sont simples.

Elles deviennent plus complexes si vous ajoutez une récupération d’erreur: la capacité intelligente de sauter une erreur après une erreur et de poursuivre l’parsing, tout en émettant un seul message d’erreur rédigé avec précision. Mais là encore, cela ajoute beaucoup de complexité à tout parsingur.

 // Bare bones scanner and parser for the following LL(1) grammar: // expr -> term { [+-] term } ; An expression is terms separated by add ops. // term -> factor { [*/] factor } ; A term is factors separated by mul ops. // factor -> unsigned_factor ; A signed factor is a factor, // | - unsigned_factor ; possibly with leading minus sign // unsigned_factor -> ( expr ) ; An unsigned factor is a parenthesized expression // | NUMBER ; or a number // // The parser returns the floating point value of the expression. #include  #include  // The token buffer. We never check for overflow! Do so in production code. char buf[1024]; int n = 0; // The current character. int ch; // The look-ahead token. This is the 1 in LL(1). enum { ADD_OP, MUL_OP, LEFT_PAREN, RIGHT_PAREN, NUMBER, END_INPUT } look_ahead; // Forward declarations. void init(void); void advance(void); double expr(void); void error(char *msg); // Parse expressions, one per line. int main(void) { init(); while (1) { double val = expr(); printf("val: %f\n", val); if (look_ahead != END_INPUT) error("junk after expression"); advance(); // past end of input mark } return 0; } // Just die on any error. void error(char *msg) { fprintf(stderr, "Error: %s. I quit.\n", msg); exit(1); } // Buffer the current character and read a new one. void read() { buf[n++] = ch; buf[n] = '\0'; // Terminate the ssortingng. ch = getchar(); } // Ignore the current character. void ignore() { ch = getchar(); } // Reset the token buffer. void reset() { n = 0; buf[0] = '\0'; } // The scanner. A tiny deterministic finite automaton. int scan() { reset(); START: switch (ch) { case ' ': case '\t': case '\r': ignore(); goto START; case '-': case '+': read(); return ADD_OP; case '*': case '/': read(); return MUL_OP; case '(': read(); return LEFT_PAREN; case ')': read(); return RIGHT_PAREN; case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': read(); goto IN_LEADING_DIGITS; case '\n': ch = ' '; // delayed ignore() return END_INPUT; default: error("bad character"); } IN_LEADING_DIGITS: switch (ch) { case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': read(); goto IN_LEADING_DIGITS; case '.': read(); goto IN_TRAILING_DIGITS; default: return NUMBER; } IN_TRAILING_DIGITS: switch (ch) { case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': read(); goto IN_TRAILING_DIGITS; default: return NUMBER; } } // To advance is just to replace the look-ahead. void advance() { look_ahead = scan(); } // Clear the token buffer and read the first look-ahead. void init() { reset(); ignore(); // junk current character advance(); } double unsigned_factor() { double rtn = 0; switch (look_ahead) { case NUMBER: sscanf(buf, "%lf", &rtn); advance(); break; case LEFT_PAREN: advance(); rtn = expr(); if (look_ahead != RIGHT_PAREN) error("missing ')'"); advance(); break; default: error("unexpected token"); } return rtn; } double factor() { double rtn = 0; // If there is a leading minus... if (look_ahead == ADD_OP && buf[0] == '-') { advance(); rtn = -unsigned_factor(); } else rtn = unsigned_factor(); return rtn; } double term() { double rtn = factor(); while (look_ahead == MUL_OP) { switch(buf[0]) { case '*': advance(); rtn *= factor(); break; case '/': advance(); rtn /= factor(); break; } } return rtn; } double expr() { double rtn = term(); while (look_ahead == ADD_OP) { switch(buf[0]) { case '+': advance(); rtn += term(); break; case '-': advance(); rtn -= term(); break; } } return rtn; } 

Et lancer le programme:

 1 + 2 * 3 val: 7.000000 (1 + 2) * 3 val: 9.000000