Mathematischen String Parsen

[Newbie44]

Hallo,

ich habe Mathematische Strings vorliegen (zum Glück ohne Klammern)

Diese soll ich ausrechnen. Hier mal einer der Strings:

45 + 63 * 52 - 36

Wie jeder weiß hat die Multiplikation Vorrang. Wie Parse ich einen String in der Art? Die Sachen sind immer Variabel. Denn die Zweite Rechnung sieht so aus:

21 * 325 + 96 - 36

Die Programmiersprache ist egal, es geht ja ungefähr gleich da es die üblichen Stringfunktionen gibt.

Ich wäre euch dankbar, wenn Ihr mir etwas helfen könntet, wie Ich so einen String richtig zerlege

Gruß und danke im vorraus

Sebastian

[s-off]

Hallo,

zum Thema Mathe-Parser gibt es hier im Forum einiges - einfach mal die Suche bemühen; dafür ist sie schliesslich da.

Ich glaube, dass Dax vor kurzem ein recht umfangreiches Projekt diesbezüglich abgeben wollte.

[Newbie44]

Ja das habe ich bereits gesehen. Aber ich möchte es versuchen selbst zu machen. Ich möchte nicht komplexe Dinge reinbringen, sondern nur Simple aufgaben mit Klammern und einfachen Aufgaben lösen.

Was fertiges verwenden mag ja schön sein, jedoch lernt man da nichts dazu.

[s-off]

Zitat:

Zitat von Newbie44

Was fertiges verwenden mag ja schön sein, jedoch lernt man da nichts dazu.

Sehr löblich.

Allerdings sagte ich auch nicht, dass Du etwas fertiges verwenden sollst.

Ich habe damit beabsichtigt, dass Du Dir anhand fertiger - und vor allem funktionierender - Dinge das Thema selbständig näher bringst.

[Dax]

Zuerst löschst du alle Nichtzahl/operatorzeichen aus dem String, sodass dort nur noch '1+2*3+4' steht. Diesen String wirfst du in eine Funktion Calculate(), die den String zuerst bei '+' und '-' halbiert und sich jeweils mit diesen Argumenten selbst aufruft. Danach zerteilt diese Funktion den String bei '*' und '/' und ruft sich wiederum selbst damit auf. Findet die Funktion keinen Operator, muss es eine Zahl sein, also gibst du dort die Zahl zurück. Bei '1+2*3+4' käme ein solcher Aufrufbaum heraus (Calculate mit C abegkürzt):

Code:

C('1+2*3+4')
 C('1') + C('2*3+4')
  C('2*3') + C('4')
   C('2') * C('3')
  -> 6 + 4
 1 + -> 10
-> 11

[Christian Seehase]

Moin Sebastian,

zudem gibt es bei den Parser-Threads zumindest einen Link auf ein Tutorial zum Thema (ich finde ihn nur gerade nicht wieder :oops:)
Dort ist recht ausführlich beschrieben, wie man so etwas grundsätzlich bauen kann, u.a. auch, wie man Klammerungen, und Punkt-vor-Strich implementiert.

[alleinherrscher]

Du solltest das ganze rekursiv angehen.

Beispiel

4 * (2 + 3*(5-2))

In der Auswertungsroutine suchst du zunächst nach der innersten Klammer also (5-2) und rufst die Auswertungsroutine mit 5-2 auf. Das muss ist dann in diesem Beispiel ein elementarer rechenschritt, den du halt programmieren musst. Wenn er das ergebnis hat, setzt er dass in den String ein, also

4 * (2+ 3*3) und sucht wieder die innerste Klammer, nun: 2+ 3*3

Da hier keine Klammer mehr enthalten ist, gilt punktrechnung vor strichrechnung, deine Routine muss sich also mit 3*3 selber aufrufen, ergebnis ausgeben und in den Substring einsetzen:

2 + 9

es folgt wieder ein elementarer Rechenschritt, der als ergebnis 11 halt, das setzt du wieder in deinen string ein:

4 * 11

usw...


so würde ich das angehen...

[Newbie44]

nochmal eine frage dazu. kann es sein das man das so ähnlich wie bei binären bäumen macht? ist irgendwie so ähnlich aufgebaut, wenn ich mir z. B. dieses beispiel ansehe, http://wwwicg.informatik.uni-rostock...aereBaeume.pdf

dann ist es doch sehr verwandt damit.

das heißt also, ich muss immer von innen nach außen arbeiten, und das ganze am besten mit rekursion.

ok schon mal danke

[alleinherrscher]

Jo, das kannste mit diesen Binärbäumen machen. Unser Prof hat uns das damals auch so erklärt wie in dem Script, fand ich damals alles sehr theoretisch, aber die werden schon recht haben, dafür werden sie schließlich bezahlt ;)

[Khabarakh]

Zitat:

Zitat von Newbie44

nochmal eine frage dazu. kann es sein das man das so ähnlich wie bei binären bäumen macht?

Mit binären Bäumen nicht direkt, aber Bäume generell kommen oft vor, ja. Das Beispiel in dem PDF mit dem Term wäre z.B. ein sogenannter Parse-Baum.
Die bisher vorgeschlagenen Methoden sollten für deine Zwecke ausreichen. Ich könnte dir noch einen sehr effizienten Parser zeigen (einen sog. prädiktiven Parser, der den String nur ein einziges Mal durchlaufen muss. Ich hoffe jedenfalls mal, dass er gegen Daxens Beispiel gewinnen würde, wetten würde ich darauf nicht :mrgreen:), aber der Code wäre nicht wirklich durchschaubar, denn er wird eigentlich einfach aus einem Schema (BNF) generiert.

[BrightAngel]

Hey! Guten Abend!
@Khabarakh: Und wie willst du mit einem Durchlauf den Term berechnen?? Du weist doch am Anfang noch nicht, was hinten für Rechenoperatoren auf dich zukommen... :shock:
Ich hab mir mal ne kleine recht effiziente Function geschrieben, die es auch rekursiv macht.
(ich habe immer einen teilterm übergeben und den zerlegt)
Aber die musste den term mehrfach durchlaufen...

[Khabarakh]

Zitat:

Zitat von BrightAngel

@Khabarakh: Und wie willst du mit einem Durchlauf den Term berechnen?? Du weist doch am Anfang noch nicht, was hinten für Rechenoperatoren auf dich zukommen... :shock:

Du hast es erfasst, einen kleinen Haken muss es geben ;) : man benötigt einen Stack für die Zwischenergebnisse (der Term wird quasi in UPN übersetzt und On-The-Fly ausgewertet). Sollte aber kein großer Dämpfer sein, mit rekursiven Methoden setzt man ja sowieso schon auf einen Stack auf. Wenn ich keinen gravierenden Denkfehler habe (was in Anbetracht der Tatsache, dass ich einen solchen Parser noch nie wirklich gecodet habe, durchaus im Bereich des Möglichen liegt :mrgreen: ), sollte sich der Parser abgesehen vom zweiten Stack wirklich mit einem Durchlauf (in dem er jeweils das derzeitige und nächste Zeichen (Lookahead-Symbol) auswerten können muss) zufrieden geben.

[Nils_13]

Ich habe mir den Thread nicht wirklich durchgelesen, aber die Wörter Binärsuche und Stapel sind mir aufgefallen. Es ist im Endeffekt egal, welche Variante du nimmst. Du kannst auch Tokens nehmen, wenn du willst, kommt trotzdem aufs gleiche raus. Richtig ätzende Sachen sparst du dir zum Glück, denn Klammern machen es, wenn alles rechenbar sein soll, echt schwierig. Je nachdem, wie faul du bist, hast du das in ein paar Tagen/Wochen/Monaten :mrgreen:/Stunden erledigt. Die Theorie ist simpel: Rekursion bis zum umfallen.

[sirius]

Zitat:

Zitat von Nils_13

denn Klammern machen es, wenn alles rechenbar sein soll, echt schwierig.

:gruebel: An welcher Stelle genau?

[BrightAngel]

also, falls es irgendjemand interessiert, wie ich es gelöst habe (ich bin da ja auch net soooo der Meister :-D - also bzgl. optimierungsvorschlägen: immer her damit.), der kann mir ja ne PM schicken...