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.