10 - Ejemplo práctico: evaluador de expresiones
Aplicamos los árboles binarios para modelar expresiones aritméticas con sumas y restas. Cada nodo interno almacena un operador (+ o -) y cada hoja contiene un operando entero. Al recorrer el árbol evaluamos la expresión completa respetando la precedencia implícita de la estructura.
10.1 Enunciado
Representar y evaluar la expresión:
((12 + (8 - 3)) - (5 + 4))
El resultado esperado es 8. Debemos construir manualmente el árbol, imprimir la expresión en notación infija y calcular su valor.
10.2 Modelo de nodo
Usamos un struct que diferencia entre operadores y operandos mediante el campo es_operador.
typedef struct TreeNode {
int es_operador;
char operador;
int valor;
struct TreeNode *izquierdo;
struct TreeNode *derecho;
} TreeNode;10.3 Creación de nodos
Definimos dos helpers: uno para operandos y otro para operadores.
TreeNode *crearOperando(int valor) {
TreeNode *n = malloc(sizeof(TreeNode));
if (!n) return NULL;
n->es_operador = 0;
n->operador = 0;
n->valor = valor;
n->izquierdo = NULL;
n->derecho = NULL;
return n;
}
TreeNode *crearOperador(char operador, TreeNode *izq, TreeNode *der) {
TreeNode *n = malloc(sizeof(TreeNode));
if (!n) return NULL;
n->es_operador = 1;
n->operador = operador;
n->valor = 0;
n->izquierdo = izq;
n->derecho = der;
return n;
}10.4 Evaluación recursiva
Para evaluar la expresión recorremos el árbol y combinamos los resultados de cada subárbol según el operador.
int evaluar(TreeNode *nodo) {
if (!nodo) return 0;
if (!nodo->es_operador) {
return nodo->valor;
}
int izq = evaluar(nodo->izquierdo);
int der = evaluar(nodo->derecho);
if (nodo->operador == '+') {
return izq + der;
}
return izq - der;
}10.5 Impresión infija
Para visualizar la expresión usamos un recorrido en orden y agregamos paréntesis.
void imprimirInfijo(TreeNode *nodo) {
if (!nodo) return;
if (nodo->es_operador) printf("(");
imprimirInfijo(nodo->izquierdo);
if (nodo->es_operador) {
printf(" %c ", nodo->operador);
} else {
printf("%d", nodo->valor);
}
imprimirInfijo(nodo->derecho);
if (nodo->es_operador) printf(")");
}10.6 Verificación
Para confirmar el resultado:
- Impresión infija debe mostrar
((12 + (8 - 3)) - (5 + 4)). evaluar(raiz)debe retornar 8.- Si cambiamos un operando (por ejemplo 5 por 7), el resultado final se ajusta automáticamente.
10.7 Código completo listo para CLion
El siguiente archivo implementa la expresión propuesta y permite reutilizar la estructura para cualquier combinación de sumas y restas.
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int es_operador;
char operador;
int valor;
struct TreeNode *izquierdo;
struct TreeNode *derecho;
} TreeNode;
TreeNode *crearOperando(int valor) {
TreeNode *n = malloc(sizeof(TreeNode));
if (!n) return NULL;
n->es_operador = 0;
n->operador = 0;
n->valor = valor;
n->izquierdo = NULL;
n->derecho = NULL;
return n;
}
TreeNode *crearOperador(char operador, TreeNode *izq, TreeNode *der) {
TreeNode *n = malloc(sizeof(TreeNode));
if (!n) return NULL;
n->es_operador = 1;
n->operador = operador;
n->valor = 0;
n->izquierdo = izq;
n->derecho = der;
return n;
}
int evaluar(TreeNode *nodo) {
if (!nodo) return 0;
if (!nodo->es_operador) return nodo->valor;
int izq = evaluar(nodo->izquierdo);
int der = evaluar(nodo->derecho);
return (nodo->operador == '+') ? (izq + der) : (izq - der);
}
void imprimirInfijo(TreeNode *nodo) {
if (!nodo) return;
if (nodo->es_operador) printf("(");
imprimirInfijo(nodo->izquierdo);
if (nodo->es_operador) printf(" %c ", nodo->operador);
else printf("%d", nodo->valor);
imprimirInfijo(nodo->derecho);
if (nodo->es_operador) printf(")");
}
void liberar(TreeNode *nodo) {
if (!nodo) return;
liberar(nodo->izquierdo);
liberar(nodo->derecho);
free(nodo);
}
int main(void) {
TreeNode *n12 = crearOperando(12);
TreeNode *n8 = crearOperando(8);
TreeNode *n3 = crearOperando(3);
TreeNode *n5 = crearOperando(5);
TreeNode *n4 = crearOperando(4);
TreeNode *sub = crearOperador('-', n8, n3); /* (8 - 3) */
TreeNode *sum12 = crearOperador('+', n12, sub); /* 12 + (8 - 3) */
TreeNode *sum5 = crearOperador('+', n5, n4); /* (5 + 4) */
TreeNode *raiz = crearOperador('-', sum12, sum5); /* (12 + (8 - 3)) - (5 + 4) */
printf("Expresion infija: ");
imprimirInfijo(raiz);
printf("\nResultado: %d\n", evaluar(raiz));
liberar(raiz);
return 0;
}