Design intelligente di un parser matematico?

Question

Qual è il modo più intelligente per progettare un parser matematico? Ciò che intendo è una funzione che accetta una stringa matematica (come: " 2 + 3/2 + (2 * 5) ") e restituisce il valore calcolato? Ne ho scritto uno in VB6 anni fa, ma alla fine è diventato troppo gonfio e poco portatile (o intelligente per quella materia). Sono apprezzate idee generali, codice psuedo o codice reale.

Answer 1

Un approccio piuttosto valido implicherebbe due passaggi. Il primo passo prevede convertire l'espressione da infix a postfix (ad es. tramite la notazione Lo shunt di Dijkstra ). Una volta fatto, è abbastanza banale scrivere un valutatore postfisso .

Answer 2

Ho scritto alcuni post sul blog sulla progettazione di un parser matematico. Esiste una introduttiva , conoscenza di base di grammatiche , implementazione di esempio scritta in Ruby e una suite di test . Forse troverai questi materiali utili.

Answer 3

Hai un paio di approcci. È possibile generare codice dinamico ed eseguirlo per ottenere la risposta senza dover scrivere molto codice. Basta eseguire una ricerca sul codice generato dal runtime in .NET e ci sono molti esempi in giro.

In alternativa puoi creare un vero parser e generare un piccolo albero di analisi che viene quindi utilizzato per valutare l'espressione. Ancora una volta, questo è piuttosto semplice per le espressioni di base. Dai un'occhiata a codeplex perché credo che abbiano un parser matematico lì. Oppure cerca BNF che includerà esempi. Qualsiasi sito Web che introduce concetti di compilatore includerà questo come esempio di base.

Valutatore di espressioni Codeplex

Answer 4

So che è vecchio, ma mi sono imbattuto in questo tentativo di sviluppare una calcolatrice come parte di un'app più grande e ho riscontrato alcuni problemi utilizzando la risposta accettata. I collegamenti sono stati IMMENSAMENTE utili per comprendere e risolvere questo problema e non dovrebbero essere scontati. Stavo scrivendo un'app Android in Java e per ogni elemento nell'espressione "stringa", " In realtà ho archiviato una stringa in una ArrayList mentre l'utente digita sulla tastiera. Per la conversione da infisso a postfisso, ho ripetuto ogni stringa nell'ArrayList, quindi ho valutato l'ArrayList of Strings postfix appena organizzato. Questo è stato fantastico per un piccolo numero di operandi / operatori, ma i calcoli più lunghi sono stati costantemente disattivati, soprattutto quando le espressioni hanno iniziato a valutare come numeri non interi. Nel link fornito per Conversione da Infix a Postfix , suggerisce il popping lo Stack se l'oggetto scansionato è un operatore e l'oggetto topStack ha una precedenza più alta. Ho scoperto che questo è quasi corretto. La sospensione dell'elemento topStack se la sua precedenza è superiore O UGUALE all'operatore scansionato ha reso finalmente i miei calcoli corretti. Speriamo che questo possa aiutare chiunque lavori su questo problema, e grazie a Justin Poliey (e fas?) Per aver fornito alcuni link preziosi.

Answer 5

Se hai " sempre attivo " applicazione, basta pubblicare la stringa matematica su google e analizzare il risultato. Modo semplice ma non sono sicuro se è quello che ti serve - ma immagino in qualche modo intelligente.

Answer 6

La domanda correlata Parser di equazioni (espressioni) con precedenza? contiene alcune buone informazioni su come iniziare anche con questo.

-Adam

Answer 7

Supponendo che il tuo input sia un'espressione infix in formato stringa, puoi convertirlo in postfix e, usando una coppia di pile: una pila di operatori e una pila di operandi, lavora la soluzione da lì. Puoi trovare informazioni generali sull'algoritmo sul link Wikipedia.

Answer 8

ANTLR è un bellissimo generatore di parser LL (*). Lo consiglio vivamente.

Answer 9

Gli sviluppatori vogliono sempre avere un approccio pulito e provare a implementare la logica di analisi da zero, di solito finendo con la Dijkstra Shunting-Yard Algorithm . Il risultato è un codice pulito, ma probabilmente pieno di bug. Ho sviluppato una tale API, JMEP , che fa tutto questo, ma mi ci sono voluti anni per avere un codice stabile.

Anche con tutto quel lavoro, puoi anche vedere dalla pagina del progetto che sto seriamente pensando di passare all'uso di JavaCC o ANTLR, anche dopo tutto quel lavoro già fatto.

Answer 10

11 anni nel futuro da quando è stata posta questa domanda: se non vuoi reinventare la ruota, ci sono molti parser matematici esotici là fuori.

Ce n'è uno che ho scritto anni fa che supporta operazioni aritmetiche, risoluzione di equazioni, calcolo differenziale, calcolo integrale, statistiche di base, definizione di funzioni / formule, rappresentazione grafica, ecc.

Si chiama ParserNG ed è gratuito.

La valutazione di un'espressione è semplice come:

    MathExpression expr = new MathExpression("(34+32)-44/(8+9(3+2))-22"); 
    System.out.println("result: " + expr.solve());

    result: 43.16981132075472

O usando variabili e calcolando espressioni semplici:

 MathExpression expr = new MathExpression("r=3;P=2*pi*r;"); 
System.out.println("result: " + expr.getValue("P"));

O usando le funzioni:

MathExpression expr = new MathExpression("f(x)=39*sin(x^2)+x^3*cos(x);f(3)"); 
System.out.println("result: " + expr.solve());

result: -10.65717648378352

O per valutare la derivata in un dato punto (Nota che fa differenziazione simbolica (non numerica) dietro le quinte, quindi l'accuratezza non è limitata dagli errori delle approssimazioni numeriche):

MathExpression expr = new MathExpression("f(x)=x^3*ln(x); diff(f,3,1)"); 
System.out.println("result: " + expr.solve());

 result: 38.66253179403897

Che differenzia x ^ 3 * ln (x) una volta a x = 3. Il numero di volte che puoi differenziare è 1 per ora.

o per l'integrazione numerica:

MathExpression expr = new MathExpression("f(x)=2*x; intg(f,1,3)"); 
System.out.println("result: " + expr.solve());

result: 7.999999999998261... approx: 8

Questo parser è abbastanza veloce e ha molte altre funzionalità.

È stato concluso il lavoro sul porting su Swift tramite collegamenti all'obiettivo C e l'abbiamo usato per rappresentare graficamente le applicazioni tra gli altri casi d'uso iterativi.

DISCLAIMER: ParserNG è stato creato da me.