[JAVA] Immettere una formula definita dall'utente

[federico100mt]

ciao,

vi presento questo post un po particolare perchè ho l'intenzione di poter dare la possibilità all'utente di ridefinire una formula "su misura".
Il mio codice ne gestisce una di default, ma vorrei dare la possibilità all'utente di poterne ridefinire una piu "precisa" o cmq adatta alle sue esigenze.

esistono metodi, pacchetti o cmq approcci per definire formule, e quindi poterle scrivere in input usando un JDialog o simili?

immagino che tutta la gestione della sintassi può essere la parte più complessa...

grazie mille
:)

[Don[ITA]]

Formule de che? matematiche?

[PGI-Bis]

Puoi usare il motore di scripting presente nella piattaforma standard per inserire rapidamente nel programma dinamismi vari tra cui anche le più variopinte formule. Bisogna poi verificare se il prezzo in performance sia o meno sostenibile.

[Vincenzo1968]

In alternativa potresti creare manualmente un piccolo parser predittivo a discesa ricorsiva.

[federico100mt]

umm ottimi spunti direi,

io piu che altro, penso che in java esistano una sorta di "equation editors" che quindi abbiano un pannello(il classico con mille funzionalità) dal quale prendi i tuoi elementi per costruire la formula.

perchè il sistema piu rude che mi viene in mente è:

immetto la mia formula come stringa in jtextfield, la trasformo in "codice" (non saprei come) e poi, sperando che l'utente l'abbia inserita bene, possa eseguire...

oppure... ??

[PGI-Bis]

Se trovi un modo per far sì che l'utente non tenti di fare corbellerie ti candidi di diritto al premio Turing, con ottime possibilità di vincerlo a mani basse :D.

Creare un editor di equazioni non è complicato e per usare l'equazione creata devi tradurla (il parser di Vincenzo1968 servirebbe alla bisogna).

[federico100mt]

Ok, compreso, allora, il parser di vincezo1968 cosa sarebbe? il nome fa paura

[PGI-Bis]

Wikipedia, e passa la paura :D

http://en.wikipedia.org/wiki/Recursive_descent_parser

[federico100mt]

ok grazie, sto dando un'occhiata, mi viene un colpo, perchè mi ricorda l'esame di linguaggi...

ma una domandina, avete mai sentito parlare di swift (equation editor)?

[Vincenzo1968]

Ok, compreso, allora, il parser di vincezo1968 cosa sarebbe? il nome fa paura

:D

Tranquillo, come dice PGI, sviluppare il parser non è complicato. Se vuoi ti posso guidare passo passo con degli esempi di codice, ma c'è un problema: non m'intendo di Java. Posso farti degli esempi in C. Dovremmo trovare un volontario che s'intenda di entrambi i linguaggi e traduca il codice da C a Java(qualche nome che mi viene in mente: Banryu, Cionci, DanieleC88, TigerShark).

;)

P.S. puoi prendere spunto dal Contest 6 (http://www.hwupgrade.it/forum/showthread.php?t=1850150). Tieni presente, anche, che esistono tools appositi come ANTLR (http://www.antlr.org/) o JavaCC (https://javacc.dev.java.net/) o JavaCUP (http://www2.cs.tum.edu/projects/cup/) che automatizzano gran parte del lavoro. Ma, nel nostro caso, trattandosi di semplici espressioni matematiche e non di un linguaggio vero e proprio, è, secondo me, più istruttivo(e anche più divertente ;)) costruire il parser interamente a mano.

[banryu79]

:D
Tranquillo, come dice PGI, sviluppare il parser non è complicato. Se vuoi ti posso guidare passo passo con degli esempi di codice, ma c'è un problema: non m'intendo di Java

Per gli esempi a supporto della spiegazione (che interessa anche a me) puoi scrivere in pseudo codice, poi ci penserà lui a tradurre in Java ;)

In ogni caso seguo il thread con interesse.

[Vincenzo1968]

QUI (http://www.guidealgoritmi.it/public/parser.zip) è possibile scaricare un programa in C che realizza un parser predittivo a discesa ricorsiva.

Il parser accetta semplici espressioni aritmetiche come le seguenti:

5 + 8
21.34 - 2 * (5 - 3.8) / -2
5 + (21.5589E-2 * 2.5)

La prima cosa che serve è un analizzatore lessicale che suddivida la stringa in input restituendo, uno alla volta, su richiesta del parser, i vari token. L'analizzatore lessicale è implementato nei file "scanner.h" e "parser.h". Si tratta di un automa a stati finiti di tipo deterministico. L'algoritmo è ben illustrato nel dragon book(in java, se non mi sbaglio, dovrebbe esistere una classe "Tokenizer" o qualcosa di simile ;)).

Facciamo un esempio con la seguente espressione:

21.34 - 2 * (5 - 3.8) / -2

quando il parser chiama la funzione GetNextToken per la prima volta, viene restituito il token "21.34"; la seconda chiamata, restituisce il token "-", la terza il token "2" e così via.

Ogni token è rappresentato dalla seguente struttura:


typedef struct tagToken
{
TokenTypeEnum Type;
char *Lexeme;
double Value;
}Token;


TokenTypeEnum è un tipo enumerativo definito come segue:


typedef enum tagTokenType
{
EOL, UNKNOWN, VALUE_ERROR, VALUE, OPAREN, CPAREN, MULT, DIV, PLUS, MINUS
}TokenTypeEnum;


Il parser realizza l'analisi sintattica ed è implementato nei file "parser.h" e "parser.c".

La grammatica classica(in formato BFN (http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form)) per le espressioni aritmetiche è la seguente:


expression => expression + term
| expression - term
| term
term => term * factor
| term / factor
| factor
factor => ( expression )
| NUMBER


Tale grammatica gestisce correttamente precedenza e associatività degli operatori. Tuttavia, se vogliamo utilizzarla per un parser a discesa ricorsiva, dobbiamo prima eliminare la ricorsione a sinistra altrimenti il parser entrerebbe in un loop infinito.
È conveniente, nel nostro caso, utilizzare il formato EBNF (http://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form):


expr: term { (+|-) term }
term: factor { (*|/) factor }
factor: [-] atom
atom: '(' expr ')'
| number


I simboli non terminali sono expr, term, factor e atom.
I simboli terminali sono + - * / ( ) e number (con number intendiamo un valore numerico di tipo intero o in virgola mobile).
Il simbolo iniziale è expr.

L'algoritmo di parsing a discesa ricorsiva è molto semplice: per ogni simbolo non terminale richiamiamo una funzione associata; ogni simbolo terminale, invece, lo confrontiamo con il simbolo di lookahead: se coincidono andiamo avanti altrimenti fermiamo il parsing con un messaggio d'errore.
Il termine 'predittivo' si riferisce al fatto che il parser è in grado, guardando un solo simbolo(lookhaead) nella stringa di input, di predire la giusta produzione della grammatica.
È utile, per quanto detto sopra, implementare una funzione "match" che si occupi di confrontare il token corrente con il simbolo di lookhaead. Se il confronto è positivo, la funzione restituisce il token successivo. Altrimenti restituisce un messaggio di errore e termina il parser.


void match(char *szInput, TokenTypeEnum ExpectedToken)
{
if ( g_Token.Type == ExpectedToken )
GetNextToken(szInput, &g_Token);
else
{
printf("Errore di sintassi\n");
exit(1);
}
}


Il resto del programma si compone delle funzioni per la gestione dei quattro non terminali della nostra grammatica:


/* expr: term { (+|-) term } */
double expr(char *szInput)
{
double expr = term(szInput);

while( g_Token.Type == PLUS || g_Token.Type == MINUS )
{
if ( g_Token.Type == PLUS )
{
match(szInput, PLUS);
expr = expr + term(szInput);
}
else
{
match(szInput, MINUS);
expr = expr - term(szInput);
}
}

return expr ;
}

/* term: factor { (*|/) factor } */
double term(char *szInput)
{
double expr = factor(szInput);

while( g_Token.Type == MULT || g_Token.Type == DIV )
{
if ( g_Token.Type == MULT )
{
match(szInput, MULT);
expr = expr * factor(szInput);
}
else
{
double right;
match(szInput, DIV);
right = factor(szInput);
if ( right != 0.0 )
expr = expr / right;
else
{
printf("Errore: divisione per 0\n");
exit(1);
}
}
}

return expr ;
}

/* factor: [-] atom */
double factor(char *szInput)
{
double expr;

if ( g_Token.Type == MINUS )
{
match(szInput, MINUS);
expr = -atom(szInput);
}
else
{
expr = atom(szInput);
}

return expr;
}

/*
atom: '(' expr ')'
| number
*/
double atom(char *szInput)
{
double atom;

if ( g_Token.Type == OPAREN )
{
GetNextToken(szInput, &g_Token);
atom = expr(szInput);
match(szInput, CPAREN);
return atom;
}
else
{
if ( g_Token.Type != VALUE )
{
printf("Errore: operando mancante\n");
exit(1);
}
atom = g_Token.Value;
GetNextToken(szInput, &g_Token);
return atom;
}
}


Come si vede, le funzioni si richiamano a vicenda; sono, cioè mutuamente ricorsive(da qui il nome: discesa ricorsiva. (discesa perchè il parse tree sottostante viente costruito dall'alto verso il basso, top-down).
La funzione expr, per esempio, richiama la funzione term; questa, a sua volta, richiama la funzione factor e così via.

Il file main.c contiene un programma di test per il nostro parser:


int main(int argc, char **argv)
{
double res;

//char *szInput = "-5+8";
//char *szInput = "5+8";
//char *szInput = "-(5 + 3) * -2";
//char *szInput = "-(5 + 3) * 2";
//char *szInput = "(5 + 3) * 2";
//char *szInput = "5 + 3 * 2";
//char *szInput = "8+3*8/2";
char *szInput = "-21.5 + 5 * 55.89235E-2";

//char *szInput = "(5 + 3.1a8) / 4";
//char *szInput = "4 / 2";


res = Parse(szInput);
printf("Risultato -> %lf\n", res);

return 0;
}


Mi rendo conto di essere stato, forse, un po' troppo sintetico. Se qualcuno avesse dubbi sulla grammatica o su qualche passaggio poco chiaro, chieda pure ;)