[Java] RegEx zur Termvalidierung

Dieses Thema im Forum "Programmierung & Entwicklung" wurde erstellt von Mr. Mouse, 24. Juli 2012 .

Schlagworte:
  1. 24. Juli 2012
    Zuletzt bearbeitet: 24. Juli 2012
    RegEx zur Termvalidierung

    Da ich ja z.Z. einen Taschenrechner programmiere habe ich einen RegEx geschrieben der den eigegebenen Term validieren soll. Der RegEx sieht so aus:

    Code:
    [\\-]?[(]?([\\-]?[(]+)*[\\-]?[0-9]+([\\.]{1}[0-9]+)?([\\+\\-\\*\\/\\^\\%RL]{1}[(]*[-]?[0-9]+([\\.]{1}[0-9]+)?[)]*)+
    Wieso matcht der auf "(5+5)*3" aber nicht auf "(5+5)^2"

    Ich dreh hier noch durch^^ wäre cool wenn mir da einer helfen könnte.

    //edit

    R steht bei mir für Wurzel und L für Logarithmus

    ~m
     
  2. 24. Juli 2012
    Zuletzt bearbeitet: 24. Juli 2012
    AW: RegEx zur Termvalidierung

    falscher ansatz.
    du kannst einen mathematischen term nicht mit einem regulären ausdruck validieren.

    wenn du das wirklich selber machen willst, musst du den term zuerst in tokens zerlegen (zahlen, operatoren, wörter[funktionen]) und dann mit nem parser abarbeiten.

    wenn du viel zeit hast und nachts schlecht einschläfst empfehle ich dir folgendes buch: Create Your Own Programming Language

    darin findest du gute beispiele für lexer/parser (generatoren) usw.
    viel spaß
     
  3. 24. Juli 2012
    AW: RegEx zur Termvalidierung

    Hallo!

    Mit einer RegExpr kann man keinen mathematischen Term validieren.
    Mithilfe eines Push-Down-Automaten bzw. einer dazugehoerigen Grammatik wuerde es gehen, wenn du dich in dem Gebiet auskennst.

    Mfg,

    Kolazomai
     
    1 Person gefällt das.
  4. 24. Juli 2012
    AW: RegEx zur Termvalidierung

    aber das muss so doch auch irgendwie gehen^^

    ich versteh nicht wieso der bei dieser form alle opratoren funktionieent, nur "^" nicht :/

    muss ja irgendwo hier liegen:

    Code:
    [\\+\\-\\*\\/\\^\\%RL]{1}
    Und wieso sollte dass nicht gehen?

    Bis jez hat es wunderbar geklappt
     
  5. 24. Juli 2012
    Zuletzt bearbeitet: 24. Juli 2012
    AW: RegEx zur Termvalidierung

    Hallo!

    Das geht nicht wegen dem "Pumping Lemma für regulaere Sprachen"
    Du kannst ja beliebig haeufig "Klammer auf" machen, dafuer muss es aber immer wieder eine "Klammer zu" geben. Dein regulärer Ausdruck kann die "Klammern auf" nicht zaehlen und sich merken, weil du keinen internen Speicher hast (wie bei Pushdown-Automaten). Folglich ist es nicht ueberpruefbar, ob es genausoviele "Klammern auf" wie "Klammern zu" gab. Deshalb kann ein mathematischer Ausdruck nicht von einer RegExp erfasst werden (ausser es gibt irgendeine Moeglichkeit der Selbstreferenzierung, dann koennte man das induktiv aufbauen; soweit ich weiss nicht moeglich).

    Mfg,

    Kolazomai
     
  6. 24. Juli 2012
    AW: RegEx zur Termvalidierung

    Ja okay, das stimmt, aber da mache ich, nachdem ich den string durch diesem RegEx geschickt habe. Sollte keine syntaktisch korrekte Klammersetzung erfolgt sein, gibts nen Error.

    Wie müsste ich denn meine RegEx ändern damit mein Problem aus dem OP gelöst wird?
     
  7. 24. Juli 2012
    AW: RegEx zur Termvalidierung

    ein weiteres problem sehe ich in ausdrücken innerhalb von ausdrücken:
    (1 + (2 + (3 + 4)))

    versuch das mal in einen regexp zu packen.
    formal wäre das <Expression Operator Expression> und somit unmöglich, da sich das endlos im regulären ausdruck wiederholen müsste.
     
  8. 24. Juli 2012
    AW: RegEx zur Termvalidierung

    Hab ich drin und läuft.

    Du kannst in einem RegEx Klammern setzten und den umklammerten Ausdruck beliebig oft wiederholen lassen.

    Jage ich deinen Term durch mein Programm bekommen ich als Ergebnis 10, so wie es sein soll.
     
  9. 24. Juli 2012
    AW: RegEx zur Termvalidierung

    wen dir hier geschrieben wird, dass du mit einem regex mathematische ausdrücke nicht validieren kannst, dann glaub den leuten doch.
    es haben ein oder zwei vielleicht schon mal was damit zu tun gehabt und es gibt schlaue artikel die dies beweisen.
    du kannst vielleicht für x ausdrücke ein reg ex bauen aber für den x+1 geht es dann wieder schief.
    benutze eine andere methode
     
  10. 24. Juli 2012
    AW: RegEx zur Termvalidierung

    Hallo!

    Ja, aber hier ist doch die Selbstreferenzierung. Dein regulaerer Ausdruck muss sich selbst "umklammern" koennen, ungefaehr so:
    Code:
    korrekterTerm = (korrekterTerm)*
    Das kriegst du (fuer alle moeglichen Faelle, egal wie gross) nicht hin, unter anderem aus dem von mir vorher aufgefuehrten Grund ("Pumping Lemma fuer Regulaere Sprachen"), den ich vorher konkret versucht habe zu erklaeren (und Murdoc hat noch ein Beispiel gegeben).

    Mfg,

    Kolazomai
     
  11. 24. Juli 2012
    AW: RegEx zur Termvalidierung

    Theoretisch ist ein einfacher term doch so aufgebaut:

    Term: (5+3)^2

    part1{1}(part2)+

    part1 = (5
    part2[0] = +3)
    part2[0] = ^2

    Und das geht immer so weiter.

    Ich hätte mal gerne ein Beispiel wo meine Theorie nicht drauf zutrifft

    Wir gehen davon aus, dass die Operatoren festgelegt werden und natürlich auch im RegEx auftauchen. Des Weiteren haben wir erstmal nur Teilterme der Form:

    OperandOperatorOperand

    Klammern können beliebig viele gesetzt werden, solange syntaktisch korrekt.

    Überprüfung, ob es wirklich NUR Pärchen gibt, folgt erst NACH diesem Regex.
     
  12. 24. Juli 2012
    Zuletzt bearbeitet: 24. Juli 2012
    AW: RegEx zur Termvalidierung

    für jemanden, der sich mit der theoretischen informatik und speziell mit regulären/kontextfreien sprachen noch nicht auseinandergesetzt hat, ist das vielleicht nich direkt ersichtlich^^

    wenn du ihm jetzt was von nem pumping lemma erzählst, hilft ihm das wahrscheinlich recht wenig.


    wie überprüfst du, ob die klammern korrekt gesetzt sind? das musst du dann ja irgendwie rekursiv machen oder nich?
    eigentlich wäre die überprüfung, ob die anzahl der klammern stimmt damit auch schon erledigt, da die klammern nich korrekt gesetzt sein können, wenn mehr klammern aufgehen als zugehen^^
    aber wie gesagt, mit RegEx leider nich möglich, da die klammern viel zu verschachtelt sein können.
     
  13. 24. Juli 2012
    AW: RegEx zur Termvalidierung

    Durch meinen RegEx werden bestimmte Fehler schon im voraus ausgeschlossen.

    z.B. geht (5+3) jedoch nicht (5+3(

    da aber sowas wie ((5+3) geht, lasse ich nach erfolgreicher Validierung den String durchlaufen mit 2 Countern, einen für "(" und einen für ")".

    Ist diese Anzahl nachher genau gleich, dann kann es keine Fehler in der Klammersetzung geben.
     
  14. 24. Juli 2012
    AW: RegEx zur Termvalidierung

    Geht einwandfrei

    Code:
    java -jar calc.jar -c (5+3)*4*(6+4)
    Ergebnis: 320
     
  15. 24. Juli 2012
    AW: RegEx zur Termvalidierung

    das ist falsch. richtig wäre:

    Code:
    Ausdruck:
     '(' Ausdruck ')'
     | Ausdruck Operator Ausdruck
     | Operand
    __vereinfacht gesagt__
     
  16. 24. Juli 2012
    Zuletzt bearbeitet: 24. Juli 2012
    AW: RegEx zur Termvalidierung

    Hey!

    @Prrovoss: Ich wollte nur mal das Stichwort reinschmeissen, dann kann sich der Threadersteller selber ueber Google etc. informieren, wenn er am Thema interessiert ist.

    @Mr. Mouse: Halten wir fest: Nur mit einer RegExp geht es nicht! Wenn du noch zusaetzlich etwas programmieren willst, dann gibt es bestimmt die ein oder andere Moeglichkeit.

    Die "einfachste" (beste?!) Loesung waere ein Push-Down-Automat (auch Kellermaschine/Stackmaschine genannt). Ansonsten kriegt mans vielleicht auch irgendwie mit verschiedenen RegExp und For-Schleifen hin. Die von mir vorgeschlagene Variante bietet sich aber dafuer an und das macht alle Welt - aus gutem Grund - auch so

    Mfg,

    Kolazomai
     
  17. 24. Juli 2012
    AW: RegEx zur Termvalidierung

    Okay, dann schonmal danke für die Hilfe!

    Wäre es nicht theoretisch am besten wenn ich den Term einfach direkt in einen BinaryTree parse?
     
  18. 24. Juli 2012
    Zuletzt bearbeitet: 24. Juli 2012
    AW: RegEx zur Termvalidierung

    willst du den term wirklich selber parsen (sprich: zerlegen, nen ast bauen und dann reduzieren), oder nur validieren und dann von deiner laufzeitumgebung auswerten lassen?

    Parser – Wikipedia sollte dir helfen
     
  19. 24. Juli 2012
    AW: RegEx zur Termvalidierung

    Hallo!

    Ein binaerer Baum ist eine Darstellungsform. Die Wurzel ist dann der Operand, die Blaetter wiederum selbst Wurzeln oder Zahlen. Die programmiertechnische Umsetzung kann man auf verschiedenste Art und Weise loesen.

    Mfg,

    Kolazomai
     
  20. 24. Juli 2012
    AW: RegEx zur Termvalidierung

    Zur Zeit mache ich es so, keine Ahnung ob es vllt zu umständlich ist:

    1. Ich übergebe den Term als String.

    2. Überprüfung auf eine gerade Anzahl von Klammerpaaren.

    3. Immer die nächste oder innerste Klammer suchen, substring bilden.

    4. substring durch meine calculate() Methode schicken, welche 2xdouble und 1*char (Operator) annimmt und das ERgbnis als String ausgibt.

    5. Klammerausdruck durch den String von calculate() ersetzen

    Beispiel:

    1. ((5+4)*3)/(5-3)

    2. (9*3)/(5-3)

    3. 27/(5-3)

    4. 27/2

    5. 13.5

    Das geht auch wunderbar und hatte bis jez keine Probleme.

    Mein eigentliches PRoblem war ja, das mein regex (5-3)*3 aber nicht (5-3)^3 zulässt.
     
  21. 25. Juli 2012
    Zuletzt bearbeitet: 25. Juli 2012
    AW: RegEx zur Termvalidierung

    folgendes wertet dein regexp als richtig:
    Code:
    ^1+1(1(1))1+(()())
    oder
    Code:
    5-3)^3)((
    und durch die überprüfung der klammern kommen beide ausdrücke auch durch.
     
  22. 25. Juli 2012
    AW: RegEx zur Termvalidierung

    Für mathematische Ausdrücke kannst du sehr gut die Reverse Polish Notation zur Berechnung verwenden. Einen Ausdruck in Infix-Schreibweise lässt sich durch den Shunting-yard-Algorithmus in die RPN umschreiben.

    Die Wikipedia-Artikel dazu erklären so gut wie alles nötige.
     
  23. 25. Juli 2012
    AW: RegEx zur Termvalidierung

    Nein, das lässt mein RegEx eben nicht durch Hab ihn schon ziemlich strikt geschrieben!

    Und Klammerpaare werden bei mir nur in der Reichen folge "(" <irgendwas dazwischen ")" zugelassen.

    @Chillikid

    Polish Notation hab ich mir auch schon angeguckt. Dann muss man den Term trptzdem validieren und nach in die notation parsen.
     
  24. 25. Juli 2012
    AW: RegEx zur Termvalidierung

    Ich versuche es jetzt mal mit der postix form. Erstmal jez nen Parser basteln.
     
  25. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.