Parser in c++ schreiben

[gizno82]

Hallo Leute,

Ich habe vor ein Konsolenprogramm zu schreiben mit dem man Widerstandsnetzwerke berechnen kann.
Das ganze soll so von statten gehen, dass man beispielsweise eingibt 500k - 300 || 1m
das - bedeutet in reihe geschaltet und || bedeutet parallel geschaltet. Sprich ein 500 k Ohm Widerstand ist in Reihe mit einem 300 Ohm Widerstand geschalten, die Summe aus diesen beiden Widerständen wird parallel zu einem 1 m Ohm Widerstand geschaltet.

Wie kann man realisieren, dass die Software in der Lage ist zu sagen okay hier ist ein - also muss der Wert links bzw. Rechts von dem Strich nach als Reihenschaltung betrachtet werden und sobald aber ein || auftaucht handelt es sich um eine Parallelschaltung.

Mir geht es hier nicht um Code Stringszerpflücken bekomme ich hin
Was mich interessiert ist die Theorie die dahinter steckt. Ich könnte das ganze mit tausenden if s machen.
Das ist aber unschön.
Mir schwebt da was von Backus Naur Form vor oder Binären Bäumen.
Bin ich da auf dem richtigen Weg ?
Könnte mir bitte jemand einen Denkanstoß geben.

Grüße Gizno

[cloidnerux]

Könnte mir bitte jemand einen Denkanstoß geben.

Im Grunde ist das eine Methodische Teile-und-herrsche Geschichte.
Du musst irgendwo anfangen den String auf ein Trennelement hin zu Untersuchen und eben den Ausdruck links und rechts davon als Objekt ansehen und erneut Parsen, also im Grunde sowas:

Code: Alles auswählen

Number Calculate(zahl a, char seperator, zahl b)
{
    //do whatever you want to do
}

Number Parse(string input)
{
    if(input.Contains(trenner))
    {
        return Calculate(Parse(input.part1), input.seperator, Parse(input.part2));
    }
    return Convert.ToNumber(input);
}

Damit zerlegst du halt so lange deinen String bis du die einzelnen Teile berechnen kannst.

MfG cloidnerux.

[Xin]

Wie kann man realisieren, dass die Software in der Lage ist zu sagen okay hier ist ein - also muss der Wert links bzw. Rechts von dem Strich nach als Reihenschaltung betrachtet werden und sobald aber ein || auftaucht handelt es sich um eine Parallelschaltung.

Mir geht es hier nicht um Code Stringszerpflücken bekomme ich hin

Warum willst Du Strings zerpflücken?

Was mich interessiert ist die Theorie die dahinter steckt. Ich könnte das ganze mit tausenden if s machen.
Das ist aber unschön.
Mir schwebt da was von Backus Naur Form vor oder Binären Bäumen.
Bin ich da auf dem richtigen Weg ?

Bei der BNF ja. Und bei den Binären Bäumen auch. Und - nicht oder. ^^

Könnte mir bitte jemand einen Denkanstoß geben.

Du wirst nicht nur seriell und parallel brauchen, sondern auch priorisierte Betrachtung.

( 500k - 300 ) || 1m != 500k - ( 300 || 1m )

Du hast also drei Operatoren: (), - und || und mindestens zwei Prioritäten: () steht über - und ||

Mit Yacc und Bison kannst Du Dir daraus einen Parser basteln lassen. Ich wusst' auch mal wie, aber ich baue Compiler und bin kein Jäger.

Wir bauen also einen binären Baum auf. Jeder Knoten hat einen Operator und jeder Operator eine Priorität. Jedes Blatt ist ein Wert.
Du fängst also an zu lesen: 500k => Wert, also ein Blatt anlegen.

"-": Operator: Knoten anlegen, vorher war ein Blatt. das Blatt gehört nach links.
300, Wert: Rechtes Blatt.
||: Operator, Knoten anlegen: Wenn die Bindungsstärke höher als der Vorgängeroperator ist (* bindet stärker als +), dann fügst Du den Operator einfach übergeordneten Knoten rechts an und nimmst das ehemalige rechte Kind als eigenes linkes Kind. Ist er niedriger, so nimmst Du den kompletten Operator als linkes Kind. Diese Überprüfung machst Du für alle Elternknoten bis Du einen schwächer bindenden Operator findest.
1m: Wert: Rechtes Kind des aktuellen Operators.

Falls Du ein Compilerbau-Buch findest, dass diesen Algorithmus zeigt, sag mir bitte Bescheid. ^^
Strings zu zerpflücken war mir zu blöd. Statt Strings zu zerpflücken liest Du ihn so nämlich einfach von links nach rechts ein und fertig.

[gizno82]

okay der Syntaxbaum ist nun mit Daten also Werten und dem Operatoren "Befüllt", was nun wie macht man jetzt weiter ?

[Xin]

okay der Syntaxbaum ist nun mit Daten also Werten und dem Operatoren "Befüllt", was nun wie macht man jetzt weiter ?

Was möchtest du denn damit machen? ^^

Wenn Du zum Beispiel ausrechnen möchtest, wie der Gesamtwiderstand ist, fügst Du jedem Knotentyp mal die Funktion GetValue() hinzu. Bei Widerständen gibst Du den Wert zurück. Bei seriellen Schaltungen addierst Du den Wert des linken und rechten Knotens, bei parallelen den Kehrwert. (wenn ich mich recht entsinne ^^).

Eine Funktion "DrawPlan()" wäre aufwendiger. ^^