Analyseur d'équation (expression) avec priorité ?
https://stackoverflow.com/questions/28256
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai développé un analyseur d'équations utilisant un algorithme de pile simple qui gérera les opérateurs binaires (+, -, |, &, *, /, etc.), les opérateurs unaires (!) et les parenthèses.
Cependant, en utilisant cette méthode, tout me laisse avec la même priorité - elle est évaluée de gauche à droite quel que soit l'opérateur, bien que la priorité puisse être appliquée à l'aide de parenthèses.
Donc, pour le moment, "1+11*5" renvoie 60, et non 56 comme on pourrait s'y attendre.
Bien que cela convienne au projet en cours, je souhaite disposer d'une routine à usage général que je peux utiliser pour des projets ultérieurs.
Modifié pour plus de clarté :
Qu'est-ce qu'un bon algorithme pour analyser des équations avec priorité ?
Je suis intéressé par quelque chose de simple à mettre en œuvre et je comprends que je peux coder moi-même pour éviter les problèmes de licence avec le code disponible.
Grammaire:
Je ne comprends pas la question de grammaire – je l'ai écrit à la main.C'est assez simple pour que je ne vois pas la nécessité de YACC ou de Bison.J'ai simplement besoin de calculer des chaînes avec des équations telles que "2+3 * (42/13)".
Langue:
Je fais cela en C, mais je m'intéresse à un algorithme, pas à une solution spécifique au langage.Le niveau C est suffisamment bas pour qu'il soit facile de le convertir dans une autre langue en cas de besoin.
Exemple de code
j'ai posté le code de test pour l'analyseur d'expression simple Je parlais plus haut.Les exigences du projet ont changé et je n'ai donc jamais eu besoin d'optimiser le code pour les performances ou l'espace car il n'était pas intégré au projet.Il est sous sa forme originale verbeuse et devrait être facilement compréhensible.Si je fais quelque chose de plus en termes de priorité des opérateurs, je choisirai probablement le hack macro car il correspond au reste du programme en termes de simplicité.Si jamais je l'utilise dans un projet réel, j'opterai pour un analyseur plus compact/rapide.
Question connexe
-Adam
La solution
À la dure
Vous voulez un analyseur de descente récursive.
Pour obtenir la priorité, vous devez penser de manière récursive, par exemple en utilisant votre exemple de chaîne,
1+11*5
pour le faire manuellement, vous devrez lire le 1, puis voyez le plus et démarrez une toute nouvelle "session" d'analyse récursive commençant par 11...et assurez-vous d'analyser le 11 * 5 dans son propre facteur, donnant un arbre d'analyse avec 1 + (11 * 5).
Tout cela semble si douloureux même pour tenter de l’expliquer, surtout avec l’impuissance supplémentaire de C.Vous voyez, après avoir analysé le 11, si le * était en fait un + à la place, vous devrez abandonner la tentative de création d'un terme et analyser à la place le 11 lui-même comme facteur.Ma tête explose déjà.C'est possible avec la stratégie récursive décente, mais il existe un meilleur moyen...
La manière facile (la bonne)
Si vous utilisez un outil GPL comme Bison, vous n'avez probablement pas à vous soucier des problèmes de licence puisque le code C généré par bison n'est pas couvert par la GPL (IANAL mais je suis presque sûr que les outils GPL ne forcent pas la GPL sur code/binaires générés ;par exemple, Apple compile du code comme, par exemple, Aperture avec GCC et le vend sans avoir à utiliser GPL pour ledit code).
Télécharger Bisons (ou quelque chose d'équivalent, ANTLR, etc.).
Il existe généralement un exemple de code sur lequel vous pouvez simplement exécuter bison et obtenir le code C souhaité qui illustre cette calculatrice à quatre fonctions :
http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html
Regardez le code généré et voyez que ce n'est pas aussi simple qu'il y paraît.De plus, les avantages d'utiliser un outil comme Bison sont 1) vous apprenez quelque chose (surtout si vous lisez le livre Dragon et apprenez les grammaires), 2) vous évitez NIH essayer de réinventer la roue.Avec un véritable outil d'analyseur-générateur, vous avez en fait l'espoir d'évoluer plus tard, en montrant à d'autres personnes que vous connaissez que les analyseurs sont le domaine des outils d'analyse.
Mise à jour:
Les gens ici ont donné de nombreux conseils judicieux.Mon seul avertissement contre le fait de sauter les outils d'analyse ou simplement d'utiliser l'algorithme Shunting Yard ou un analyseur décent récursif roulé à la main est que les petits langages jouets1 pourrait un jour se transformer en grands langages réels avec des fonctions (sin, cos, log) et des variables, des conditions et des boucles for.
Flex/Bison peut très bien être excessif pour un petit interprète simple, mais un analyseur + évaluateur unique peut causer des problèmes sur toute la ligne lorsque des modifications doivent être apportées ou des fonctionnalités doivent être ajoutées.Votre situation variera et vous devrez faire preuve de jugement ;ne le fais pas punissez les autres pour vos péchés [2] et construire un outil moins qu'adéquat.
Mon outil préféré pour l'analyse
Le meilleur outil au monde pour ce travail est le Parsec bibliothèque (pour les analyseurs récursifs décents) fournie avec le langage de programmation Haskell.Cela ressemble beaucoup BNF, ou comme un outil spécialisé ou un langage spécifique à un domaine pour l'analyse (exemple de code [3]), mais il s'agit en fait d'une bibliothèque standard dans Haskell, ce qui signifie qu'elle se compile dans la même étape de construction que le reste de votre code Haskell, et vous pouvez écrire du code Haskell arbitraire et l'appeler dans votre analyseur, et vous pouvez mélanger et faire correspondre d'autres bibliothèques tout est dans le même code.(En passant, l'intégration d'un langage d'analyse comme celui-ci dans un langage autre que Haskell entraîne de nombreuses erreurs syntaxiques.Je l'ai fait en C# et ça marche plutôt bien mais ce n'est pas si joli et succinct.)
Remarques:
1 Richard Stallman dit, dans Pourquoi vous ne devriez pas utiliser Tcl
La principale leçon d'EMACS est qu'une langue pour les extensions ne devrait pas être un simple "langage d'extension".Ce devrait être un véritable langage de programmation, conçu pour écrire et maintenir des programmes substantiels.Parce que les gens voudront faire ça!
[2] Oui, j'ai toujours peur d'utiliser ce « langage ».
Notez également que lorsque j'ai soumis cette entrée, l'aperçu était correct, mais L'analyseur moins qu'adéquat de SO a mangé ma balise d'ancrage proche dans le premier paragraphe, prouvant que les analyseurs ne sont pas quelque chose avec lequel il faut prendre à la légère, car si vous utilisez des expressions régulières et des hacks uniques vous vous tromperez probablement sur quelque chose de subtil et de petit.
[3] Extrait d'un analyseur Haskell utilisant Parsec :une calculatrice à quatre fonctions étendue avec des exposants, des parenthèses, des espaces pour la multiplication et des constantes (comme pi et e).
aexpr = expr `chainl1` toOp
expr = optChainl1 term addop (toScalar 0)
term = factor `chainl1` mulop
factor = sexpr `chainr1` powop
sexpr = parens aexpr
<|> scalar
<|> ident
powop = sym "^" >>= return . (B Pow)
<|> sym "^-" >>= return . (\x y -> B Pow x (B Sub (toScalar 0) y))
toOp = sym "->" >>= return . (B To)
mulop = sym "*" >>= return . (B Mul)
<|> sym "/" >>= return . (B Div)
<|> sym "%" >>= return . (B Mod)
<|> return . (B Mul)
addop = sym "+" >>= return . (B Add)
<|> sym "-" >>= return . (B Sub)
scalar = number >>= return . toScalar
ident = literal >>= return . Lit
parens p = do
lparen
result <- p
rparen
return result
Autres conseils
Le algorithme de gare de triage est le bon outil pour cela.Wikipédia est vraiment déroutant à ce sujet, mais en gros, l'algorithme fonctionne comme ceci :
Disons que vous voulez évaluer 1 + 2 * 3 + 4.Intuitivement, vous « savez » qu’il faut d’abord faire le 2*3, mais comment obtenir ce résultat ?La clé est de réaliser que lorsque vous parcourez la chaîne de gauche à droite, vous évaluerez un opérateur lorsque l'opérateur qui suit il a une priorité inférieure (ou égale à).Dans le contexte de l'exemple, voici ce que vous souhaitez faire :
- Regarder:1 + 2, ne fais rien.
- Maintenant, regardez 1 + 2 * 3, ne faites toujours rien.
- Regardez maintenant 1 + 2 * 3 + 4, vous savez maintenant que 2 * 3 doit être évalué car l'opérateur suivant a une priorité inférieure.
Comment mettez-vous cela en œuvre ?
Vous souhaitez avoir deux piles, une pour les nombres et une autre pour les opérateurs.Vous placez tout le temps des nombres sur la pile.Vous comparez chaque nouvel opérateur avec celui en haut de la pile, si celui en haut de la pile a une priorité plus élevée, vous le retirez de la pile d'opérateurs, retirez les opérandes de la pile de nombres, appliquez l'opérateur et poussez le résultat. sur la pile de chiffres.Maintenant, vous répétez la comparaison avec l’opérateur haut de pile.
Pour revenir à l'exemple, cela fonctionne comme ceci :
N = [] ops = [
- Lire 1.N = [1], Opérations = [ ]
- Lire +.N = [1], Opérations = [+]
- Lire 2.N = [1 2], Opérations = [+]
- Lire
*.N = [1 2], Opérations = [+ *] - Lire 3.N = [1 2 3], Opérations = [+ *]
- Lire +.N = [1 2 3], Opérations = [+ *]
- Pop 3, 2 et exécutez 2
*3, et poussez le résultat sur N.N = [1 6], Opérations = [+] +est laissé associatif, vous souhaitez donc également supprimer 1, 6 et exécuter le +.N = [7], Opérations = [].- Enfin, poussez le [+] sur la pile d'opérateurs.N = [7], Opérations = [+].
- Pop 3, 2 et exécutez 2
- Lire 4.N = [7 4].Opérations = [+].
- Vous êtes à court d'entrées, vous souhaitez donc vider les piles maintenant.Sur quoi vous obtiendrez le résultat 11.
Là, ce n'est pas si difficile, n'est-ce pas ?Et il ne fait aucune invocation à des grammaires ou à des générateurs d'analyseurs.
http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
Très bonne explication des différentes approches :
- Reconnaissance de descente récursive
- L'algorithme de la gare de triage
- La solution classique
- Escalade prioritaire
Écrit dans un langage simple et en pseudo-code.
J'aime celui qui « grimpe par priorité ».
Il y a un bel article ici sur la combinaison d'un simple analyseur de descente récursive avec une analyse de priorité des opérateurs.Si vous avez récemment écrit des analyseurs, cela devrait être très intéressant et instructif à lire.
Il y a longtemps, j'ai créé mon propre algorithme d'analyse syntaxique, que je ne trouvais dans aucun livre sur l'analyse syntaxique (comme le Dragon Book).En regardant les pointeurs vers l’algorithme Shunting Yard, je vois la ressemblance.
Il y a environ 2 ans, j'ai publié un article à ce sujet, complet avec le code source Perl, sur http://www.perlmonks.org/?node_id=554516.Il est facile de porter vers d'autres langues :la première implémentation que j'ai faite était dans l'assembleur Z80.
Il est idéal pour le calcul direct avec des nombres, mais vous pouvez l'utiliser pour produire un arbre d'analyse si vous le devez.
Mise à jour Parce que davantage de personnes peuvent lire (ou exécuter) Javascript, j'ai réimplémenté mon analyseur en Javascript, après que le code ait été réorganisé.L'ensemble de l'analyseur contient moins de 5 Ko de code Javascript (environ 100 lignes pour l'analyseur, 15 lignes pour une fonction wrapper), y compris le rapport d'erreurs et les commentaires.
Vous pouvez trouver une démo en direct sur 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 que vous décriviez la grammaire que vous utilisez actuellement pour analyser.On dirait que le problème vient peut-être de là !
Modifier:
Le fait que vous ne compreniez pas la question de grammaire et que « vous avez écrit ceci à la main » explique très probablement pourquoi vous rencontrez des problèmes avec les expressions de la forme « 1+11*5 » (c'est-à-dire avec la priorité des opérateurs) .Rechercher sur Google « grammaire pour les expressions arithmétiques », par exemple, devrait donner de bons indicateurs.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é pour prendre en charge certaines expressions plus compliquées (y compris les fonctions par exemple, ou les pouvoirs,...).
Je vous suggère d'y jeter un oeil ce fil, par exemple.
Presque toutes les introductions aux grammaires/analyses traitent les expressions arithmétiques comme exemple.
Notez qu’utiliser une grammaire n’implique pas du tout utiliser un outil spécifique (à la Yacc, Bison,...).En effet, vous utilisez très 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 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));
Lorsque vous posez votre question, aucune récursion n'est nécessaire.La réponse est trois choses :Notation Postfix plus algorithme Shunting Yard plus évaluation d'expression Postfix :
1).Notation Postfix = inventée pour éliminer le besoin de spécification explicite de priorité.Lire la suite sur le net mais voici l'essentiel :expression infixe ( 1 + 2 ) * 3 bien que facile à lire et à traiter pour les humains, pas très efficace pour le calcul via une machine.Qu'est-ce que?Règle simple qui dit "réécrivez l'expression en la mettant en cache en priorité, puis traitez-la toujours de gauche à droite".Donc l'infixe ( 1 + 2 ) * 3 devient un suffixe 12+3*.POST car l'opérateur est toujours placé APRÈS les opérandes.
2).Évaluation de l'expression postfixe.Facile.Lit les nombres dans la chaîne postfixe.Poussez-les sur une pile jusqu'à ce qu'un opérateur soit vu.Vérifier le type d'opérateur - unaire ?binaire?tertiaire?Extrayez autant d'opérandes de la pile que nécessaire pour évaluer cet opérateur.Évaluer.Repoussez le résultat sur la pile !Et tu as presque fini.Continuez ainsi jusqu'à ce que la pile n'ait qu'une seule entrée = valeur que vous recherchez.
Faisons ( 1 + 2 ) * 3 qui est en suffixe est "12+3*".Lire le premier chiffre = 1.Poussez-le sur la pile.Lisez ensuite.Nombre = 2.Poussez-le sur la pile.Lisez ensuite.Opérateur.Lequel?+.Quel genre?Binaire = nécessite deux opérandes.Pop pile deux fois = argright vaut 2 et argleft vaut 1.1 + 2 font 3.Repoussez 3 sur la pile.Lisez ensuite à partir de la chaîne postfix.C'est un numéro.3.Poussez.Lisez ensuite.Opérateur.Lequel?*.Quel genre?Binaire = nécessite deux nombres -> pop pile deux fois.Passez d’abord en argright, puis une deuxième fois en argleft.Évaluez l'opération - 3 fois 3 font 9. Appuyez sur 9 sur la pile.Lisez le caractère postfix suivant.C'est nul.Fin de la saisie.Pop stack onec = c'est votre réponse.
3).Shunting Yard est utilisé pour transformer une expression infixe (facilement) lisible par l'homme en expression postfixe (également facilement lisible par l'homme après un peu de pratique).Facile à coder manuellement.Voir commentaires ci-dessus et net.
Cela dépend de la façon dont vous voulez que ce soit "général".
Si vous voulez que ce soit vraiment très général, par exemple être capable d'analyser des fonctions mathématiques comme sin(4+5)*cos(7^3), vous aurez probablement besoin d'un analyser l'arbre.
Dans lequel, je ne pense pas qu'une implémentation complète soit appropriée pour être collée ici.Je vous suggère de consulter l'un des fameux "Livre des dragons".
Mais si vous voulez juste un support prioritaire, vous pouvez alors le faire en convertissant d'abord l'expression en forme postfixée dans laquelle 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.
Lorsque vous l'avez sous forme postfix, alors c'est un jeu d'enfant puisque vous comprenez déjà comment la pile aide.
Je suggérerais de tricher et d'utiliser le Algorithme de gare de triage.C'est un moyen simple d'écrire un analyseur simple de type calculatrice et prend en compte la priorité.
Si vous souhaitez symboliser correctement les choses et avoir des variables, etc.impliqué, alors j'irais de l'avant et écrirais un analyseur de descente récursive comme suggéré par d'autres ici, mais si vous avez simplement besoin d'un analyseur de style calculatrice, cet algorithme devrait être suffisant :-)
J'ai trouvé ceci sur la PIClist à propos du Algorithme de gare de triage:
Harold écrit :
Je me souviens avoir lu, il y a longtemps, d'un algorithme qui a converti les expressions algébriques en RPN pour une évaluation facile.Chaque valeur d'infixe ou opérateur ou parenthèse était représentée par une voiture de chemin de fer sur une piste.Un type de voiture s'est séparé d'une autre piste et l'autre a continué tout droit.Je ne me souviens pas des détails (évidemment!), Mais j'ai toujours pensé qu'il serait intéressant de coder.C'est à l'époque où j'écrivais le code d'assemblage 6800 (pas 68000).
Il s'agit de "l'algorythm de cour shunting" et c'est ce que la plupart des analyseurs de machines utilisent.Voir l'article sur l'analyse de Wikipedia.Un moyen facile de coder l'algorythm de cour shunting consiste à utiliser deux piles.L'un est la pile "push" et l'autre la pile "réduire" ou "résultat".Exemple:
PSTACK = () // Entrée RSTACK = () Entrée:1 + 2 * 3 Précédence = 10 // La plus basse réduit = 0 // ne réduisez pas
commencer:jeton '1' :ISNUMBER, Met dans le jeton PSTACK (push) '+':ISOperator définit la précèdence = 2 Si la priorité <préalable_Operator_precence, alors réduisez () // voir ci-dessous «+» dans le jeton pstack (push) '2':ISNUMBER, Met en jeton pstack (push) '*':isOperator, définissez la priorité = 1, placez dans pstack (push) // vérifie la priorité comme // au-dessus du jeton '3':ISNumber, mettre en pstack (push) fin de l'entrée, besoin de réduire (l'objectif est vide pstack) réduire () // fait
Pour réduire, les éléments pop de la pile poussère et les mettre dans la pile de résultats, échangez toujours les 2 meilleurs éléments sur PSTACK s'ils sont du formulaire 'Operator' 'Number':
pstack :'1' '+' '2' '' '3' pile :() ...pstack :() rpile :'3' '2''' '1' '+'
si l'expression avait été :
1*2+3
Ensuite, le déclencheur de réduction aurait été la lecture du jeton «+» qui a une précède plus faible que le «*» déjà poussé, donc il aurait fait:
pstack :'1' '' '2' pile :()...pstack :() rpile :'1' '2'''
puis poussé «+» puis «3» puis finalement réduit:
pstack :'+' '3' pile :'1' '2'''...pstack :() rpile :'1' '2''' '3' '+'
La version courte est donc :Les numéros de poussée, lors de la poussée des opérateurs, vérifiez la priorité de l'opérateur précédent.S'il était plus élevé que l'opérateur qui doit être poussé maintenant, réduisez d'abord, puis poussez l'opérateur actuel.Pour gérer les parens, économisez simplement la priorité de l'opérateur `` précédent '' et mettez une marque sur le pstack qui indique à l'algorythme de réduction de cesser de réduire lors de la résolution de l'intérieur d'une paire paren.La clôture Paen déclenche une réduction comme le fait la fin de l'entrée, et supprime également la marque de paren ouverte du pstack, et restaure la priorité de `` opération précédente '' afin que l'analyse puisse continuer après la clôture de Paen où elle s'était arrêtée.Cela peut être fait avec une récursivité ou sans (indice:Utilisez une pile pour stocker la priorité précédente lors de la rencontre d'un '(' ...).La version généralisée de ceci consiste à utiliser un générateur d'analyseur implémenté Algorythm, F.Ex.Utilisation de YACC ou de bison ou de taccle (analogue TCL de YACC).
Pierre
-Adam
J'ai posté la source d'un ultra compact (1 classe, < 10 KiB) Évaluateur mathématique Java sur mon site internet.Il s'agit d'un analyseur de descente récursif du type qui a provoqué l'explosion crânienne pour l'affiche de la réponse acceptée.
Il prend en charge la priorité complète, les parenthèses, les variables nommées et les fonctions à argument unique.
j'ai publié un analyseur d'expression basé sur Gare de triage de Dijkstra algorithme, selon les termes de la Licence Apache 2.0:
Une autre ressource pour l'analyse de priorité est le Analyseur de priorité des opérateurs entrée sur Wikipédia.Couvre l'algorithme de triage de Dijkstra et un algorithme alternatif d'arbre, mais couvre plus particulièrement un algorithme de remplacement de macro très simple qui peut être implémenté de manière triviale devant tout analyseur ignorant la 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))))
Ce qui est impressionnant par sa simplicité et très compréhensible.
J'ai mis en place un analyseur de descente récursive en Java dans le Analyseur MathEclipse projet.Il pourrait également être utilisé comme Boîte à outils Web Google module
Je travaille actuellement sur une série d'articles sur la construction d'un analyseur d'expressions régulières comme outil d'apprentissage des modèles de conception et de la programmation lisible.Vous pouvez jeter un oeil à code lisible.L'article présente une utilisation claire de l'algorithme des gares de triage.
J'ai écrit un analyseur d'expression en F# et j'en ai blogué ici.Il utilise l'algorithme du chantier de manœuvre, mais au lieu de convertir d'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 prend pas en charge les opérateurs unaires.J'ai écrit ceci pour apprendre le F#, mais pas pour apprendre l'analyse d'expressions.
Une solution Python utilisant pyparsing peut être trouvée ici.L'analyse de la notation infixe avec divers opérateurs avec priorité est assez courante, et donc l'analyse pyparse inclut également le infixNotation (Auparavant operatorPrecedence) générateur d'expressions.Avec lui, vous pouvez facilement définir des expressions booléennes en utilisant "AND", "OR", "NOT", 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 ajoutez des opérateurs P et C pour calculer les permutations et les combinaisons.Vous pouvez écrire un analyseur infixe pour la notation matricielle, qui inclut la gestion des opérateurs « -1 » ou « T » (pour l'inversion et la transposition).L'exemple OperatorPrecedence d'un analyseur à 4 fonctions (avec '!' ajouté pour le plaisir) est ici et un analyseur et évaluateur plus complet est ici.
Je sais que c'est une réponse tardive, mais je viens d'écrire un petit analyseur qui permet à tous les opérateurs (préfixe, suffixe et infixe-gauche, infixe-droite et non associatif) d'avoir une priorité arbitraire.
Je vais étendre cela pour un langage avec prise en charge DSL arbitraire, mais je voulais juste souligner que l'on n'a pas besoin d'analyseurs personnalisés pour la priorité des opérateurs, on peut utiliser un analyseur généralisé qui n'a pas du tout besoin de tables, et recherche simplement la priorité de chaque opérateur telle qu'elle apparaît.Les gens ont mentionné des analyseurs Pratt personnalisés ou des analyseurs de triage qui peuvent accepter des entrées illégales - celui-ci n'a pas besoin d'être personnalisé et (sauf s'il y a un bug) n'acceptera pas de mauvaises entrées.Il n'est pas complet dans un sens, il a été écrit pour tester l'algorithme et son entrée se présente sous une forme qui nécessitera un prétraitement, mais il y a des commentaires qui le précisent.
Remarque Certains types d'opérateurs communs manquent par exemple le type d'opérateur utilisé pour indexer la table IE [index] ou appeler une fonction de fonction (expression de paramètre, ...) Je vais les ajouter, mais pensez aux deux comme postfix Les opérateurs où ce qui se situe entre les délimiteurs '[' et ']' ou '(' et ')' est analysé avec une instance différente de l'analyseur d'expression.Désolé d'avoir omis cela, mais la partie postfix est présente - l'ajout du reste doublera probablement presque la taille du code.
Étant donné que l'analyseur ne contient que 100 lignes de code de raquette, je devrais peut-être simplement le coller ici, j'espère que ce n'est pas plus long que ce que permet stackoverflow.
Quelques précisions sur les décisions arbitraires :
Si un opérateur postfix de faible priorité est en compétition pour les mêmes blocs infixes qu'un opérateur de préfixe de faible priorité, 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 faible priorité.- par exemple:((données a) (gauche 1 +) (pré 2 non) (données b) (post 3!) (gauche 1 +) (données c)) est a + pas b! + c où n'est pas un opérateur de préfixe et!est l'opérateur postfix et les deux ont une priorité plus faible que + donc ils veulent se regrouper de manière incompatible comme (a + pas b!) + c ou comme a + (pas b! + c) Dans ces cas, l'opérateur de préfixe gagne toujours, donc le Le deuxième est la façon dont il analyse
Les opérateurs infixes non associatifs sont vraiment là pour que vous n'ayez pas à prétendre que les opérateurs qui renvoient des types différents de ceux qu'ils prennent ont un sens ensemble, mais sans avoir de types d'expression différents pour chacun, c'est une bidouille.Ainsi, dans cet algorithme, les opérateurs non associatifs refusent de s’associer non seulement à eux-mêmes mais à 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 de priorité ne devrait pas se poser, car cela n'a pas vraiment de sens de donner la même priorité à des opérateurs de différents types.Cet algorithme fait quelque chose dans ces cas-là, mais je ne prends même pas la peine de comprendre exactement quoi, car une telle grammaire est en premier lieu une mauvaise idée.
#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 une solution récursive de cas simple écrite en Java.Notez qu'il ne gère pas les nombres négatifs, mais vous pouvez l'ajouter si vous le souhaitez :
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;
}
}
L'algorithme pourrait être facilement codé en C en tant qu'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;
}
les bibliothèques suivantes pourraient être utiles : yupana - les opérations strictement arithmétiques ; petiteexpression - opérations arithmétiques + fonctions mathématiques C + une fournie par l'utilisateur ; mpc - combinateurs d'analyseurs
Explication
Capturons une séquence de symboles qui représentent l'expression algébrique.Le premier est un nombre, c’est-à-dire 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.C'est soit number ou tout symbole qui représente sum "*" sum séquence.
sum -> number | sum "+" sum
Essayez de remplacer number dans sum "+" sum ce sera number "+" number qui pourrait à son tour être étendu à [0..9]+ "+" [0..9]+ qui pourrait finalement être réduit à 1+8 qui est une 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 à un ensemble de règles de production autrement dit la grammaire 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 contrôler la priorité de l'opérateur, modifier la position de sa règle de production par rapport aux autres.Regardez la grammaire ci-dessus et notez que la règle de production pour * est placé en dessous + cela forcera product évaluer avant sum.La mise en œuvre combine simplement la reconnaissance de formes 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 évaluons term d'abord et renvoyez-le s'il n'y a pas * personnage après c'est un choix laissé dans notre règle de production sinon - évaluez les symboles après et revenez term.value * product.value c'est le bon choix dans notre règle de production, c'est-à-dire term "*" product
