Aufgabe «Transformation des Ausdrucksbaums mit enum und Pattern Matching»

Gegeben ist ein arithmetischer Ausdruck, der als binärer Baum dargestellt wird. Jeder Knoten des Baums ist entweder eine Zahl (Blatt) oder eine Operation (Addition, Subtraktion, Multiplikation, Division) mit zwei Kindern. Es muss eine Funktion implementiert werden, die einen solchen Baum entgegennimmt und einen neuen Baum zurückgibt, der nach folgenden Regeln vereinfacht ist: Wenn ein Knoten eine Operation ist und beide Kinder Zahlen sind, berechne das Ergebnis und ersetze den Knoten durch eine Zahl; wenn eines der Kinder die Zahl 0 ist und die Operation Multiplikation ist, ersetze den Knoten durch 0; wenn eines der Kinder die Zahl 0 ist und die Operation Addition ist, ersetze den Knoten durch das andere Kind; wenn die Operation Division ist und der Divisor die Zahl 1 ist, ersetze den Knoten durch den Dividenden; wenn die Operation Subtraktion ist und beide Kinder gleich sind, ersetze den Knoten durch die Zahl 0. Wende dies rekursiv an, solange möglich. Es wird garantiert, dass alle Operationen ganzzahlig sind, die Division ist ganzzahlig mit Abrundung. Eingabedaten: Zuerst die Zahl n – Anzahl der Knoten. Dann n Zeilen, jede im Format: Knotentyp ("num" oder "op"), für "num" – Wert (ganze Zahl), für "op" – Operationssymbol ('+', '-', '*', '/') und zwei ganze Zahlen – Indizes des linken und rechten Kindes (0-basiert). Die Wurzel hat immer den Index 0. Ausgabe: Für jeden Knoten nach der Vereinfachung seinen Typ und Wert/Operation im gleichen Format ausgeben (Reihenfolge der Knoten wie im ursprünglichen Baum, auch wenn der Knoten zu einer Zahl geworden ist, seinen Index beibehalten). Wenn der Knoten zu einer Zahl geworden ist, "num Wert" ausgeben; wenn er eine Operation geblieben ist, "op Symbol linker_Index rechter_Index" ausgeben (Indizes der Kinder aus dem vereinfachten Baum).

Beispiel 1

Beispiel 2

Beispiel 3

Beispiel 4