Design intelligente di un parser matematico?

Qual è il modo più intelligente per progettare un parser matematico? Quello che intendo è una funzione che prende 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 non molto portabile (o intelligente per quella materia …). Sono apprezzate idee generali, codice psuedo o codice reale.

Un buon approccio comporterebbe due passaggi. Il primo passo prevede la conversione dell’espressione da infisso a postfisso (ad esempio tramite la notazione di smistamento di Dijkstra ). Una volta fatto, è piuttosto banale scrivere un valutatore postfix .

Ho scritto alcuni post sul blog sulla progettazione di un parser matematico. C’è un’introduzione generale, una conoscenza di base delle grammatiche , un’implementazione di esempio scritta in Ruby e una suite di test . Forse troverai utile questo materiale.

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

In alternativa è ansible creare un parser effettivo e generare un piccolo albero di analisi che viene quindi utilizzato per valutare l’espressione. Ancora una volta questo è abbastanza semplice per le espressioni di base. Controlla codeplex perché credo che abbiano un parser matematico lì. Oppure basta cercare BNF che includa esempi. Qualsiasi sito web che introduce concetti di compilatori includerà questo come esempio di base.

Codeplex Expression Evaluator

Se hai un’applicazione “sempre triggers”, pubblica la stringa matematica su google e analizza il risultato. Modo semplice ma non sicuro se questo è quello che ti serve – ma in qualche modo intelligente credo.

La domanda relativa parser di equazione (espressione) con precedenza? ha alcune buone informazioni su come iniziare anche con questo.

-Adamo

So che questo è vecchio, ma mi sono imbattuto in questo tentativo di sviluppare una calcolatrice come parte di un’app più grande e ho trovato alcuni problemi usando la risposta accettata. I collegamenti erano IMMENSAMENTE utili per comprendere e risolvere questo problema e non dovrebbero essere scontati. Stavo scrivendo un’app per Android in Java e per ogni elemento nell’espressione “stringa”, ho effettivamente memorizzato una stringa in un arraylist mentre l’utente digita sulla tastiera. Per la conversione infisso-a-postfisso, ho ripetuto l’iterazione di ciascuna stringa in ArrayList, quindi ho valutato il postfix ArrayList di Stringhe appena disposto. Questo è stato fantastico per un piccolo numero di operandi / operatori, ma i calcoli più lunghi sono stati coerenti, specialmente quando le espressioni iniziarono a valutare i non interi. Nel collegamento fornito per la conversione da Infix a Postfix , suggerisce di scoppiare lo Stack se l’elemento scansionato è un operatore e l’elemento topStack ha una precedenza più alta. Ho trovato che questo è quasi corretto. Popping the topStack item se la sua precedenza è superiore O EQUAL all’operatore scansionato finalmente ha fatto i miei calcoli uscire corretto. Speriamo che questo possa aiutare chiunque lavori su questo problema, e grazie a Justin Poliey (e fas?) Per aver fornito alcuni collegamenti inestimabili.

Supponendo che il tuo input sia un’espressione infissa in formato stringa, potresti convertirlo in postfix e, usando una coppia di stack: uno stack operatore e uno stack operandi, lavorare la soluzione da lì. Puoi trovare informazioni generali sugli algoritmi sul link di Wikipedia.

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

Gli sviluppatori vogliono sempre avere un approccio pulito e cercano di implementare la logica del parsing da zero, di solito finendo con l’ algoritmo di Dijkstra Shunting-Yard . Il risultato è un codice dall’aspetto accurato, ma probabilmente con errori. Ho sviluppato una tale API, JMEP , che fa tutto questo, ma mi ci sono voluti anni per avere un codice stabile.

Anche con tutto ciò che funziona, puoi vedere anche da quella pagina del progetto che sto seriamente pensando di passare all’uso di JavaCC o ANTLR, anche dopo tutto quel lavoro già fatto.