Hallo,
gibt es einen regulären Ausdruck, bzw. kann es einen regulären Ausdruck geben, um arithmetische Ausdrücke (also eine ‚Rechnung‘ wie (3+4*(6/4+(6*-8)+7)) ) zu validieren?
Das Problem schein mir, dass es im Prinzip eine unendlich tiefe Verschachtelung von Klammern geben kann, weshalb ich auf keine Lösung kommen konnte.
Vielleicht liest das hier ja ein kluger Kopf, der weiter weiß? (Mir reicht ein Ausdruck für die vier Grundrechenarten (±*/) und ganze Zahlen.)
Vielen Dank für jede Antwort!
Hallo
gibt es einen regulären Ausdruck, bzw. kann es einen regulären
Ausdruck geben, um arithmetische Ausdrücke (also eine
‚Rechnung‘ wie (3+4*(6/4+(6*-8)+7)) ) zu validieren?Das Problem schein mir, dass es im Prinzip eine unendlich
tiefe Verschachtelung von Klammern geben kann, weshalb ich auf
keine Lösung kommen konnte.
Ja, kann man. Nach herkömmlicher
Perl-Weisheit wird es auf einen
regulären Ausdruck $rg der üblichen Form:
my $rg;
$rg = qr{ \(
(?:
(?\> [^()]+)
|
(??{$rg})
)\*
\)
}x;
hinauslaufen, welcher verschachtelte
Klammerausdrücke ‚matcht‘.
Kannst Du mehr verraten? Welche Sprache, welche
Randbedingungen etc.
Grüße
CMБ
gibt es einen regulären Ausdruck, bzw. kann es einen regulären
Ausdruck geben, um arithmetische Ausdrücke (also eine
‚Rechnung‘ wie (3+4*(6/4+(6*-8)+7)) ) zu validieren?
Hi Klaus,
was genau heißt denn validieren, ausrechnen?
In Excel-Vba wäre das dann so:
Sub tt()
MsgBox Evaluate(3 + 4 * (6 / 4 + (6 * -8) + 7))
End Sub
Dann wird -155 angezeigt.
Gruß
Reinhard
Das Problem schein mir, dass es im Prinzip eine unendlich
tiefe Verschachtelung von Klammern geben kann, weshalb ich auf
keine Lösung kommen konnte.Vielleicht liest das hier ja ein kluger Kopf, der weiter weiß?
(Mir reicht ein Ausdruck für die vier Grundrechenarten (±*/)
und ganze Zahlen.)Vielen Dank für jede Antwort!
Vielen Dank für die Antwort!
Ja, kann man. Nach herkömmlicher
Perl-Weisheit wird es auf einen
regulären Ausdruck $rg der üblichen Form:my $rg;
$rg = qr{ (
(?:
(?> [^()]+)
|
(??{$rg})
)*
)
}x;hinauslaufen, welcher verschachtelte
Klammerausdrücke ‚matcht‘.Kannst Du mehr verraten? Welche Sprache, welche
Randbedingungen etc.
Sorry, klar kann ich mehr verraten: Soweit war ich auch schon, allerdings lassen sich diese zirkulären Ausdrücke nicht in jeder Sprache umsetzten, weshalb ich wissen wollte, ob es auch eine andere Lösung gibt. Ich will den Ausdruck in einem XML-Schema/XSD-Dokument zur Typisierung eines Attributs verwenden. Und da lässt sich sowas leider nicht machen. Auch mit XML-Entitäten (&term; etc.) lassen sich keine zirkulären Ausdrücke erstellen…
Gruss, Klaus
Hallo Reinhard,
VBS kann’s auch:
msgbox eval("12+3")
dann geht eine Box auf, in der ‚15‘ steht. 
Gruß, Rainer
Das Problem schein mir, dass es im Prinzip eine unendlich
tiefe Verschachtelung von Klammern geben kann, weshalb ich auf
keine Lösung kommen konnte.
Genau das ist der Grund, warum es nicht geht. Reguläre Ausdrücke sind dafür ein zu schwacher Formalismus. Du kannst allerdings Grammatiken (context-freie Grammatiken z.B.) dafür verwenden. Dann schaut das ganze z.B. so aus:
factor = zahl | „(“ expr „)“
term = factor { * factor }
expr = term { + term }
mfg
eine Idee
Hi,
ich werf mal eine Idee in die Runde.
Mit reinen reg. Ausdrücken fällt mir nichts ein aber zusammen mit ein klein wenig programmieraufwand.
‚Rechnung‘ wie (3+4*(6/4+(6*-8)+7)) ) zu validieren?
Schritt 1: Zähle die Anzahl der des Zeichens „(“ (die muß gleich sein der Anzahl der „)“ Zeichen.
Schritt 2: Schleife von von 0 bis zur Anzahl
in der Schleife:
Schritt 3: Ermittle letzes Vorkommen des Zeichens „(“ und das nächste Zeichen ab dieser Stelle „)“
Schritt 4: Hol diesen String und validiere mit reg.Ausdrück ob es eine math. Operation ist. (Dies sollte einfach sein)
Schritt 5: Rechne den Ausdruck aus. Dies ist etwas aufwendiger. Zahlen suchen und konvertieren und die 4 Rechenarten suchen.
Schritt 6: Ersetze den String mit dem Ergebniss das du bekommen hast.
Nun springt er wieder an den Anfang der Schleife und sucht wieder die innerste Klammer.
Ersetzt diese und macht weiter.
Bei (3+4*(6/4+(6*-8)+7)) würde nach dem ersten durchlauf stehen bleiben
(3+4*(6/4±40+7))
nun sucht er das (6/4±40+7)
dies sollte er rechnen können.
und stehen bleibt (3+4*-31,5)
und dann den Rest.
Würde das gehen ?
Ich denke nur das das richtige Rechnen beachtet werden muß.
z.B. bei „6/4±40+7“
Auch sowas sollte damit gehen
(5*(2+6)+(45/2))*(456-5(2+2))
Er würde erst den hinteren Teil zusammen ziehen dann der Vorderen nach und nach.
Ich habe es selbst nicht ausprobiert.
Wenn nicht - es war nur ein Gedanke
Du kannst
allerdings Grammatiken (context-freie Grammatiken z.B.) dafür
verwenden.
Genau das tue ich auch. Dazu hab ich einen Scanner+Interpreter gebaut, der mir diese LL(k)-Grammatik verarbeitet.
Jetzt möchte ich aber zur Laufzeit der Anwendung über eine XML-Datei (siehe Artikel unten) den zu parsenden Text einlesen. Und für die Ersteller der XML-Datei soll ein XML-Schema existieren, womit die XML-Datei validiert werden kann. Ich möchte ungern ein zusätzliches Tool mitliefern, dass den Text validiert, sondern dem Anwender es ermöglichen schon während des Schreibens des Texts zu sehen, ob die Syntax richtig ist. Einige XML-Editoren unterstützen eben diese Echtzeit-Validierung anhand eines XML-Schemas.
was genau heißt denn validieren, ausrechnen?
Zitat von http://de.wikipedia.org/w/index.php?title=Validierun…:
In der Softwaretechnik bezeichnet Validierung (auch Plausibilisierung,
als Test auf Plausibilität, oder engl. Sanity Check genannt) die
Kontrolle eines konkreten Wertes darauf, ob er zu einem bestimmten
Datentyp gehört oder in einem vorgegebenen Wertebereich oder einer
vorgegebenen Wertemenge liegt.
Schritt 4: Hol diesen String und validiere mit reg.Ausdrück ob
es eine math. Operation ist. (Dies sollte einfach sein)
Schritt 5: Rechne den Ausdruck aus. Dies ist etwas
aufwendiger. Zahlen suchen und konvertieren und die 4
Rechenarten suchen.
naja naja…
also so einfach? ich weiss ja nicht…
vor allem dann, wenn man sich eben nicht auf die vier GRUNDrechenarten beschränken will, sondern auch mal ein sinus, cosinus, tangens, (quadrat/n-te)-wurzel, exponential- oder Betragsfunktionen usw mit einbauen möchte…
Und dann gibts ja auch noch pi 
und was ist, wenn in der Rechnung nun auch noch die Größenangaben stehen?
400 m² + 10 km² usw…
oder 48 min + 1,5 h
also wenns flexibel sein muss gehört noch einiges mehr dazu fürchte ich…
In der Softwaretechnik bezeichnet Validierung (auch Plausibilisierung,
als Test auf Plausibilität, oder engl. Sanity Check genannt) die
Kontrolle eines konkreten Wertes darauf, ob er zu einem bestimmten
Datentyp gehört oder in einem vorgegebenen Wertebereich oder einer
vorgegebenen Wertemenge liegt.
Hallo Klaus,
danke für die Info, dann wäre der angesagte Term sowieso unplausibel weil da ne Klammer fehlt bzw zuviel ist.
Jetzt erst habe ich die Anfrage konkret verstanden, ja, es geht, daß du einen Term (also einen mathematischen Ausdruck wie (3+4)) zerlegst um ihn dann zu berechnen.
Das geht alles, ist aber sehr sehr aufwändig, weil man alle Eventualitäten bedenken muss.
Weil, wie schon gesagt, die Anzahl der öffnenden und schliessenden Klammern zu vergleichen ist kein Akt, aber ob die Klammersetzung Sinn macht wird zum Problem.
Gruß
Reinhard
Hallo Klaus,
von der theoretischen Ecke aus gesehen,
sind Reguläre Ausdrücke äquivalent zu Endlichen Automaten,
und die können nur konstant viele Dinge zählen,
d.h. die Verschachtelungstiefe der Klammern wäre begrenzt.
Mit dem Pumping-Lemma ( http://de.wikipedia.org/wiki/Pumping-Lemma)
lässt sich nachweisen, dass es keinen regulären Ausdruck für die Klammersprache
gibt.
Hoffe, dies Negativ-Resultat hilft Dir weiter
Thorsten
Hallo,
gibt es einen regulären Ausdruck, bzw. kann es einen regulären
Ausdruck geben, um arithmetische Ausdrücke (also eine
‚Rechnung‘ wie (3+4*(6/4+(6*-8)+7)) ) zu validieren?Das Problem schein mir, dass es im Prinzip eine unendlich
tiefe Verschachtelung von Klammern geben kann,
Hallo Thorsten
von der theoretischen Ecke aus gesehen,
sind Reguläre Ausdrücke äquivalent zu Endlichen Automaten,
und die können nur konstant viele Dinge zählen,
d.h. die Verschachtelungstiefe der Klammern wäre begrenzt.
„Reguläre Ausrücke“, sprich: die unter
diesem Namen verbreiteten Minisprachen
*sind* nichtregulär (insbesondere als
N FA implementiert) und könnten daher
auch beliebig tief verschachtelte Klammern
auflösen.
Mit zwei „Erscheinungsformen“, nämlich Perl 5.x und
PCRE 7.x habe ich das gelegentlich angewendet.
Also: die nichtregulären regulären Ausdrücke können
das, die anderen nicht
Grüße
CMБ
… (insbesondere als
N FA implementiert) und könnten daher
auch beliebig tief verschachtelte Klammern
auflösen.
NFAs sind äquivalent zu DFAs und regulären Ausdrücken,
die helfen da also nicht weiter und können ebenfalls
die Klammersprache nicht erkennen.
Mit zwei „Erscheinungsformen“, nämlich Perl 5.x und
PCRE 7.x habe ich das gelegentlich angewendet.
Das Perl solche Erweiterungen hat,
mag sein … wie sieht ein passender regülarer Ausdruck
für die Klammersprache in Perl aus?
Hallo,
gibt es einen regulären Ausdruck, bzw. kann es einen regulären
Ausdruck geben, um arithmetische Ausdrücke (also eine
‚Rechnung‘ wie (3+4*(6/4+(6*-8)+7)) ) zu validieren?Das Problem schein mir, dass es im Prinzip eine unendlich
tiefe Verschachtelung von Klammern geben kann, weshalb ich auf
keine Lösung kommen konnte.
die haben gluabe ich dein problem geloest.
http://www.pcre.org/pcre.txt und dann der abschnitt RECURSIVE PATTERNS
implementiert xsd pcre?
schwääre kost
Hallo Klaus,
ich würde erst einmal alle „Whitespaces“ entfernen und dann prüfen, ob eine der Zeichenketten „)[0-9]+“, „[±*/])“, „([±*/)]“ oder „[±*/][±*/]“ (evtl. geht hierfür auch „([±*/])\1“) existiert. Falls ja, dann dürfte die Zeichenkette nicht valide sein.
Ich habe hoffentlich alle invaliden Folgen bedacht.
Jetzt entfernst Du noch alles außer den Klammern aus der Zeichenkette und ersetzt solange „()“ durch nichts, bis keine Ersetzung mehr möglich ist. Bleibt ein leerer String übrig, ist die Zeichenkette valide, ansonsten nicht.
Was hältst Du davon?
Gruß
Volkmar
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
stimmt
Hi,
Ja, stimmt.
Wenn soetwas berücksichtigt werden soll dann wirds komplizierter.
Ich denke möglich wäre meine Idee schon aber ich würde das auch nur so machen wenn ich es machen müßte und absolut keinen anderen Weg fände.
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
NFAs sind äquivalent zu DFAs und regulären Ausdrücken,
die helfen da also nicht weiter und können ebenfalls
die Klammersprache nicht erkennen.
Vielen Dank. Auch für den Hinweis auf das Pumping-Lemma
Das Perl solche Erweiterungen hat,
mag sein … wie sieht ein passender regülarer Ausdruck
für die Klammersprache in Perl aus?
hat Semjon Michailowitsch unten schon geschrieben:
http://www.wer-weiss-was.de/cgi-bin/forum/showarticl…
Jetzt weiß ich auf jeden Fall, dass ich diese Sprache nicht mit einem regulären Ausdruck in einem XML-Schema validieren kann und werde deshalb einen Parser zum testen verwenden.
die haben gluabe ich dein problem geloest.
http://www.pcre.org/pcre.txt und dann der abschnitt RECURSIVE
PATTERNS
Hatten wir unten schon, trotzdem vielen Dank.
Hallo Thorsten
Das Perl solche Erweiterungen hat,
mag sein … wie sieht ein passender regulärer
Ausdruck für die Klammersprache in Perl aus?
Ich hab mal ein ‚hands on‘-Beispiel für den
Hausgebrauch gebastelt (verbesserungen er-
wünscht):
use strict;
use warnings;
my $t\_ok = '(3+4\*(6/4+(6\*-8)+7))';
my $t\_no = '(3+4\*(6/4+(6\*-8)+7)))';
my $rg;
$rg = qr{ \(
(?:
(?\> [^()]+)
|
(??{ $rg })
)\*
\)
}x;
for ($t\_ok, $t\_no) {
my ($result) = /$rg/g;
(my $differ = $\_) =~ s/\Q$result\E//;
print '-'x59, "\n", ($\_ eq $result ? 'OK':'ERROR'), ": $\_ ==\> $differ\n";
}
Das liefert im beschriebenen Falle:
-----------------------------------------------------------
OK: (3+4\*(6/4+(6\*-8)+7)) ==\>
-----------------------------------------------------------
ERROR: (3+4\*(6/4+(6\*-8)+7))) ==\> )
Grüße
CMБ