Evaluar el árbol
Calcule el resultado
Evaluar el árbol es una lección gratuita de C Academy en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de C Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de C Academy incluye 4 lecciones en total.
Recorrido del AST
La evaluación es un recorrido en postorden: primero se calculan los hijos y después se combinan mediante el operador del nodo. Una hoja numérica simplemente devuelve su valor.
Este intérprete que recorre el árbol es el backend más sencillo que puede tener un intérprete.
La firma de eval
Nuestro evaluador recibe un puntero a un nodo y devuelve un entero. Como el árbol es recursivo, la función también lo es.
En lenguajes de coma flotante devolvería un double o un valor etiquetado.
int eval(Node *n); /* returns the integer value of the subtree */Evaluación de una hoja
El caso base detiene la recursión. Cuando un nodo es un número, su valor es la respuesta para ese subárbol.
Todo descenso recursivo debe alcanzar un caso base; de lo contrario, nunca terminaría.
int eval(Node *n) {
if (n->kind == N_NUM) {
return n->value;
}
/* ... handle N_BINOP below ... */
return 0;
}Evaluación de un BinOp
Para un nodo operador, descendemos recursivamente por ambos hijos y después aplicamos el operador. Evaluar primero el izquierdo y luego el derecho proporciona el orden habitual de izquierda a derecha.
Un switch sobre el carácter del operador mantiene la lógica legible.
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;
}Cómo evitar la división entre cero
La división entera entre cero produce un comportamiento indefinido en C y normalmente bloquea el proceso. Un intérprete seguro comprueba primero el divisor.
Es preferible informar de un error de ejecución claro a provocar un SIGFPE descontrolado.
#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;
}Evaluación de principio a fin
Aquí se evalúa como 20 un árbol construido manualmente para (2 + 3) * 4. El mismo eval podría recorrer cualquier árbol producido por el parser.
Ejecútelo para confirmar que el recorrido en postorden calcula la respuesta correcta.
#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;
}Profundidad de la pila
Cada operador anidado añade un marco a la pila de llamadas de C. Una expresión profundamente anidada, como una con mil pares de paréntesis, puede desbordarla.
La mayoría de las expresiones reales son poco profundas, pero un intérprete robusto puede cambiar a una pila explícita para mayor seguridad.
Plegado de constantes
Como la evaluación y el análisis comparten el árbol, puede optimizarlo. Si ambos hijos de un binop son números, puede calcular el resultado una vez y reemplazar el nodo por una hoja.
Este plegado de constantes es una optimización clásica de los intérpretes.
/* 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;
}Liberación del árbol
Los nodos asignados en el heap deben liberarse. Una liberación en postorden visita los hijos antes que el padre, al igual que la evaluación.
Olvidarlo provoca una fuga de memoria con cada expresión que ejecuta el intérprete.
void free_tree(Node *n) {
if (n->kind == N_BINOP) {
free_tree(n->bin.left);
free_tree(n->bin.right);
}
free(n);
}Menos unario
Es necesario gestionar la negación, como en -5. Una opción es usar un nodo unario; otra consiste en transformar -x en 0 - x durante el análisis.
En ambos casos, la evaluación sigue siendo un recorrido recursivo sencillo.
/* desugar approach: parse_factor returns binop('-', num(0), operand) */
if (cur().kind == TOK_MINUS) {
bump();
return binop('-', num(0), parse_factor());
}¿Por qué recorrer el árbol?
Los intérpretes que recorren el árbol son fáciles de escribir y depurar, aunque sacrifican algo de velocidad. Lenguajes como las primeras versiones de Ruby usaban este modelo antes de pasar a máquinas virtuales de bytecode.
A continuación añadiremos variables para que el intérprete pueda recordar valores.
Comprobación rápida
Razonе sobre el orden en que eval visita los nodos.
Repaso
Ha implementado un evaluador recursivo: un caso base para las hojas, recursión para los binop, una protección contra la división entre cero, además de la liberación del árbol y el plegado de constantes.
Ahora el intérprete calcula cualquier AST aritmético. El siguiente paso es añadir variables.
Preguntas frecuentes
¿La lección «Evaluar el árbol» es gratis?
Sí — el texto completo de «Evaluar el árbol» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de C Academy, actualiza a CoddyKit PRO. El curso de C Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Evaluar el árbol»?
Calcule el resultado Practicas C Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar C Academy?
No se requiere experiencia previa. C Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «Evaluar el árbol»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de C Academy?
Sí. Cada lección de C Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Tokenizar la entrada
- Analizar expresiones
- Evaluar el árbol
- Añadir variables