Validare espressioni matematiche/logiche

**Antonio** · 31-05-2010, 13:24

Un saluto a tutti,

posto con la speranza che qualcuno si sia ritrovato nella mia stessa situazione; quello che sto facendo è mettere in piedi un algoritmo per il controllo di espressioni che contengono operatori matematici (+,-,*,/) e logici (or,not,and).

Una soluzione l'ho trovata, ma fa uso ricorsivo di una regex non propriamente semplice oltre ad altre sostituzioni O(n) ed il criterio di arresto in caso di errore nel peggiore dei casi può avere la stessa complessità dell'algoritmo di risoluzione stesso.

Qualcuno conosce qualche algoritmo già ingegnerizzato che non sia O(n^(n. di capelli che aveva Cocciante in testa)) ?

**Uno** · 31-05-2010, 18:47

A parte che non dici in che linguaggio, ma magari ti interessa solo il flow chart... però (complice il fatto che in questi giorni sto lavorando ad un editor js che oltre che veramente cross browser sia veramente in grado di far uscire codice pulito e a gusto del webmaster) mica sono riuscito a capire che ti serve.
Che tipo di controllo?

**Antonio** · 31-05-2010, 19:02

Mi serve controllare che l'espressione sia formalmente corretta, quindi che non ci siano ad esempio operatori appesi ("a AND" oppure "AND x" oppure "3+a+"), parentesi aperte e non chiuse etc etc.

Il linguaggio con il quale è scritto non mi interessa, dato che mi interessa l'algoritmo usato

Per ora ho messo in piedi un algoritmo, ma il criterio di arresto in caso di errore ha una complessità pari al numero di parentesi innestate presenti; per fare un esempio

(((varn == 3/5*varz) || !boolvar && num/3*nonso <12) && (ciao != "Hello")) || || !bool2

In questo caso, dove ho una OR finale senza secondo operatore, con il mio metodo mi accorgerei dell'errore dopo aver eseguito calcoli per una complessità pari a O(n^4), senza contare la complessità dell'espressione regolare che uso per ogni iterazione.

Dato che non penso di essere l'unico sulla terra ad essersi fatto il problema di validare una espressione, mi chiedevo se c'era qualcosa di già fatto ed ottimizzato.

PS: la sola espressione regolare che mi controlla la validità di ciò che è presente in una eventuale parentesi è qualcosa come 700 e passa caratteri con decine di condizioni all'interno.

**Uno** · 31-05-2010, 20:47

Credo di aver capito (+ o -).
No, non mi pare di aver mai visto una cosa specifica.

Posso dirti come lo imposterei io (un accenno eh...)

Considererei l'espressione come un un qualsiasi file strutturato tipo xml, latex etc...
Prima verificherei le parentesi (se parliamo di espressioni matematiche con parentesi tonde, quadre e graffe un tipo per volta) poi una volta che sono tranquillo sull'integrità dei nodi ne prenderei uno per volta con la stessa regex.

**Antonio** · 31-05-2010, 21:56

Se devo ricreare tutto l'albero "alla DOM" sono non poche iterazioni e la complessità è superiore a quella dell'algortimo che ho messo in piedi (dato che non devo eseguire, ma solo controllare che sia ok l'espressione, non ho bisogno di arrivare ad una struttura ad albero

Mi tengo la mia soluzione, anche se non pulitissima ho i seguenti risultati con questa espressione (oltremodo sovradimensionata):

Completed in 0.012470006942749 seconds

Codice:

(((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio)  && (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2  && ciccio) || ( ((((((_ff/9*2-1.2 == jguigi.lo9)  /_.nji+1212.12+opop-0.2 && ciccio) && (((_ff/9*2-1.2 ==  jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio) || (  (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio)  || (boh<5636 + _ff/9*2-1.2 == jguigi.lo9 /_.nji+1212.12+opop-0.2))))  || (((((((((((((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2  && ciccio) && (((_ff/9*2-1.2 == jguigi.lo9)  /_.nji+1212.12+opop-0.2 && ciccio) || ( ((((((_ff/9*2-1.2 ==  jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio) &&  (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio)  || ( (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 &&  ciccio) || (boh<5636 + _ff/9*2-1.2 == jguigi.lo9  /_.nji+1212.12+opop-0.2)))) || ((((((((((_ff/9*2-1.2 == jguigi.lo9)  /_.nji+1212.12+opop-0.2 && ciccio) && (((_ff/9*2-1.2 ==  jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio) || (  ((((((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 &&  ciccio) && (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2  && ciccio) || ( (((_ff/9*2-1.2 == jguigi.lo9)  /_.nji+1212.12+opop-0.2 && ciccio) || (boh<5636 + _ff/9*2-1.2  == jguigi.lo9 /_.nji+1212.12+opop-0.2)))) || (((((((_ff/9*2-1.2 ==  jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio) &&  (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio)  || ( ((((((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2  && ciccio) && (((_ff/9*2-1.2 == jguigi.lo9)  /_.nji+1212.12+opop-0.2 && ciccio) || ( (((_ff/9*2-1.2 ==  jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio) || (boh<5636 +  _ff/9*2-1.2 == jguigi.lo9 /_.nji+1212.12+opop-0.2)))) ||  ((((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 &&  ciccio) && (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2  && ciccio) || ( (((_ff/9*2-1.2 == jguigi.lo9)  /_.nji+1212.12+opop-0.2 && ciccio) || (boh<5636 + _ff/9*2-1.2  == jguigi.lo9 /_.nji+1212.12+opop-0.2)))) || (boh<5636 + _ff/9*2-1.2  == jguigi.lo9 /_.nji+1212.12+opop-0.2)) && boh || (ciccio) +  _ff/9*2-1.2 == jguigi.lo9 /_.nji+1212.12+opop-0.2)) && boh ||  (ciccio)) /_.nji+1212.12+opop-0.2 && ciccio) || (boh<5636 +  _ff/9*2-1.2 == jguigi.lo9 /_.nji+1212.12+opop-0.2)))) || (boh<5636 +  _ff/9*2-1.2 == jguigi.lo9 /_.nji+1212.12+opop-0.2)) && boh ||  (ciccio)) /_.nji+1212.12+opop-0.2 && ciccio) &&  (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio)  || ( (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 &&  ciccio) || (boh<5636 + _ff/9*2-1.2 == jguigi.lo9  /_.nji+1212.12+opop-0.2)))) || (boh<5636 + _ff/9*2-1.2 == jguigi.lo9  /_.nji+1212.12+opop-0.2)) && boh || (ciccio) + _ff/9*2-1.2 ==  jguigi.lo9 /_.nji+1212.12+opop-0.2)) && boh || (ciccio))  /_.nji+1212.12+opop-0.2 && ciccio) || (boh<5636 + _ff/9*2-1.2  == jguigi.lo9 /_.nji+1212.12+opop-0.2)))) || (boh<5636 + _ff/9*2-1.2  == jguigi.lo9 /_.nji+1212.12+opop-0.2)) && boh || (ciccio))  /_.nji+1212.12+opop-0.2 && ciccio) && (((_ff/9*2-1.2 ==  jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio) || (  ((((((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 &&  ciccio) && (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2  && ciccio) || ( (((_ff/9*2-1.2 == jguigi.lo9)  /_.nji+1212.12+opop-0.2 && ciccio) || (boh<5636 + _ff/9*2-1.2  == jguigi.lo9 /_.nji+1212.12+opop-0.2)))) || ((((_ff/9*2-1.2 ==  jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio) &&  (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio)  || ( (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 &&  ciccio) || (boh<5636 + _ff/9*2-1.2 == jguigi.lo9  /_.nji+1212.12+opop-0.2)))) || (boh<5636 + _ff/9*2-1.2 == jguigi.lo9  /_.nji+1212.12+opop-0.2)) && boh || (ciccio) + _ff/9*2-1.2 ==  jguigi.lo9 /_.nji+1212.12+opop-0.2)) && boh || (ciccio))  /_.nji+1212.12+opop-0.2 && ciccio) || (boh<5636 + _ff/9*2-1.2  == jguigi.lo9 /_.nji+1212.12+opop-0.2)))) || (boh<5636 + _ff/9*2-1.2  == jguigi.lo9 /_.nji+1212.12+opop-0.2)) && boh || (ciccio))  /_.nji+1212.12+opop-0.2 && ciccio) && (((_ff/9*2-1.2 ==  jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio) || (  (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio)  || (boh<5636 + _ff/9*2-1.2 == jguigi.lo9 /_.nji+1212.12+opop-0.2))))  || (boh<5636 + _ff/9*2-1.2 == jguigi.lo9 /_.nji+1212.12+opop-0.2))  && boh || (ciccio) + _ff/9*2-1.2 == jguigi.lo9  /_.nji+1212.12+opop-0.2)) && boh || (ciccio))  /_.nji+1212.12+opop-0.2 && ciccio) || (boh<5636 + _ff/9*2-1.2  == jguigi.lo9 /_.nji+1212.12+opop-0.2)))) || (boh<5636 + _ff/9*2-1.2  == jguigi.lo9 /_.nji+1212.12+opop-0.2)) && boh || (ciccio))  /_.nji+1212.12+opop-0.2 && ciccio) && (((_ff/9*2-1.2 ==  jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio) || (  ((((((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 &&  ciccio) && (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2  && ciccio) || ( (((_ff/9*2-1.2 == jguigi.lo9)  /_.nji+1212.12+opop-0.2 && ciccio) || (boh<5636 + _ff/9*2-1.2  == jguigi.lo9 /_.nji+1212.12+opop-0.2)))) || (((((((_ff/9*2-1.2 ==  jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio) &&  (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio)  || ( ((((((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2  && ciccio) && (((_ff/9*2-1.2 == jguigi.lo9)  /_.nji+1212.12+opop-0.2 && ciccio) || ( (((_ff/9*2-1.2 ==  jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio) || (boh<5636 +  _ff/9*2-1.2 == jguigi.lo9 /_.nji+1212.12+opop-0.2)))) ||  ((((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 &&  ciccio) && (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2  && ciccio) || ( (((_ff/9*2-1.2 == jguigi.lo9)  /_.nji+1212.12+opop-0.2 && ciccio) || (boh<5636 + _ff/9*2-1.2  == jguigi.lo9 /_.nji+1212.12+opop-0.2)))) || (boh<5636 + _ff/9*2-1.2  == jguigi.lo9 /_.nji+1212.12+opop-0.2)) && boh || (ciccio) +  _ff/9*2-1.2 == jguigi.lo9 /_.nji+1212.12+opop-0.2)) && boh ||  (ciccio)) /_.nji+1212.12+opop-0.2 && ciccio) || (boh<5636 +  _ff/9*2-1.2 == jguigi.lo9 /_.nji+1212.12+opop-0.2)))) || (boh<5636 +  _ff/9*2-1.2 == jguigi.lo9 /_.nji+1212.12+opop-0.2)) && boh ||  (ciccio)) /_.nji+1212.12+opop-0.2 && ciccio) &&  (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio)  || ( (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 &&  ciccio) || (boh<5636 + _ff/9*2-1.2 == jguigi.lo9  /_.nji+1212.12+opop-0.2)))) || (boh<5636 + _ff/9*2-1.2 == jguigi.lo9  /_.nji+1212.12+opop-0.2)) && boh || (ciccio) + _ff/9*2-1.2 ==  jguigi.lo9 /_.nji+1212.12+opop-0.2)) && boh || (ciccio))  /_.nji+1212.12+opop-0.2 && ciccio) || (boh<5636 + _ff/9*2-1.2  == jguigi.lo9 /_.nji+1212.12+opop-0.2)))) || (boh<5636 + _ff/9*2-1.2  == jguigi.lo9 /_.nji+1212.12+opop-0.2)) && boh || (ciccio))  /_.nji+1212.12+opop-0.2 && ciccio) && (((_ff/9*2-1.2 ==  jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio) || (  ((((((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 &&  ciccio) && (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2  && ciccio) || ( (((_ff/9*2-1.2 == jguigi.lo9)  /_.nji+1212.12+opop-0.2 && ciccio) || (boh<5636 + _ff/9*2-1.2  == jguigi.lo9 /_.nji+1212.12+opop-0.2)))) || ((((_ff/9*2-1.2 ==  jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio) &&  (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio)  || ( (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 &&  ciccio) || (boh<5636 + _ff/9*2-1.2 == jguigi.lo9  /_.nji+1212.12+opop-0.2)))) || (boh<5636 + _ff/9*2-1.2 == jguigi.lo9  /_.nji+1212.12+opop-0.2)) && boh || (ciccio) + _ff/9*2-1.2 ==  jguigi.lo9 /_.nji+1212.12+opop-0.2)) && boh || (ciccio))  /_.nji+1212.12+opop-0.2 && ciccio) || (boh<5636 + _ff/9*2-1.2  == jguigi.lo9 /_.nji+1212.12+opop-0.2)))) || (boh<5636 + _ff/9*2-1.2  == jguigi.lo9 /_.nji+1212.12+opop-0.2)) && boh || (ciccio))  /_.nji+1212.12+opop-0.2 && ciccio) && (((_ff/9*2-1.2 ==  jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio) || (  (((_ff/9*2-1.2 == jguigi.lo9) /_.nji+1212.12+opop-0.2 && ciccio)  || (boh<5636 + _ff/9*2-1.2 == jguigi.lo9 /_.nji+1212.12+opop-0.2))))  || (boh<5636 + _ff/9*2-1.2 == jguigi.lo9 /_.nji+1212.12+opop-0.2))  && boh || (ciccio) + _ff/9*2-1.2 == jguigi.lo9  /_.nji+1212.12+opop-0.2)) && boh || (ciccio))  /_.nji+1212.12+opop-0.2 && ciccio) || (boh<5636 + _ff/9*2-1.2  == jguigi.lo9 /_.nji+1212.12+opop-0.2)))) || (boh<5636 + _ff/9*2-1.2  == jguigi.lo9 /_.nji+1212.12+opop-0.2)) && boh || (ciccio)

**Uno** · 02-06-2010, 00:26

Ma tu fai una unica regex indipendentemente da quanto è lunga l'espressione?
Io non stavo dicendo di creare un parser per la manipolazione del dom, semplicemente nel primo passaggio (molto veloce e se becca un errore mi risparmia il resto) verificherei la corrispondenza delle parentesi, poi applicherei delle regex più leggere e veloci ai blocchi che leggerei sequenzialmente senza preoccuparmi di parenti, ancestrali, figli etc..

Secondo me in proporzione all'aumento dell'espressione si potrebbe guadagnare qualche spicciolo di tempo. Su una espressione corta è facile che il tuo sistema (che non conosco, mi fido di quel poco che hai esposto) sia più veloce, ma aumentando la lunghezza non so... bisognerebbe solo provare.

**Antonio** · 02-06-2010, 08:37

Originariamente Scritto da Uno

Ma tu fai una unica regex indipendentemente da quanto è lunga l'espressione?

Claro che si

Originariamente Scritto da Uno

Io non stavo dicendo di creare un parser per la manipolazione del dom, semplicemente nel primo passaggio (molto veloce e se becca un errore mi risparmia il resto) verificherei la corrispondenza delle parentesi, poi applicherei delle regex più leggere e veloci ai blocchi che leggerei sequenzialmente senza preoccuparmi di parenti, ancestrali, figli etc..

E' esattamente quel che faccio.

Prima di usare LA regex, controllo che le parentesi siano correttamente aperte/chiuse e che non ci siano parentesi aperte e subito dopo chiuse.

Con la regex controllo la validità di espressioni del tipo:

_ff/9*2-1.2 == jguigi.lo9 /_.nji+1212.12+opop-0.2 && ciaio || boh...

Quindi tutto quel che può capitare se non ci sono parentesi che rompono le scatole.

Il problema è dato dal fatto che le regex non hanno memoria, quindi non posso sapere da regex quando una parentesi è stata aperta e quando è stata chiusa; quindi un semplice errore tipo:

"ciao ((((boh))))" oppure "(a && ((boh) && ) || ) lol"

dove prima o dopo della parentesi manca l'operatore non posso validarlo con una unica regex a causa delle parentesi.

Quello che faccio attualmente (dopo i check che ho esposto in precedenza) è un ciclo con 2 operazioni:

- Op1 esegue un massive replace della roba trovata con la mia regex e la sostituisce con "a" (quindi cose del tipo "ciccio boh" che sono senza operatore nel mezzo non vengono sostituite).
- Op2 esegue un massive replace di tutte le (a) trovate con la sola "a"
- Op3 controlla che la lunghezza della stringa originaria sia maggiore della nuova stringa che ho trovato; nel caso in cui la stringa si sia ridotta ad avere lunghezza = 1(quindi contenga la sola "a") allora non ci sono errori sintattici, se invece la stringa dopo un passaggio non diminuisce in lunghezza allora significa che c'è un errore e si esce dal ciclo, se invece la lunghezza è diminuita ci si fà un altro giro sulla giostra.

Con il ciclo che eseguo è come se andassi a pseudo-risolvere (in realtà non lo faccio) l'espressione come farebbe un umano, togliendo man mano le parentesi; metodo che non mi piace per niente

.

**danielej** · 02-06-2010, 08:51

Così a prima vista, si potrebbe togliere direttamente il significato all'espressione e in teoria dovrebbe essere fattibile con complessità lineare e consumo minimo di memoria, elaborando i caratteri da sinistra a destra per individuare esclusivamente che tipo di informazione rappresentano, es.

- Tolgo opertori unari corretti, termino in caso di operatore posizionato male
- Sostituisco operatori binari con simbolo ascii non stampabile (che qui scrivo come *) e operandi in altro simbolo ascii non stampabile (che qui scrivo come A)
- Tolgo spazi
- Conto numero parentesi aperte e richiuse procedendo da sinistra e tenendo un contatore, +1 aperta -1 chiusa, se va a -1 o al termine il contatore è > 0 c'è un errore.
- Tolgo le parentesi

Leggo da sinistra e se l'espressione: inizia in *A, contiene **, termina in A*, non è valida

Codice:

(((varn == 3/5*varz) || !boolvar && num/3*nonso <12) && (ciao != "Hello")) || || !bool2

(((varn == 3/5*varz) || boolvar && num/3*nonso <12) && (ciao != "Hello")) || || bool2

(((A * A*A*A) * A * A*A*A *A) * (A * A)) * * A

(((A*A*A*A)*A*A*A*A*A)*(A*A))**A

A*A*A*A*A*A*A*A*A*A*A**A

Questa alla fine contiene ** e non è valida

**Antonio** · 02-06-2010, 09:10

Originariamente Scritto da danielej

- Tolgo le parentesi

Leggo da sinistra e se l'espressione: inizia in *A, contiene **, termina in A*, non è valida

Codice:

(((varn == 3/5*varz) || !boolvar && num/3*nonso <12) && (ciao != "Hello")) || || !bool2

(((varn == 3/5*varz) || boolvar && num/3*nonso <12) && (ciao != "Hello")) || || bool2

(((A * A*A*A) * A * A*A*A *A) * (A * A)) * * A

(((A*A*A*A)*A*A*A*A*A)*(A*A))**A

A*A*A*A*A*A*A*A*A*A*A**A

Questa alla fine contiene ** e non è valida

All'incirca è quel che fò io, l'unica differenza è che elimini in un colpo solo le parentesi. Devo vedere se non ho controindicazioni con i controlli che eseguo...

**danielej** · 02-06-2010, 09:37

Sicuramente l'impatto massimo sulle prestazioni c'è dalla verifica dei contenuti di ciascuna parentesi, che per k parentesi innestate richiede n^k iterazioni

Poi rileggendo mi è venuto in mente un evento imprevisto nella sostituzione delle parentesi con quanto ho scritto, prima di cambiarle va aggiunto il controllo "(Operatore binario" = errore, "Operatore binario)" = errore , altro passaggio lineare comunque.

(a+b)-c (valida) -> a+b-c (valida)

Quello che non andava era ad esempio la verifica di:
(a+)c (non valida, operatore binario da solo) -> a+c (valida)

Comunque se con la regex si riescono a sostituire tutti gli operatori binari con uno unico sempre uguale per me le verifiche si fanno più semplici.

**TheVice** · 02-06-2010, 19:39

hmmm, se hai bisogno di controllare anche la precedenza degli operatori temo che il mezzo più efficiente resti il classico parsing a discesa ricorsiva che ti trasforma l'espressione dalla notazione in-fissa a quella pre-fissa in cui diventa più semplice gestire gli operatori e gli operandi.