Bei meine Beschäftigung mittm Thema Expressionparser stieß ich auf ein paar hochinteressante Algorithmen, und auch paar listenreiche Klassen.
Zunächst mal Expression-Beispiel:
Das ist ein Ausdruck in Infix-Schreibweise, und unter Berücksichtigung der Klammer-Regeln und der Vorrang-Regeln der Operatoren, kann man das ausrechnen, kommt -15 bei raus.
Beim Rechnen geht man so vor, dass man Teil-Ausdrücke bildet, die jeweils mehrere Werte zusammenrechnen zu einem Wert. Dabei darf man nicht einfach von links nach rechts vorgehen, sondern muß die Operatoren mit höherem Vorrang vorrangig abarbeiten (deshalb heißt das auch "Operator-Vorrang" ;)).
Ums ganz schlimm zu machen, wird durch Klammerung auch noch in die Vorränge eingegriffen, also dafür einen gscheiten Algorithmus zu erfinden ist Aufgabe für Genies.
Nun gabs mal ein Genie in Polen, der hat eine klammerfreie Notation erfunden, also eine Schreibweise, wie man obigen Ausdruck auch ohne Klammern und Vorränge eindeutig formulieren kann. Als noch praktischer erwies sich, wenn man die Operatoren hinter die Operanden schreibt, und so sieht dann die "umgekehrt-polnische Notation" obiger Expression aus, alias "Postfix-Notation":Sieht völlig krank aus, aber Computer finden das klasse, denn in dieser Notation können sie den Ausdruck ganz einfach von links nach rechts abarbeiten, und kommt auch -15 bei raus.
Also von links nach rechts: Wenns eine Zahl ist, dann legt man sie auf einen Zahlen-Stack. Wenns ein Operator ist, dann nimmt dieser sich seine Operanden von genau diesem Stack runter, berechnet damit einen Wert, und legt den wieder drauf:
Nicht wahr: bei einer Zahl nimmt der Stack um eins zu, bei einem binären Operator um eins ab, denn 2 Zahlen werden runtergenommen, und eine neue wieder drauf.
Das ist nur bei binären Operatoren so, bei unären bleibt der Stack gleich, weil eine runter und eine drauf.
Unärer Operator?? Naja, zB. die Negation, also das Minus-Zeichen vor einer Zahl:Dassis postfix-mäßig schlecht mit dem Minus-Zeichen, weils dann nicht mehr eindeutig ist. Also auf "Postfix" notiere ich die Negation mit '!'.
Gesehen? In Zeile#7 bleibt die Höhe des Stacks konstant, nur der letzte Wert wurde ausgetauscht durch seine Negation.

Aber ich spinne noch weiter, denn wenns binäre und unäre Operatoren gibt, gibts dann auch nulläre? Also Operatoren, die gar keine Operanden brauchen, um einen Wert zu bilden?
Klar gibts das - Zahlen zum Beispiel! Und wie man sieht: Zahlen verhalten sich genau nach Postfix-Rechenregel als nulläre Operatoren: Sie nehmen keinen Wert runter, und legen einen Wert drauf.
Zahlen - genauer gesagt - Konstanten sind also nulläre Operatoren.
Unds gibt noch mehr nulläre Operatoren, nämlich die Variablen - kommen wir noch zu.

Zunächst aber der "Shunting-yard-Algorithmus" zur Konvertierung von Infix- in Postfix-Notation:
Zu deutsch "Rangierbahnhof"-Algo, weils einen Operator-Stack gibt, in den jeder Operator erst mal (vorwärts) hineinfährt, und nach gewissen Regeln fährt er dann (rückwärts) wieder raus in die Ausgabe.
Die operatorStack-Regel lautet: Bevor ein neuer Operator auf den Stack darf, werden alle Operatoren höheren oder gleichen Ranges vom Stack in die Ausgabe geflusht. Also rangniedere Operatoren verdrängen rang-gleiche und -höhere vom Stack in die Ausgabe. Somit ist der Stack auch sortiert: der höchste obenauf.
Kleine Zwischenfrage: Nulläre Operatoren - welchen Rang haben die? Antwort: 99, also maximal. Dadurch verdrängt eine Zahl nur eine andere Zahl, aber keinen der anderen Operatoren.
Und Klammern, was ist mit denen? Die kriegen Rang 0, und Sonderbehandlung. Rang 0 bewirkt, dass die öffnende Klammer von anneren Operatoren überhaupt nicht verdrängt werden kann.
Die Sonderbehandlung besteht darin, dass trotz niedrigsten Ranges die öffnende Klammer auch ihrerseits keinen Operator vom Stack drängt.
Schließende Klammer flusht dann den Stack in die Ausgabe, bis hin zur öffnende Klammer. Beide Klammern verfallen, also die öffnende wird runtergepoppt, und die schließende wird garnicht erst draufgelegt.
Beachte, wenn mehrere Operatoren verdrängt werden (Zeilen #9, #15, #17), dass sie in umgekehrter Reihenfolge zur Ausgabe kommen.
So sind Stapel nunmal: Was man als letztes drauflegt, bekommt man als erstes wieder runter.

Zunächstmal der "Shunting-yard-Algo" für Infix->Postfix:Man erkennt vlt, dassich eine Klasse Token erfunden habe, die ihren eigenen Rang kennt (Token.IsHigherThan(otherToken)), und die einen Operator-Code hat (OpCode), um anzugeben, was eiglich gerechnet werden soll.
OpCode kann noch mehr darstellen als die im Code ersichtlichen (), nämlich die Operatoren +-*/^! (wer hätte das gedacht?). Diese werden alle im Case Else verarbeitet.

So, jetzt Ausrechnen einer Liste postfix-notierten Token:Tja - zuächst mal ist da von Token garkeine Rede, sondern das komische da von #4 - #14 ist ein Einzeiler, der ein Dictionary(Of Char, Action(Of Stack(Of Double), Token)) initialisiert, also ein Dictionary, wo man für einen Char-Key eine Methode bekommt, die mit einem Token was greuliches auf einem Double-Stack anrichtet.
Was diese Action(Of Stack, Token) jeweils anrichtet, ist hofflich zu erkennen, etwa bei OpCode "0"c (nullärer Konstanten-Operator) wird kein Wert vom Stack genommen, und ein Wert gepusht, nämlich die im Token gespeicherte Nummer.
OpCode "!"c (unäre Negation) nimmt einen Wert runter, und tut dessen Negation wieder drauf.
OpCode "^"c (binärer Potenz-Operator) nimmt 2 Werte: den ersten zwischenspeichert er als right, denn bei Potenzierung muß auf richtige Reihenfolge der Operatoren geachtet werden.
Die restlichen OpCodes sind ebenfalls binär, wobei "/"c und "-"c auch ohne Zwischenspeicherung richtig rechnen trotz falscher Reihenfolge.
Jo, bei so gründlicher Vorbereitung fällt die eigentliche Schleife natürlich absolut minimalistisch aus:Jedes Token weiß wasses zu tun hat, und tut es auch.

Neben der Postfix-Notation gibts eine weitere klammerfreie Darstellung für Expressions - den Expression-Tree:

Dassis sogar viel intuitiver als die Postfix-Notation, man erkennt doch gleich, dass obiger Ausdruck aus 2 Teilausdrücken besteht, wovon der erste 2 Zahlen addiert, während der zweite Teilausdruck von einer Division (3. Teilausdruck) eine Zahl subtrahiert.
Also wenn man eine schachtelbare Operator-Klasse hätte - das würde beim Ausrechnen selbst den Postfix-Algo alt aussehen lassen.
Einem Root-Expression-Node weist du einfach an: "Ausrechnen!", und in einer lichtschnellen Kettenreaktion pflanzt sich diese Anweisung durch den Baum fort und das Ergebnis ist da.
Da wird nichtmal eine Schleife benötigt, sondern die Addition rechnet einfach Operand1 + Operator2, die Subtraktion rechnet Operand1 - Operator2, und nicht anders machens Division und Multiplikation.
Und dabei ists egal, ob die Operanden selbst wieder zusammengesetzt sind oder atomar - eine Variable oder eine Konstante ist ein Ausdruck wie jeder andere, nur atomar.

Aber wie baut man son Bäumle auf?
Naja, den Algo zeige ich vlt. am besten mit TreeNodes, die sind ja dazu da, um Baum-Strukturen zu bilden:Prinzipiell dasselbe wie Postfix ausrechnen, nur statt eines Stack(Of Double) hat man einen Stack(Of TreeNode):
Ein Operator nimmt mehrere Operanden vom Stack runter, und tut sein Ergebnis wieder drauf. Nur bei Treenodes ist das Ergebnis kein Double, sondern halt ein neuer Treenode, in den die vom Stack genommenen "Operanden"-Nodes eingehängt sind.
Auch kann ich hier kein so listiges Dictionary vorbereiten, sondern führe eine traditionelle Fallunterscheidung durch. Dieses, weil ich nun auch Parameter unterstütze - da mag ich nicht für jeden denkbaren ParameterNamen einen Dictionary-Eintrag anlegen.

Gut, das ist jetzt ein Treeview, und ein Treeview sieht auch gut aus - aber rechnen kannernich
Also weiterhin schachtelbare Expression-Klasse gesucht - ach guggemal System.Linq.Expressions - du lieber Himmel - da fährt vlt. mal abgedrehtes Zeugs herum!

Binary-, Block-, CatchBlock-, Constant-, Goto-, Index-, Loop-, Parameter- ... - da ist ja eine vollständige Programmiersprache abgebildet, nicht nur son bischen Arithmetik wie bei mir!
Na, entsprechend wüst ist das Zeugs auch zu benutzen.
Ich zeige erstmal nur, wie ich die Signatur designed habe:Also man gibt einen String hinein und bekommt fixnfertig eine Func(Of Double, Double, Double, Double, Double) zurück, also eine Function, die aus 4 Double-Argumenten ein Double-Ergebnis berechnet.
Aufrufbeispiel:
Da der übergebene String "( a + b ) * ( c + a - 2 )" hier nur 3 Parameter verwendet, ist zum Ausrechnen das vierte Argument beliebig - nur weglassen kannmans nicht.
Wolle gugge TestApp?


Ein weiteres ist noch vorrauszuschicken, nämlich Expressions werden nicht mit Schlüsselwort New gebildet, sondern die Expression-Klasse bietet haufenweise statische Generator-Funktionen an für Operatoren (und für endlos annere Sachen).
Also eine Potenzierung bekommt man durch Aufruf von Expression.Power(xp1 As Expression, xp2 As Expression)
eine Division durch Expression.Divide(xp1 As Expression, xp2 As Expression)
eine Multiplikation durch Expression.Multiply(xp1 As Expression, xp2 As Expression)
eine Negation durch Expression.Negate(xp1 As Expression) (unärer Operator)
eine Konstante durch Expression.Constant(value, Typ) (nullär - verlangt kein Expression-Argument)
usw.

So, jetzt aber CreateExpressionTree() komplett:Prinzipiell dasselbe wie mitte Treenodes, nur statt Stack(Of Treenode) isses jetzt ein Stack(Of Expression), der nach Postfix-Rechenregel "ausgerechnet" wird.
Ich kann hier auch wieder eine Dictionary-Vorbereitung treffen, sodass ich im Select in der Schleife alle binären Operatoren über einen Kamm scheren kann.

Es gibt sogar ein zweites Dictionary, nämlich noch eines für die Parameter-Expressions:Ich konvertiere alle Zeichen von "abcd" je in eine ParameterExpression dieses Namens. Daraus bau ich gleich ein Dictionary, welches als Key den Parameter-Namen verwendet.
So, dann also die Schleife abfahren, und am Schluss bleibt eine Expression auffm Stack liegen, und da sind alle Sub-Expressions drin eingeschachtelt.
Hieraus (#25) wird eine (kompilierbare) Lambda-Expression generiert, wobei ich die ParameterExpressions nochmal der Reihe nach angeben muß, damit der Lambda die richtige Argument-Reihenfolge generiert.
Das noch .Compilen, und raus kommt der richtige Methoden-Rückgabewert vom Typ Func(Of Double, Double, Double, Double, Double), also eine anonyme Function, die auch tatsächlich so schnell rechnet, wie anonyme Methoden in .Net halt sind.