Sonntag, 2. Oktober 2011

Ein Algorithmus zum Aufzählen von Ausdrucksbäumen

Damit über das Ergebnis eines ohne Klammern hingeschriebenen Terms wie
24 - 3 * 5 - 4
keine Diskussionen entstehen, gibt es bekanntlich einige Vorrangregeln: Die Punktrechnung wird der Strichrechnung vorgezogen, und der Ausdruck wird von links nach rechts ausgerechnet. Wenn man sich an diese Konventionen hält,ergibt obiger Ausdruck den Wert 5. Wenn man es anders wünscht, muss man Klammern setzen. Zum Beispiel liefert der folgende Ausdruck
( 24 - 3 ) * ( 5 - 4 )
ein anderes Ergebnis, obwohl die Zahlen und Rechenoperationen immer noch in der gleichen Reihenfolge dastehen. Durch die hinzugefügten Klammern wurde die entscheidende Information hinzugefügt, dass die in den Klammern stehenden Ausdrücke zuerst gerechnet werden sollen.

Eine gegebene Folge von Zahlen und Rechenoperationen vorausgesetzt: Wie viele unterschiedliche Ausführungsreihenfolgen gibt es denn insgesamt für die Ausrechnung? Das heisst: Auf wie viele verschiedene Weisen kann man klammern?

Um an ein solches Problem heranzugehen, muss man es zuerst auf geeignete Art modellieren. Unsere übliche Notation mit Klammern und Vorrangsregeln ist für eine theoretische Betrachtung eher ungeeignet. Es empfiehlt sich eine Stippvisite bei den Informatikern. Diese bevorzugen für Terme wie den obigen eine Baumdarstellung. Jede Rechenoperation wird durch einen Knoten mit zwei Kindknoten repräsentiert. Diese können selbst wieder Kinder haben - wenn sie wiederum eine Rechenoperation sind - oder nicht: wenn es Zahlen sind. Die Zahlen sind also die terminalen Knoten des Ausdrucksbaums, die auch Blätter genannt werden. Die Rechnung 1 + 1 wird dann durch folgendes Diagramm repräsentiert:



Der Ausdruck 24 - 3 * 5 - 4, der mir hier als Aufhänger diente, sieht mit der Brille des Informatikers so aus:



Der Ausdruck (24 - 3) * (5 - 4) behält die Reihenfolge der Zahlen und Operationen bei, klammert sie aber anders. Das ergibt den folgenden Baum:



Bei Wahl dieses Modells lässt sich die Aufgabe, alle möglichen Klammerungen eines Ausdrucks aufzuzählen, leichter behandeln. Für einen Ausdruck mit n Operationen und - daraus folgend - mit n+1 Zahlen haben wir also alle "Ausdrucksbäume" mit insgesamt 2n+1 Knoten zu bilden, wobei genau n+1 Knoten Blätter sind. Die n inneren Knoten, die den Operationen entsprechen, also zwei Kindknoten haben, wollen wir Operationsknoten nennen.

Bei der Suche nach einem rekursiven Algorithmus, um alle Ausdrucksbäume aufzuzählen, verrannte ich mich zuerst in dem Bestreben, den Algorithmus gewissermassen "von oben" beginnen zu lassen, beim Wurzelknoten. Ich habe den Verdacht, dass dies überhaupt nicht oder nur unter grossen Qualen möglich ist.

Der Trick bei dieser Aufgabe ist, dass man besser "von unten" anfängt: Mit einer Operation wie 1+1, also einem Knoten, der zwei Blätter als Kinder enthält und damit eine Art "Ende" des Graphen darstellt. Wenn man den Algorithmus bei einem solchen Knoten beginnen lässt, wird alles ganz einfach: Von dort aus kann man die möglichen Ausdrücke wie folgt aufbauen:

  • Auf jeder Stufe des Algorithmus wollen wir einen neuen Operationsknoten mit Kindknoten besetzen. Als Kindknoten können wir uns aus einem Vorrat von "freien", d.h. schon auf einer früheren Stufe mit Kindknoten besetzten, aber noch nicht in den Ausdruck eingebauten Operationsknoten bedienen.
  • Dieser Vorrat, der auch leer sein kann, darf auf jeder Stufe höchstens gleich der Anzahl der noch verfügbaren, d.h. noch gar nicht eingebauten Operationsknoten sein. Sonst liessen sich nicht mehr alle freien Operationsknoten in den Baum einbauen.
  • Um einen Operationsknoten mit Kindknoten zu besetzen, können wir keinen, einen oder zwei freie Operationsknoten zu Kindern erklären. Die offene oder offenen Stellen des Operationsknotens besetzen wir mit Blättern. Bei der Alternative, einen Operationsknoten zu besetzen, sind auch noch die beiden Fälle zu unterscheiden, dass man das linke oder rechte Kind mit dem Operationsknoten belegt.


Der Algorithmus terminiert beim Wurzelknoten: Aufgrund der Restriktion an die Zahl der freien Operationsknoten liegen beim Wurzelknoten höchstens zwei freie Operationsknoten vor, die man auf jeden Fall in einer letzten Operation "verdrahten" kann.

Zur Verdeutlichung will ich den Algorithmus am Fall n=3 einmal durchspielen. Das folgende Schema zeigt die möglichen Klamemerausdrücke am Beispiel eines Ausdrucks mit drei Operationen O0 (der Wurzeloperation), O1, O2 und vier Zahlen:



Jedes Doppelkästchen steht für die beiden Kindknoten der Operation. Ein graues Kästchen steht für die Belegung mit einem Operationsknoten, ein weisses Kästchen für die Belegung mit einem Blatt. Jede Zeile steht für eine mögliche Klammerung.

Man beginnt ganz rechts, also mit der Ausprägung von O2. Da es am Anfang noch keine freien Operationsknoten gibt, muss O2 in jedem möglichen Fall mit zwei Blättern belegt werden. Nun ist ein freier Operationsknoten entstanden.

Erst beim nächsten Operationsknoten O1 ergeben sich nun Wahlmöglichkeiten: Entweder belegt man auch diesen Knoten mit zwei Blättern – das ergibt die erste Möglichkeit – oder man belegt einen der beiden Kindknoten von O2 mit O1. Das ergibt jeweils zwei weitere Fälle.

Schliesslich sind wir auf der dritten und letzten Ebene: Der Wurzelknoten O0 ist zu belegen. In der ersten dargestellten Zeile haben wir nun zwei freie Operationsknoten. Diese müssen nun mit dem Wurzelknoten verdrahtet werden. Die Reihenfolge spielt, wenn zwei Operationsknoten verdrahtet werden, keine Rolle – wie in diesem Fall. Wenn aber nur ein Operationsknoten zugeordnet und die andere Stelle mit einem Blatt besetzt wird, spielt die Reihenfolge durchaus eine Rolle.

So ergeben sich insgesamt fünf Möglichkeiten, einen Ausdruck mit vier Zahlen und drei Operationen zu klammern. Aus dem Algorithmus ergibt sich, dass es für das Resultat auf die zahlenmässige Zuordnung (also die Subskripte 0,1,2 der Operationsknoten) nicht ankommt. Eine Möglichkeit lässt sich zahlenmässig durch eine "Signatur" beschreiben: Ein Tupel (an-1, an-2, …, a0) von Zahlen zwischen 0 und 2, wobei in den Fällen ai=1 noch zu notieren ist, ob das linke (L) oder rechte (R) Kindelement für den Operationsknoten verwendet wurde. Die im Beispiel resultierenden Signaturen habe ich oben angefügt.

Diese Zuordnung ergibt einen Zusammenhang zwischen der Anzahl binärer Ausdrucksbäume und den sogenannten Kombinationen, also verschiedenen möglichen Auswahlen einer Teilmenge aus einer grösseren Menge — hier den Auswahlen von n-1 aus 2n Elementen. Von hier gelangt man zu den wohlbekannten Catalanschen Zahlen. Da die Diskussion die Grösse eines Blogs sprengt, habe ich diesen Zusammenhang in einem kleinen Artikel erläutert:

http://ruediger-plantiko.net/etree.pdf

Ein vollständiges C-Programm, das die Ausdrucksbäume gemäss diesem Algorithmus aufzählt, habe ich auf Pastebin unter der URL http://pastebin.com/mehTM4Z0 verfügbar gemacht.

Das Programm erzeugt z.B. für n=4 die folgende Aufzählung der 14 möglichen Klammerungen eines Ausdrucks mit vier Operationen:

[op,[op,[op,num,num],num],[op,num,num]]
[op,[op,num,[op,num,num]],[op,num,num]]
[op,[op,[op,num,num],[op,num,num]],num]
[op,num,[op,[op,num,num],[op,num,num]]]
[op,[op,num,num],[op,[op,num,num],num]]
[op,[op,[op,[op,num,num],num],num],num]
[op,num,[op,[op,[op,num,num],num],num]]
[op,[op,num,[op,[op,num,num],num]],num]
[op,num,[op,num,[op,[op,num,num],num]]]
[op,[op,num,num],[op,num,[op,num,num]]]
[op,[op,[op,num,[op,num,num]],num],num]
[op,num,[op,[op,num,[op,num,num]],num]]
[op,[op,num,[op,num,[op,num,num]]],num]
[op,num,[op,num,[op,num,[op,num,num]]]]

Keine Kommentare :