Den Baum auswerten
Berechnen Sie das Ergebnis.
Den Baum auswerten ist eine kostenlose C Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des C Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.
Den AST durchlaufen
Die Auswertung erfolgt als Postorder-Traversierung: Zuerst werden die Kindknoten berechnet, anschließend werden sie mit dem Operator des Knotens kombiniert. Ein Zahlenblatt gibt einfach seinen Wert zurück.
Dieser Interpreter, der den Baum durchläuft, ist das einfachste Backend eines Interpreters.
Die Signatur von eval
Unser Auswerter erhält einen Zeiger auf einen Knoten und gibt eine Ganzzahl zurück. Da der Baum rekursiv ist, gilt das auch für die Funktion.
Bei Gleitkommasprachen würden Sie stattdessen ein double oder einen Wert mit Typkennung zurückgeben.
int eval(Node *n); /* returns the integer value of the subtree */Ein Blatt auswerten
Der Basisfall beendet die Rekursion. Wenn ein Knoten eine Zahl enthält, ist ihr Wert die Antwort für diesen Teilbaum.
Jeder rekursive Abstieg muss einen Basisfall erreichen, sonst würde er nie enden.
int eval(Node *n) {
if (n->kind == N_NUM) {
return n->value;
}
/* ... handle N_BINOP below ... */
return 0;
}Einen BinOp auswerten
Bei einem Operator-Knoten steigen wir rekursiv in beide Kindknoten ab und wenden anschließend den Operator an. Wenn die linke Seite vor der rechten ausgewertet wird, ergibt sich die übliche Reihenfolge von links nach rechts.
Ein switch über das Operatorzeichen hält die Logik übersichtlich.
int eval(Node *n) {
if (n->kind == N_NUM) return n->value;
int l = eval(n->bin.left);
int r = eval(n->bin.right);
switch (n->bin.op) {
case '+': return l + r;
case '-': return l - r;
case '*': return l * r;
case '/': return l / r;
}
return 0;
}Division durch null absichern
Eine Ganzzahldivision durch null führt in C zu undefiniertem Verhalten und lässt den Prozess typischerweise abstürzen. Ein sicherer Interpreter prüft den Divisor vorher.
Eine saubere Laufzeitfehlermeldung ist besser als ein unkontrolliertes SIGFPE.
#include <stdio.h>
#include <stdlib.h>
static int safe_div(int a, int b) {
if (b == 0) {
fprintf(stderr, "runtime error: division by zero\n");
exit(1);
}
return a / b;
}Auswertung von Anfang bis Ende
Hier wird ein manuell erstellter Baum für (2 + 3) * 4 ausgewertet und ergibt 20. Dasselbe eval kann jeden vom Parser erzeugten Baum auswerten.
Führen Sie das Programm aus, um zu bestätigen, dass die Postorder-Traversierung das richtige Ergebnis berechnet.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int is_num; int value;
char op; struct Node *l, *r;
} Node;
static Node *N(int v){ Node*n=calloc(1,sizeof*n); n->is_num=1; n->value=v; return n; }
static Node *B(char o,Node*a,Node*b){ Node*n=calloc(1,sizeof*n); n->op=o; n->l=a; n->r=b; return n; }
static int eval(Node *n){
if (n->is_num) return n->value;
int l = eval(n->l), r = eval(n->r);
switch (n->op){
case '+': return l + r;
case '-': return l - r;
case '*': return l * r;
case '/': return l / r;
}
return 0;
}
int main(void){
Node *ast = B('*', B('+', N(2), N(3)), N(4));
printf("%d\n", eval(ast));
return 0;
}Stacktiefe
Jeder verschachtelte Operator fügt dem C-Aufruf-Stack einen Stackframe hinzu. Ein tief verschachtelter Ausdruck mit beispielsweise tausend Klammern kann ihn zum Überlaufen bringen.
Die meisten realen Ausdrücke sind flach. Ein robuster Interpreter kann jedoch vorsichtshalber auf einen expliziten Stack umsteigen.
Konstanten falten
Da Auswertung und Parsing denselben Baum verwenden, können Sie optimieren. Wenn beide Kindknoten eines Binop Zahlen sind, können Sie das Ergebnis einmal berechnen und den Knoten durch ein Blatt ersetzen.
Dieses Constant Folding ist eine klassische Optimierung von Interpretern.
/* fold: collapse a binop of two literals into one literal */
Node *fold(Node *n) {
if (n->kind == N_BINOP) {
n->bin.left = fold(n->bin.left);
n->bin.right = fold(n->bin.right);
if (n->bin.left->kind == N_NUM &&
n->bin.right->kind == N_NUM)
return num(eval(n));
}
return n;
}Den Baum freigeben
Auf dem Heap reservierte Knoten müssen freigegeben werden. Eine Freigabe in Postorder besucht die Kindknoten vor dem Elternknoten und entspricht damit der Auswertung.
Wenn Sie das vergessen, entsteht bei jedem vom Interpreter ausgeführten Ausdruck ein Speicherleck.
void free_tree(Node *n) {
if (n->kind == N_BINOP) {
free_tree(n->bin.left);
free_tree(n->bin.right);
}
free(n);
}Unäres Minus
Negation wie bei -5 muss verarbeitet werden. Eine Möglichkeit ist ein unärer Knoten; eine andere besteht darin, -x während des Parsens in 0 - x umzuwandeln.
In beiden Fällen bleibt die Auswertung ein einfacher rekursiver Durchlauf.
/* desugar approach: parse_factor returns binop('-', num(0), operand) */
if (cur().kind == TOK_MINUS) {
bump();
return binop('-', num(0), parse_factor());
}Warum den Baum durchlaufen?
Interpreter, die den Baum durchlaufen, sind einfach zu schreiben und zu debuggen, allerdings auf Kosten etwas geringerer Geschwindigkeit. Sprachen wie das frühe Ruby verwendeten dieses Modell, bevor sie zu Bytecode-VMs wechselten.
Als Nächstes fügen wir Variablen hinzu, damit sich der Interpreter Werte merken kann.
Schnelltest
Überlegen Sie, in welcher Reihenfolge eval die Knoten besucht.
Zusammenfassung
Sie haben einen rekursiven Auswerter implementiert: einen Basisfall für Blätter, Binop-Rekursion, eine Absicherung gegen Division durch null sowie das Freigeben des Baums und Constant Folding.
Der Interpreter kann nun beliebige arithmetische ASTs berechnen. Als Nächstes kommen Variablen hinzu.
Häufig gestellte Fragen
Ist die Lektion „Den Baum auswerten“ kostenlos?
Ja — der vollständige Text von „Den Baum auswerten“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des C Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Den Baum auswerten“?
Berechnen Sie das Ergebnis. Du übst C Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um C Academy zu starten?
Keine Vorkenntnisse erforderlich. C Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Den Baum auswerten“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser C Academy-Lektion Code schreiben und ausführen?
Ja. Jede C Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Eingaben tokenisieren
- Ausdrücke parsen
- Den Baum auswerten
- Variablen hinzufügen