Équation (expression) analyseur avec priorité?

Le manœuvre de triage algorithme est le bon outil pour cela. Wikipédia est vraiment confus à ce sujet, mais, fondamentalement, l'algorithme fonctionne comme ceci:

dites, vous voulez évaluer 1 + 2 * 3 + 4. Intuitivement, vous "savez" que vous devez faire le 2 * 3 d'abord, mais comment obtenez-vous ce résultat? La clé est de réaliser que lorsque vous scannez la chaîne de gauche à droite, vous évaluerez un opérateur lorsque l'opérateur qui suit elle a une priorité inférieure (ou égale à). Dans le contexte de l'exemple, voici ce que vous voulez faire:

1. regardez: 1 + 2, Ne faites rien.
2. regardez maintenant 1 + 2 * 3 toujours rien.
3. Maintenant, regardez 1 + 2 * 3 + 4 maintenant, vous savez que 2 * 3 doit être évalué parce que le prochain opérateur a priorité inférieure.

comment implémentez-vous cela?

vous voulez avoir deux piles, une pour les nombres, et une autre pour les opérateurs. Vous mettez des numéros sur la pile tout le temps. Vous comparez chaque nouvel opérateur avec celui qui se trouve en haut de la pile, si celui qui se trouve en haut de la pile a une priorité plus élevée, vous le retirez de la pile de l'opérateur, vous retirez les opérandes de la pile de numéros, vous appliquez l'opérateur et vous poussez le résultat sur la pile de numéros. Maintenant, vous répétez la comparaison avec le haut de l'opérateur de pile.

de retour au exemple, cela fonctionne comme ceci:

N = [ ] Ops = []

• Lire 1. N = [1], Np = [ ]
• Read +. N = [1], Np = [+]
• Lire 2. N = [12], Ops = [ + ]
• Lire * . N = [1 2], Np = [+ *]
• Lire 3. N = [1 2 3], Ops = [ + * ]
• Read +. N = [1 2 3], Ops = [+ *]
  • Pop 3, 2 et exécuter 2 * 3, et pousser le résultat sur N. N = [16], Ops = [ + ]
  • + est laissé associatif, donc vous voulez pop 1, 6 ainsi et exécuter le +. N = [7], Ops = [].
  • pousse finalement le [+] sur la pile de l'opérateur. N = [7], Ops = [+].
• Lire 4. N = [7 4]. Op.]+[ =
• vous êtes à court d'entrées, donc vous voulez vider les piles maintenant. Sur lequel vous obtiendrez la 11.

là, ce n'est pas si difficile, n'est-ce pas? Et il ne fait pas d'invocations à des grammaires ou des générateurs de parser.

http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm

Très bonne explication des différentes approches:

• Recursive-descent recursive-recognition
• La manœuvre de triage algorithme
• la solution classique
• priorité escalade

écrit en langage simple et en pseudo-code.

j'aime 'priorité d'escalade".

il y a un bel article ici sur la combinaison d'un simple analyseur recursive-descent avec l'analyse opérateur-priority. Si vous avez été récemment écrit des analyseurs, il devrait être très intéressant et instructif à lire.

il y a longtemps, j'ai inventé mon propre algorithme d'analyse, que je ne pouvais trouver dans aucun livre sur l'analyse (comme le livre du Dragon). En regardant les indicateurs de l'algorithme de triage, je vois la ressemblance.

il y a environ 2 ans, j'ai fait un post à ce sujet, complet avec le code source Perl, sur http://www.perlmonks.org/?node_id=554516 . Il est facile de passer à d'autres langues: la première implémentation que j'ai faite était en assembleur Z80.

Il est idéal pour le calcul avec des nombres, mais vous pouvez l'utiliser pour produire un arbre d'analyse si vous devez.

Update parce que plus de gens peuvent lire (ou exécuter) Javascript, j'ai réimplementé mon analyseur en Javascript, après que le code a été réorganisé. L'analyseur complet est en dessous de 5K de code Javascript (environ 100 lignes pour l'analyseur, 15 lignes pour une fonction de wrapper) y compris le rapport d'erreur, et les commentaires.

vous pouvez trouver une démo en direct à http://users.telenet.be/bartl/expressionParser/expressionParser.html .

// operator table
var ops = {
   '+'  : {op: '+', precedence: 10, assoc: 'L', exec: function(l,r) { return l+r; } },
   '-'  : {op: '-', precedence: 10, assoc: 'L', exec: function(l,r) { return l-r; } },
   '*'  : {op: '*', precedence: 20, assoc: 'L', exec: function(l,r) { return l*r; } },
   '/'  : {op: '/', precedence: 20, assoc: 'L', exec: function(l,r) { return l/r; } },
   '**' : {op: '**', precedence: 30, assoc: 'R', exec: function(l,r) { return Math.pow(l,r); } }
};

// constants or variables
var vars = { e: Math.exp(1), pi: Math.atan2(1,1)*4 };

// input for parsing
// var r = { string: '123.45+33*8', offset: 0 };
// r is passed by reference: any change in r.offset is returned to the caller
// functions return the parsed/calculated value
function parseVal(r) {
    var startOffset = r.offset;
    var value;
    var m;
    // floating point number
    // example of parsing ("lexing") without aid of regular expressions
    value = 0;
    while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
    if(r.string.substr(r.offset, 1) == ".") {
        r.offset++;
        while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
    }
    if(r.offset > startOffset) {  // did that work?
        // OK, so I'm lazy...
        return parseFloat(r.string.substr(startOffset, r.offset-startOffset));
    } else if(r.string.substr(r.offset, 1) == "+") {  // unary plus
        r.offset++;
        return parseVal(r);
    } else if(r.string.substr(r.offset, 1) == "-") {  // unary minus
        r.offset++;
        return negate(parseVal(r));
    } else if(r.string.substr(r.offset, 1) == "(") {  // expression in parens
        r.offset++;   // eat "("
        value = parseExpr(r);
        if(r.string.substr(r.offset, 1) == ")") {
            r.offset++;
            return value;
        }
        r.error = "Parsing error: ')' expected";
        throw 'parseError';
    } else if(m = /^[a-z_][a-z0-9_]*/i.exec(r.string.substr(r.offset))) {  // variable/constant name        
        // sorry for the regular expression, but I'm too lazy to manually build a varname lexer
        var name = m[0];  // matched string
        r.offset += name.length;
        if(name in vars) return vars[name];  // I know that thing!
        r.error = "Semantic error: unknown variable '" + name + "'";
        throw 'unknownVar';        
    } else {
        if(r.string.length == r.offset) {
            r.error = 'Parsing error at end of string: value expected';
            throw 'valueMissing';
        } else  {
            r.error = "Parsing error: unrecognized value";
            throw 'valueNotParsed';
        }
    }
}

function negate (value) {
    return -value;
}

function parseOp(r) {
    if(r.string.substr(r.offset,2) == '**') {
        r.offset += 2;
        return ops['**'];
    }
    if("+-*/".indexOf(r.string.substr(r.offset,1)) >= 0)
        return ops[r.string.substr(r.offset++, 1)];
    return null;
}

function parseExpr(r) {
    var stack = [{precedence: 0, assoc: 'L'}];
    var op;
    var value = parseVal(r);  // first value on the left
    for(;;){
        op = parseOp(r) || {precedence: 0, assoc: 'L'}; 
        while(op.precedence < stack[stack.length-1].precedence ||
              (op.precedence == stack[stack.length-1].precedence && op.assoc == 'L')) {  
            // precedence op is too low, calculate with what we've got on the left, first
            var tos = stack.pop();
            if(!tos.exec) return value;  // end  reached
            // do the calculation ("reduce"), producing a new value
            value = tos.exec(tos.value, value);
        }
        // store on stack and continue parsing ("shift")
        stack.push({op: op.op, precedence: op.precedence, assoc: op.assoc, exec: op.exec, value: value});
        value = parseVal(r);  // value on the right
    }
}

function parse (string) {   // wrapper
    var r = {string: string, offset: 0};
    try {
        var value = parseExpr(r);
        if(r.offset < r.string.length){
          r.error = 'Syntax error: junk found at offset ' + r.offset;
            throw 'trailingJunk';
        }
        return value;
    } catch(e) {
        alert(r.error + ' (' + e + '):\n' + r.string.substr(0, r.offset) + '<*>' + r.string.substr(r.offset));
        return;
    }    
}

Il serait utile si vous pouviez décrire la grammaire que vous utilisez actuellement à analyser. Sonne comme le problème pourrait se trouver là!

Edit:

le fait que vous ne comprenez pas la question de grammaire et que "vous avez écrit ceci à la main" explique très probablement pourquoi vous avez des problèmes avec les expressions du formulaire. 1+11*5" (c'est-à-dire avec la préséance de l'opérateur). Googler pour "grammaire pour les expressions arithmétiques", par exemple, devrait donner de bons résultats pointeur. Une telle grammaire n'a pas besoin d'être compliquée:

<Exp> ::= <Exp> + <Term> |
          <Exp> - <Term> |
          <Term>

<Term> ::= <Term> * <Factor> |
           <Term> / <Factor> |
           <Factor>

<Factor> ::= x | y | ... |
             ( <Exp> ) |
             - <Factor> |
             <Number>

ferait l'affaire par exemple, et peut être trivialement augmentée pour prendre soin de quelques expressions plus complexes (y compris les fonctions par exemple, ou pouvoirs...).

je vous suggère de jeter un oeil à ce fil, par exemple.

presque toutes les introductions aux grammaires/parsing traitent les expressions arithmétiques comme un exemple.

noter que l'utilisation d'une grammaire n'implique pas du tout l'utilisation d'un outil spécifique ( a la Yacc, Bison,...). En effet, vous utilisez certainement déjà la grammaire suivante:

<Exp>  :: <Leaf> | <Exp> <Op> <Leaf>

<Op>   :: + | - | * | /

<Leaf> :: <Number> | (<Exp>)

(ou quelque chose du genre) sans le savoir!

Avez-vous pensé à utiliser des Stimuler l'Esprit ? Il vous permet d'écrire des grammaires de type EBNF en C++ comme ceci:

group       = '(' >> expression >> ')';
factor      = integer | group;
term        = factor >> *(('*' >> factor) | ('/' >> factor));
expression  = term >> *(('+' >> term) | ('-' >> term));

comme vous le dites, il n'est pas nécessaire de revenir sur votre question. La réponse est trois choses: notation Postfix plus algorithme de triage Plus évaluation de L'expression Postfix:

1). Notation Postfix = inventé pour éliminer la nécessité d'une spécification explicite de priorité. Lire la suite sur le net mais voici l'essentiel: infix expression ( 1 + 2 ) * 3 bien que facile à lire pour les humains et le processus pas très efficace pour l'informatique via la machine. Qu'est-ce que? Simple règle qui dit "réécrire l'expression en la cachant en priorité, puis toujours la traiter de gauche à droite". Ainsi infix (1 + 2 ) * 3 devient un postfix 12+3*. POST parce que l'opérateur est toujours placé après les opérandes.

2). L'évaluation de postfix expression. Facile. Lire les nombres sur la chaîne postfix. Pousser sur une pile jusqu'à ce qu'un opérateur est vu. Vérifier le type d'opérateur-unaire? binaire? tertiaire? Pop autant d'opérandes de la pile que nécessaire pour évaluer cet opérateur. Évaluer. Pousser résultat arrière sur pile! Et u r presque terminé. Continuez à le faire jusqu'à ce que la pile n'ait qu'une entrée = valeur U R à la recherche.

Let's do ( 1 + 2 ) * 3 qui est dans postfix est "12+3*". Lire le premier chiffre = 1. Push sur la pile. Lire la suite. Nombre = 2. Push sur la pile. Lire la suite. Opérateur. Lequel? +. De quel genre? Binaire = nécessite deux opérandes. Pop stack deux fois = argright est 2 et argleft est 1. 1 + 2 est 3. Poussez 3 de nouveau sur la pile. Lire la suite de postfix chaîne. Ses un certain nombre. 3.Pousser. Lire la suite. Opérateur. Lequel? *. De quel genre? Binaire = nécessite deux nombres - > pop pile deux fois. Première de la pop dans argright, la deuxième fois en argleft. Évaluer l'opération - 3 fois 3 est 9.Appuyez sur 9 sur stack. Lire le prochain postfix char. C'est la valeur null. Fin de saisie. Pop stack onec = c'est ta réponse.

3). Shunting Yard est utilisé pour transformer l'expression humaine (facilement) lisible infix en une expression postfix (aussi humaine facilement lisible après une certaine pratique). Facile à coder manuellement. Voir les commentaires ci-dessus et net.

Est-il une langue que vous voulez utiliser? ANTLR vous permettra de le faire à partir d'une perspective Java. Adrian Kuhn a un excellent writeup sur la façon d'écrire une grammaire exécutable dans Ruby; en fait, son exemple est presque exactement votre expression arithmétique exemple.

Ça dépend "général" vous voulez qu'il soit.

si vous voulez qu'il soit vraiment vraiment général comme être capable d'analyser les fonctions mathématiques aussi bien que sin(4+5)*cos(7^3) vous aurez probablement besoin d'un arbre de parse .

dans lequel, je ne pense pas qu'une mise en œuvre complète soit approprié d'être collé ici. Je vous suggère de vérifier l'un des tristement célèbres Livre du Dragon ".

mais si vous voulez juste le support de priorité , alors vous pouvez le faire en convertissant d'abord l'expression en forme de postfix dans lequel un algorithme que vous pouvez copier-coller devrait être disponible à partir de google ou je pense que vous pouvez le coder vous-même avec un arbre binaire.

Quand vous l'avez dans postfix forme, alors c'est du gâteau à partir de là, puisque vous comprenez déjà comment la pile d'aide.

je suggère de tricher et d'utiliser le " algorithme de triage . C'est un moyen facile d'écrire un simple analyseur de type calculatrice et prend priorité en compte.

si vous voulez correctement tokenise choses et avoir des variables, etc. impliqué alors j'irais de l'avant et écrire un analyseur de descente récursive comme suggéré par d'autres ici, cependant si vous avez simplement besoin d'un analyseur de style de calculatrice alors cet algorithme devrait être suffisant :-)

j'ai trouvé ceci sur la PIClist à propos du algorithme de triage de triage :

Harold écrit:

je me souviens avoir lu, il y a longtemps, un algorithme qui convertissait expressions algébriques à RPN pour une évaluation facile. Chaque valeur infix ou l'exploitant ou la parenthèse était représenté par un wagon de chemin de fer sur un piste. Un type de voiture divisée à une autre voie et l'autre continué tout droit devant. Je ne me souviens pas des détails (évidemment!), mais toujours pensé que c' ce serait intéressant de coder. C'est quand j'écrivais 6800 (pas 68000) code d'assemblage.

C'est le " shunting yard algorithm" et c'est ce que la plupart des analyseurs de machine utiliser. Voir l'article sur parsing in Wikipedia. Un moyen facile de coder le la Cour de triage algorithm doit utiliser deux pile. L'une est la pile "push" et l'autre le "réduire" ou "résultat" pile. Exemple:

pstack = () / / empty rstack = () input: 1+2*3 priorité = 10 // la plus basse réduire = 0 // ne pas réduire

démarrer: token '1': isnumber, mettre en jeton pstack (push)'+': isoperator placer priorité=2 si priorité < previous_operator_precedence alors réduire() // voir ci-dessous mis '+' dans pstack (push) jeton '2': isnumber, mettre le jeton pstack (push)'*': isoperator, set priority=1, put in pstack (pousser) // vérifier l'ordre de priorité comme suit: // au-dessus du jeton '3': isnumber, mettre en pstack (push) fin de l'entrée, besoin de réduire (le but est de vider le sac) réduire() //fait

pour réduire, pop éléments de la poussée empiler et les mettre dans le résultat empiler, toujours permuter les 2 premiers éléments sur pstack s'ils sont de la forme "numéro de l'exploitant":

pstack: '1' '+' '2' ' ' '3' rtack: () ... pstack: () rstack: '3' '2' ' ' '1' '+'

si l'expression aurait été:

1*2+3

alors le déclencheur de réduction aurait été la lecture du jeton '+' qui a une précession plus faible que la '*' déjà poussé, de sorte qu'il aurait fait:

pstack: '1' ' ' '2' rstack: ()... pstack: () rstack: '1' '2' ' '

et ensuite poussé '+' et '3' et puis enfin réduit:

pstack: '+ ''3' rstack: '1' '2' ' ' ... pstack: () rstack: '1' '2' ' ' '3' '+'

donc la version courte est: push numbers, lorsque vous poussez les opérateurs, Vérifiez la priorité de l'ancien opérateur. Si elle était supérieure à celle de l'opérateur c'est être poussé maintenant, d'abord laisser réduire, puis pousser le courant opérateur. Pour gérer parens simplement enregistrer la préséance du "précédent" l'opérateur, et mettez une marque sur le sac cela dit la réduire algorithm à arrêter de réduire en résolvant l'intérieur d'une paire de parenthèse. La parenthèse fermante déclenche une réduction de la fin de l'entrée, et supprime également les ouvrir parenthèse marque de la pstack, et restaure la précédente opération" priorité donc l'analyse peut continuer après la clôture parenthèse où il la gauche hors. Cela peut être fait avec la récursivité ou sans (astuce: utiliser une pile pour stocker la préséance précédente lorsque rencontre avec un" ("...). Le la version généralisée est à utiliser un analyseur générateur de mise en œuvre shunting yard algorithm, F. ex. utiliser Yacc ou bison ou taccle (TCL analogue de yacc).

Peter

- Adam

j'ai posté la source pour un ultra compact (1 classe, < 10 KiB) Java Math Evaluator sur mon site web. Il s'agit d'un analyseur de descente récursif du type qui a causé l'explosion crânienne pour l'affiche de la réponse acceptée.

il supporte la priorité complète, la parenthèse, les variables nommées et les fonctions à argument unique.

j'ai publié un analyseur d'expressions basé sur l'algorithme Dijkstra's Shunting Yard , selon les termes de la licence Apache 2.0 :

http://projects.congrace.de/exp4j/index.html

une autre ressource pour l'analyse de priorité est l'entrée opérateur-analyseur de priorité sur Wikipedia. Couvre l'algorithme shunting yard de Dijkstra, et un algorithme tree alternate, mais plus particulièrement couvre un algorithme de remplacement de macro vraiment simple qui peut être trivialement mis en œuvre devant n'importe quel analyseur ignorant de priorité:

#include <stdio.h>
int main(int argc, char *argv[]){
  printf("((((");
  for(int i=1;i!=argc;i++){
    if(argv[i] && !argv[i][1]){
      switch(argv[i]){
      case '^': printf(")^("); continue;
      case '*': printf("))*(("); continue;
      case '/': printf("))/(("); continue;
      case '+': printf(")))+((("); continue;
      case '-': printf(")))-((("); continue;
      }
    }
    printf("%s", argv[i]);
  }
  printf("))))\n");
  return 0;
}

Invoquez - le comme:

$ cc -o parenthesise parenthesise.c
$ ./parenthesise a \* b + c ^ d / e
((((a))*((b)))+(((c)^(d))/((e))))

qui est impressionnant dans sa simplicité, et très compréhensible.

j'ai implémenté un recursive descent parser en Java dans le projet MathEclipse Parser . Il pourrait également être utilisé comme un Google Web Toolkit module

je travaille actuellement sur une série d'articles construisant un analyseur d'expression régulière comme un outil d'apprentissage pour les modèles de conception et de programmation lisible. Vous pouvez jeter un oeil à readablecode . L'article présente une utilisation claire de l'algorithme shunting yards.

j'ai écrit un analyseur d'expression en F# et blogué à ce sujet ici . Il utilise l'algorithme shunting yard, mais au lieu de convertir infix en RPN, j'ai ajouté une deuxième pile pour accumuler les résultats des calculs. Il gère correctement la priorité des opérateurs, mais ne supporte pas les opérateurs unaires. J'ai écrit ça pour apprendre le F#, pas pour apprendre l'analyse des expressions.

une solution de Python en pyparsing peut être trouvée ici . La notation parsing infix avec divers opérateurs avec priorité est assez fréquente, et donc pyparsing comprend également le constructeur d'expressions infixNotation (anciennement operatorPrecedence ). Avec elle, vous pouvez facilement définir des expressions booléennes en utilisant "et", "ou", "pas", par exemple. Ou vous pouvez étendre votre arithmétique à quatre fonctions pour utiliser d'autres opérateurs, tels que ! pour factoriel, ou " % " pour module, ou ajouter P et C les opérateurs doivent calculer les permutations et les combinaisons. Vous pouvez écrire un analyseur infix pour la notation matricielle, qui inclut la gestion des opérateurs' -1 'ou' T ' (pour l'inversion et la transposition). L'exemple operatorpence d'un analyseur 4 fonctions (avec '!'juste pour le plaisir) est ici et un plus complet de l'analyseur et l'évaluateur est ici .

je sais que c'est une réponse tardive, mais je viens d'écrire un petit parser qui permet à tous les opérateurs (prefix, postfix et infix-left, infix-right et non associatif) d'avoir une priorité arbitraire.

je vais étendre ceci pour un langage avec support DSL arbitraire, mais je voulais juste faire remarquer qu'on n'a pas besoin d'analyseurs personnalisés pour la priorité de l'opérateur, on peut utiliser un analyseur généralisé qui n'a pas besoin de tables du tout, et regarde juste la priorité de chaque opératrice telle qu'elle apparaît. Les gens ont mentionné des analyseurs Pratt personnalisés ou des analyseurs shunting yard qui peuvent accepter des entrées illégales - celui-ci n'a pas besoin d'être personnalisé et (à moins qu'il y ait un bogue) n'acceptera pas de mauvaises entrées. Il n'est pas complet en un sens, il a été écrit pour tester l'algorithme et son entrée est sous une forme qui nécessitera un prétraitement, mais il y a des commentaires qui le rendent clair.

notez que certains types courants d'opérateurs sont absents par exemple le type de opérateur utilisé pour indexer ie table[index] ou appeler une fonction(paramètre-expression, ...) Je vais les ajouter, mais pensez aux deux comme des opérateurs postfix où ce qui se trouve entre les délimiteurs " ["et"] " ou " ("et") " est analysé avec une instance différente de l'analyseur d'expressions. Désolé d'avoir laissé, mais le suffixe partie est en ajoutant le reste sera probablement presque le double de la taille du code.

puisque l'analyseur n'est que 100 lignes de code de raquette, peut-être que je devrais juste le coller ici, j'espère que ce n'est pas plus long que stackoverflow permet.

quelques détails sur les décisions arbitraires:

si un opérateur postfix de priorité faible est en compétition pour les mêmes blocs infix qu'un opérateur de préfixe de priorité faible, l'opérateur de préfixe gagne. Cela n'apparaît pas dans la plupart des langues car la plupart n'ont pas d'opérateurs postfix de priorité faible. - par exemple: ((Données A) (à gauche 1 +) (avant 2 Non)(données b) (après 3 !) (à gauche 1 +) (données C)) est a+pas b!+C où il n'y a pas d'opérateur de préfixe et ! est l'opérateur postfix et les deux ont priorité que + donc ils veulent grouper de manière incompatible soit comme (a+b pas!)+C ou comme a+(pas b!+C) dans ces cas, l'opérateur de préfixe gagne toujours, donc le second est la façon dont il part

non associatif des opérateurs infixes sont vraiment là, de sorte que vous n'avez pas à faire semblant que les opérateurs qui retournent des types différents qu'ils ne prennent du sens ensemble, mais sans avoir différents types d'expressions pour chacun c'est un kludge. Ainsi, dans cet algorithme, les opérateurs non-associatifs refusent de s'associer non seulement avec eux-mêmes, mais avec tout opérateur ayant la même priorité. C'est un cas courant car < < = = = = > = etc ne s'associent pas dans la plupart des langues.

la question de savoir comment différents types d'opérateurs (à gauche, préfixe etc) rompent les liens sur la priorité est une question qui ne devrait pas se poser, parce qu'il n'est pas vraiment logique de donner des opérateurs de différents types la même priorité. Cet algorithme fait quelque chose dans ces cas-là, mais je ne me soucie même pas de comprendre exactement quoi parce qu'une telle grammaire est une mauvaise idée en premier lieu.

#lang racket
;cool the algorithm fits in 100 lines!
(define MIN-PREC -10000)
;format (pre prec name) (left prec name) (right prec name) (nonassoc prec name) (post prec name) (data name) (grouped exp)
;for example "not a*-7+5 < b*b or c >= 4"
;which groups as: not ((((a*(-7))+5) < (b*b)) or (c >= 4))"
;is represented as '((pre 0 not)(data a)(left 4 *)(pre 5 -)(data 7)(left 3 +)(data 5)(nonassoc 2 <)(data b)(left 4 *)(data b)(right 1 or)(data c)(nonassoc 2 >=)(data 4)) 
;higher numbers are higher precedence
;"(a+b)*c" is represented as ((grouped (data a)(left 3 +)(data b))(left 4 *)(data c))

(struct prec-parse ([data-stack #:mutable #:auto]
                    [op-stack #:mutable #:auto])
  #:auto-value '())

(define (pop-data stacks)
  (let [(data (car (prec-parse-data-stack stacks)))]
    (set-prec-parse-data-stack! stacks (cdr (prec-parse-data-stack stacks)))
    data))

(define (pop-op stacks)
  (let [(op (car (prec-parse-op-stack stacks)))]
    (set-prec-parse-op-stack! stacks (cdr (prec-parse-op-stack stacks)))
    op))

(define (push-data! stacks data)
    (set-prec-parse-data-stack! stacks (cons data (prec-parse-data-stack stacks))))

(define (push-op! stacks op)
    (set-prec-parse-op-stack! stacks (cons op (prec-parse-op-stack stacks))))

(define (process-prec min-prec stacks)
  (let [(op-stack (prec-parse-op-stack stacks))]
    (cond ((not (null? op-stack))
           (let [(op (car op-stack))]
             (cond ((>= (cadr op) min-prec) 
                    (apply-op op stacks)
                    (set-prec-parse-op-stack! stacks (cdr op-stack))
                    (process-prec min-prec stacks))))))))

(define (process-nonassoc min-prec stacks)
  (let [(op-stack (prec-parse-op-stack stacks))]
    (cond ((not (null? op-stack))
           (let [(op (car op-stack))]
             (cond ((> (cadr op) min-prec) 
                    (apply-op op stacks)
                    (set-prec-parse-op-stack! stacks (cdr op-stack))
                    (process-nonassoc min-prec stacks))
                   ((= (cadr op) min-prec) (error "multiply applied non-associative operator"))
                   ))))))

(define (apply-op op stacks)
  (let [(op-type (car op))]
    (cond ((eq? op-type 'post)
           (push-data! stacks `(,op ,(pop-data stacks) )))
          (else ;assume infix
           (let [(tos (pop-data stacks))]
             (push-data! stacks `(,op ,(pop-data stacks) ,tos))))))) 

(define (finish input min-prec stacks)
  (process-prec min-prec stacks)
  input
  )

(define (post input min-prec stacks)
  (if (null? input) (finish input min-prec stacks)
      (let* [(cur (car input))
             (input-type (car cur))]
        (cond ((eq? input-type 'post)
               (cond ((< (cadr cur) min-prec)
                      (finish input min-prec stacks))
                     (else 
                      (process-prec (cadr cur)stacks)
                      (push-data! stacks (cons cur (list (pop-data stacks))))
                      (post (cdr input) min-prec stacks))))
              (else (let [(handle-infix (lambda (proc-fn inc)
                                          (cond ((< (cadr cur) min-prec)
                                                 (finish input min-prec stacks))
                                                (else 
                                                 (proc-fn (+ inc (cadr cur)) stacks)
                                                 (push-op! stacks cur)
                                                 (start (cdr input) min-prec stacks)))))]
                      (cond ((eq? input-type 'left) (handle-infix process-prec 0))
                            ((eq? input-type 'right) (handle-infix process-prec 1))
                            ((eq? input-type 'nonassoc) (handle-infix process-nonassoc 0))
                            (else error "post op, infix op or end of expression expected here"))))))))

;alters the stacks and returns the input
(define (start input min-prec stacks)
  (if (null? input) (error "expression expected")
      (let* [(cur (car input))
             (input-type (car cur))]
        (set! input (cdr input))
        ;pre could clearly work with new stacks, but could it reuse the current one?
        (cond ((eq? input-type 'pre)
               (let [(new-stack (prec-parse))]
                 (set! input (start input (cadr cur) new-stack))
                 (push-data! stacks 
                             (cons cur (list (pop-data new-stack))))
                 ;we might want to assert here that the cdr of the new stack is null
                 (post input min-prec stacks)))
              ((eq? input-type 'data)
               (push-data! stacks cur)
               (post input min-prec stacks))
              ((eq? input-type 'grouped)
               (let [(new-stack (prec-parse))]
                 (start (cdr cur) MIN-PREC new-stack)
                 (push-data! stacks (pop-data new-stack)))
               ;we might want to assert here that the cdr of the new stack is null
               (post input min-prec stacks))
              (else (error "bad input"))))))

(define (op-parse input)
  (let [(stacks (prec-parse))]
    (start input MIN-PREC stacks)
    (pop-data stacks)))

(define (main)
  (op-parse (read)))

(main)

voici un cas simple solution récursive écrit en Java. Notez qu'il ne traite pas les nombres négatifs, mais vous pouvez ajouter que si vous voulez:

public class ExpressionParser {

public double eval(String exp){
    int bracketCounter = 0;
    int operatorIndex = -1;

    for(int i=0; i<exp.length(); i++){
        char c = exp.charAt(i);
        if(c == '(') bracketCounter++;
        else if(c == ')') bracketCounter--;
        else if((c == '+' || c == '-') && bracketCounter == 0){
            operatorIndex = i;
            break;
        }
        else if((c == '*' || c == '/') && bracketCounter == 0 && operatorIndex < 0){
            operatorIndex = i;
        }
    }
    if(operatorIndex < 0){
        exp = exp.trim();
        if(exp.charAt(0) == '(' && exp.charAt(exp.length()-1) == ')')
            return eval(exp.substring(1, exp.length()-1));
        else
            return Double.parseDouble(exp);
    }
    else{
        switch(exp.charAt(operatorIndex)){
            case '+':
                return eval(exp.substring(0, operatorIndex)) + eval(exp.substring(operatorIndex+1));
            case '-':
                return eval(exp.substring(0, operatorIndex)) - eval(exp.substring(operatorIndex+1));
            case '*':
                return eval(exp.substring(0, operatorIndex)) * eval(exp.substring(operatorIndex+1));
            case '/':
                return eval(exp.substring(0, operatorIndex)) / eval(exp.substring(operatorIndex+1));
        }
    }
    return 0;
}

}

pourrait facilement être encodé en C comme analyseur de descente récursive.

#include <stdio.h>
#include <ctype.h>

/*
 *  expression -> sum
 *  sum -> product | product "+" sum
 *  product -> term | term "*" product
 *  term -> number | expression
 *  number -> [0..9]+
 */

typedef struct {
    int value;
    const char* context;
} expression_t;

expression_t expression(int value, const char* context) {
    return (expression_t) { value, context };
}

/* begin: parsers */

expression_t eval_expression(const char* symbols);

expression_t eval_number(const char* symbols) {
    // number -> [0..9]+
    double number = 0;        
    while (isdigit(*symbols)) {
        number = 10 * number + (*symbols - '0');
        symbols++;
    }
    return expression(number, symbols);
}

expression_t eval_term(const char* symbols) {
    // term -> number | expression
    expression_t number = eval_number(symbols);
    return number.context != symbols ? number : eval_expression(symbols);
}

expression_t eval_product(const char* symbols) {
    // product -> term | term "*" product
    expression_t term = eval_term(symbols);
    if (*term.context != '*')
        return term;

    expression_t product = eval_product(term.context + 1);
    return expression(term.value * product.value, product.context);
}

expression_t eval_sum(const char* symbols) {
    // sum -> product | product "+" sum
    expression_t product = eval_product(symbols);
    if (*product.context != '+')
        return product;

    expression_t sum = eval_sum(product.context + 1);
    return expression(product.value + sum.value, sum.context);
}

expression_t eval_expression(const char* symbols) {
    // expression -> sum
    return eval_sum(symbols);
}

/* end: parsers */

int main() {
    const char* expression = "1+11*5";
    printf("eval(\"%s\") == %d\n", expression, eval_expression(expression).value);

    return 0;
}

_{suivant libs peut être utile: yupana - strictement opérations arithmétiques; tinyexpr - opérations arithmétiques + C fonctions mathématiques + celui fourni par l'utilisateur; cpp - analyseur combinators}

explication

capturons la séquence de symboles qui représentent l'expression algébrique. Premier est un nombre, qui est un chiffre décimal répété une ou plusieurs fois. _{nous appellerons cette notation règle de production.}

number -> [0..9]+

l'opérateur D'Addition avec ses opérandes est une autre règle. Il s'agit de number ou de tout symbole représentant la séquence sum "*" sum .

sum -> number | sum "+" sum

essayer remplacer number par sum "+" sum qui sera number "+" number qui à son tour pourrait être élargi en [0..9]+ "+" [0..9]+ qui pourrait finalement être réduit à 1+8 qui est l'expression d'addition correcte.

D'autres substitutions produiront également une expression correcte: sum "+" sum -> number "+" sum -> number "+" sum "+" sum -> number "+" sum "+" number -> number "+" number "+" number -> 12+3+5

petit à petit nous pourrions ressembler ensemble de production règles _{aka grammar} qui expriment toutes les expressions algébriques possibles.

expression -> sum
sum -> difference | difference "+" sum
difference -> product | difference "-" product
product -> fraction | fraction "*" product
fraction -> term | fraction "/" term
term -> "(" expression ")" | number
number -> digit+                                                                    

pour commander l'opérateur priorité modifier la position de sa règle de production contre les autres. Regardez la grammaire ci-dessus et notez que la règle de production pour * est placée sous + cela forcera product évaluer avant sum . La mise en œuvre combine simplement la reconnaissance de modèle avec l'évaluation et reflète donc étroitement les règles de production.

expression_t eval_product(const char* symbols) {
    // product -> term | term "*" product
    expression_t term = eval_term(symbols);
    if (*term.context != '*')
        return term;

    expression_t product = eval_product(term.context + 1);
    return expression(term.value * product.value, product.context);
}

ici nous eval term d'abord et le retourner s'il n'y a pas de * caractère après _{c'est le choix de gauche dans notre règle de production} autrement-évaluer les symboles après et le retour term.value * product.value _{c'est le choix de droite dans notre règle de production i.e. term "*" product}