Arithmetische Sytntax prüfen

[Mike]

Hallo Liste,

ich stehe gerade vor einem Problem und weiß nicht so ganz wie ich anfangen soll. Der Anwender gibt in ein Eingabefeld eine Formel ein. Dazu darf er Zahlen, Platzhalter, die Operatoren + - * /^ und Klammern verwenden, z.B. 3*(a^2+2b)

Um keinen Unsinn in die DB zu schreiben sollte diese Eingabe natürlich auf richtige Syntax überprüft werden. Gibt es da einen Trick oder muss ich da zur Uni und Algebra Bücher wälzen? Geht das dann übehaupt mit JavaScript?

Danke für jeden Tip,

Mike

[Sven Rautenberg]

Moin!

ich stehe gerade vor einem Problem und weiß nicht so ganz wie ich anfangen soll. Der Anwender gibt in ein Eingabefeld eine Formel ein. Dazu darf er Zahlen, Platzhalter, die Operatoren + - * /^ und Klammern verwenden, z.B. 3*(a^2+2b)

Du erlaubst also eine gewisse Syntax, deren Regeln sich gottseidank an die der Mathematik anlehnen.

Um keinen Unsinn in die DB zu schreiben sollte diese Eingabe natürlich auf richtige Syntax überprüft werden. Gibt es da einen Trick oder muss ich da zur Uni und Algebra Bücher wälzen? Geht das dann übehaupt mit JavaScript?

Mit Javascript geht das auch. Ich denke aber, du unterschätzt die Komplexität deiner Aufgabe ganz erheblich.

Im Prinzip willst du (du weißt es nur noch nicht) einen Parser schreiben, der die Syntax der Formel analysiert und sein OK dazu gibt. Dazu mußt du den eingegebenen String in seine einzelnen Bestandteile (der Fachmann spricht von Token) zerlegen, diese Token zueinander in Beziehung setzen, einen Parsebaum aufbauen und im Erfolgsfall (wenn alles stimmt) grünes Licht geben - andernfalls eben "Syntax Error".

Da ich "Javascript" gelesen habe: Damit geht das natürlich grundsätzlich auch, aber wenn du verhindern willst, dass Blödsinn in die Datenbank kommt, mußt du die Prüfung serverseitig durchführen. Javascript kann lediglich dem Benutzer etwas helfen, Fehler schon vor dem endgültigen Abschicken zu erkennen.

Ich frage mich aber: Was willst du mit solch einer Formel-Eingabe erreichen? Doch nicht etwa auf dem Server rechnen? Das könnte unter Umständen böse enden, wenn du die Syntax nicht wirklich vollständig prüfst - insbesondere auf eingeschleppten bösen Programmcode. Denn die Formel darf wirklich nichts anderes tun als rechnen. Vereinfachungen wie "eval()" sind da definitiv nichts, was man anwenden sollte (allenfalls als Schnellprüfung mit Javascript noch _vor_ dem Eintragen in die DB).

- Sven Rautenberg

[Mike]

ich stehe gerade vor einem Problem und weiß nicht so ganz wie ich anfangen soll. Der Anwender gibt in ein Eingabefeld eine Formel ein. Dazu darf er Zahlen, Platzhalter, die Operatoren + - * /^ und Klammern verwenden, z.B. 3*(a^2+2b)

Mit Javascript geht das auch. Ich denke aber, du unterschätzt die Komplexität deiner Aufgabe ganz erheblich.

Das ist mein Problem, ich weiß wenn man es vollständig (das mach ich ja am Server) macht ist es ziemlich komplex. Aber es sollte eben auf Clientseite auch passieren, um schnelleres Feedback zu geben. Was kann man da machen?

Ich frage mich aber: Was willst du mit solch einer Formel-Eingabe erreichen? Doch nicht etwa auf dem Server rechnen? Das könnte unter Umständen böse enden, wenn du die Syntax nicht wirklich vollständig prüfst - insbesondere auf eingeschleppten bösen Programmcode. Denn die Formel darf wirklich nichts anderes tun als rechnen.

Die Formel ist Grundlage für Auswertungen. Da diese etwas kompliziert sind, haben wir im Backend ein C++ System, das die Dinger rechnet. Ans Web angeschlossen ist es mit ColdFusion via Com Java Bridge.

Mike

[Sven Rautenberg]

Moin!

Das ist mein Problem, ich weiß wenn man es vollständig (das mach ich ja am Server) macht ist es ziemlich komplex. Aber es sollte eben auf Clientseite auch passieren, um schnelleres Feedback zu geben. Was kann man da machen?

Ok, es gibt natürlich Möglichkeiten. :)

Zunächst aber:
DISCLAIMER: Die hier vorgestellte Idee eignet sich bestenfalls als Vorauswahl in Javascript, um ganz bös falsche Formeln nicht ins System reinzuslassen. Serverseitige Kontrollen müssen explizit den Parsebaum aufbauen und kontrollieren - bei Javascript schadet sich der User durch falschen oder angreifenden Code allerhöchstens selbst.

So, nachdem die Haftungsfragen geklärt sind, mein Vorschlag:

Logischerweise enthält deine Formel nicht alle 256 verschiedenen Zeichen, sondern nur eine geringe Auswahl davon. Das wäre der erste Ansatz für eine Kontrolle: Sind falsche Zeichen drin. Ein regulärer Ausdruck mit einer Zeichenklasse erledigt das in einem Schritt.

Dann die Klammern: Die kann man ja mal simpel durchzählen. Sind gleichviele öffnende und schließende Klammern enthalten? Es wäre besser, wenn dem so ist.

Und als letzer Schritt würde ich den eingegebenen String mal im Javascript-eval() ausführen lassen. Ich habe keine Ahnung, was eval() so an Rückgabe liefert, aber vielleicht läßt sich damit ja feststellen, ob der übergebene Code korrekt ist oder nicht.

- Sven Rautenberg

[Mike]

Hi Sven,

die eval Funktion klappt super! Einfach in der Formal alle Platzhalter mit z.B. 1 ersetzen und dann den String an eval() übergeben. Eval liefert einen Fehler, falls der String nicht berechnet werden kann. Diesen einfach mit try und catch abfangen und schon haben wir die Test-Routine!

Vielen Dank für den Tip. Und jetzt geht es ans Eingemachte: Den Java Parser.

Mike

Und als letzer Schritt würde ich den eingegebenen String mal im Javascript-eval() ausführen lassen. Ich habe keine Ahnung, was eval() so an Rückgabe liefert, aber vielleicht läßt sich damit ja feststellen, ob der übergebene Code korrekt ist oder nicht.

»»

[Alexander]

Hi,

die eval Funktion klappt super! Einfach in der Formal alle Platzhalter mit z.B. 1 ersetzen und dann den String an eval() übergeben. Eval liefert einen Fehler, falls der String nicht berechnet werden kann.

Hmm, so einfach würde es mir an deiner Stelle nicht machen. Wenn Du z.B. einen solchen Ausdruck hast, ist der für a = 1 und b != 1 sehr wohl definiert, nach deiner "Prüfung" allerdings nicht: a/(1-b)

Ich weiss ja nicht, welche Randbedinungen du für die Varaiblen vorgibst, aber einfach alle Varaiblen durch den selben Wert zu ersetzen, ist eine fragwürdige Methode. Ich würde das nicht so machen, sondern jeder Variablen einen anderen Wert zuweisen.

Viele Grüße...

Alex :)

[Alexander Foken]

Moin Moin !

Hmm, so einfach würde es mir an deiner Stelle nicht machen. Wenn Du z.B. einen solchen Ausdruck hast, ist der für a = 1 und b != 1 sehr wohl definiert, nach deiner "Prüfung" allerdings nicht: a/(1-b)
Ich weiss ja nicht, welche Randbedinungen du für die Varaiblen vorgibst, aber einfach alle Varaiblen durch den selben Wert zu ersetzen, ist eine fragwürdige Methode. Ich würde das nicht so machen, sondern jeder Variablen einen anderen Wert zuweisen.

Das ist leider kein Stückchen besser.

Nimm a=12345, b=67890 und als Formel "a/(67890-b)": Kabooom!

Nimm a=2.76, b=3.1415 und als Formel "a/(3.1415-b)": Kabooom!

...

Nimm a=10, b=5 und als Formel "a*2*b/(a-2*b)": Kaboom!

Ohne einen vernünftigen Parser ist eval nur bedingt geeignet, die Formeln zu prüfen, egal welche Werte Du für Variable einsetzt.

Was ist mit Ausdrücken, die zwar in JS, aber nicht im Backend gültig sind?

Die "Formel" "window.name.length" ist durchaus in JS gültig.

Was ist, wenn das Backend die Formeln in mathematisch-fauler Notation ohne explizite Multiplikationsoperatoren akzeptiert? "2ab-4cd+8ef" mag das Backend mögen, JS nicht.

Alexander

[Sven Rautenberg]

Moin!

Das ist leider kein Stückchen besser.

Nimm a=12345, b=67890 und als Formel "a/(67890-b)": Kabooom!

Bei Opera teilt das eval() wunderbar durch Null und liefert als gültiges Ergebnis "infinity" zurück, während mangelhafte (für Javascript) Rechenausdrücke mit einem Javascriptfehler beantwortet werden.

Ich denke, das Problem ist, dass man abschätzen muß, wie problematisch es ist, den vollständigen Parser-Algorithmus nochmal in Javascript zu implementieren, wenn doch der einzige Vorteil ist, sich einmal Formularabschicken zu sparen.

Ok, logischerweise sollte der Ersatzalgorithmus nichts Richtiges als falsch zurückweisen, aber wenn er alles Richtige als richtig durchläßt, und zusätzlich nur ganz wenig Falsches als richtig, dann ist schon etwas gewonnen.

- Sven Rautenberg

[Philipp Hasenfratz]

Halihallo Sven

Nimm a=12345, b=67890 und als Formel "a/(67890-b)": Kabooom!
Bei Opera teilt das eval() wunderbar durch Null und liefert als gültiges Ergebnis "infinity" zurück

Was meiner bescheidenen mathematischen Kenntnissen nach falsch ist.

Die Umkehrfunktion von Division ist Multiplikation, das neutrale Element 1, folglich:

1. für jedes a aus N nehmen wir an: a/0=x; x=infinity
2. x*0=a => a müsste 0 sein, aber aus 1) kann "a" jede natürliche Zahl sein.

=> a/0 darf nicht zulässig sein, da die Funktion nicht reversibel (bijektiv, glaube ich)
wäre.

Das Ergebnis "infinity" ist nicht nur im Umgang mit Computern falsch, da der Computer
nicht in der Lage ist das Ergebnis in eine Zahl abzubilden, sondern ist mathematisch
unmöglich. Somit ist es falsch von Opera, keinen Fehler auszugeben.

Möglich wäre:

lim(für n->infinity) von a/(C/n)   ; C ist eine Konstante aus Z z.B.

da lim(n->infinity) von C/n gegen null strebt, strebt lim(n->infinity) von a/(C/n) gegen
unendlich (infinity) oder minus unendlich (depends on sign(a)). Das wäre mathematisch
korrekt(er), nicht jedoch ohne den Limes.

Man möge mir jetzt die korrekte mathematische Beschreibung nennen, aber den Sinn habe
ich IMHO verstanden, glaube ich.

Kleiner mathematischer Exkurs, ich hoffe ich habe nicht allzuviele Kenntnisse verloren ;)

Viele Grüsse

Philipp