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 con clases en Python.

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 una clase que diferencia entre operadores y operandos mediante el atributo es_operador.

class Nodo:
    def __init__(self, valor=None, operador=None, es_operador=False):
        self.valor = valor
        self.operador = operador
        self.es_operador = es_operador
        self.izquierdo = None
        self.derecho = None

10.3 Creación de nodos

Definimos dos helpers: uno para operandos y otro para operadores.

class ArbolExpresion:
    def crear_operando(self, valor):
        return Nodo(valor=valor, es_operador=False)

    def crear_operador(self, operador, izquierdo, derecho):
        nodo = Nodo(operador=operador, es_operador=True)
        nodo.izquierdo = izquierdo
        nodo.derecho = derecho
        return nodo

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.

class ArbolExpresion:
    # ...
    def evaluar(self, nodo):
        if nodo is None:
            return 0
        if not nodo.es_operador:
            return nodo.valor

        izq = self.evaluar(nodo.izquierdo)
        der = self.evaluar(nodo.derecho)
        return izq + der if nodo.operador == "+" else izq - der

10.5 Impresión infija

Para visualizar la expresión usamos un recorrido en orden y agregamos paréntesis.

class ArbolExpresion:
    # ...
    def imprimir_infijo(self, nodo):
        if nodo is None:
            return
        if nodo.es_operador:
            print("(", end="")
        self.imprimir_infijo(nodo.izquierdo)
        if nodo.es_operador:
            print(f" {nodo.operador} ", end="")
        else:
            print(nodo.valor, end="")
        self.imprimir_infijo(nodo.derecho)
        if nodo.es_operador:
            print(")", end="")

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 en Python 3

El siguiente archivo implementa la expresión propuesta y permite reutilizar la estructura para cualquier combinación de sumas y restas.

class Nodo:
    def __init__(self, valor=None, operador=None, es_operador=False):
        self.valor = valor
        self.operador = operador
        self.es_operador = es_operador
        self.izquierdo = None
        self.derecho = None


class ArbolExpresion:
    def crear_operando(self, valor):
        return Nodo(valor=valor, es_operador=False)

    def crear_operador(self, operador, izquierdo, derecho):
        nodo = Nodo(operador=operador, es_operador=True)
        nodo.izquierdo = izquierdo
        nodo.derecho = derecho
        return nodo

    def evaluar(self, nodo):
        if nodo is None:
            return 0
        if not nodo.es_operador:
            return nodo.valor
        izq = self.evaluar(nodo.izquierdo)
        der = self.evaluar(nodo.derecho)
        return izq + der if nodo.operador == "+" else izq - der

    def imprimir_infijo(self, nodo):
        if nodo is None:
            return
        if nodo.es_operador:
            print("(", end="")
        self.imprimir_infijo(nodo.izquierdo)
        if nodo.es_operador:
            print(f" {nodo.operador} ", end="")
        else:
            print(nodo.valor, end="")
        self.imprimir_infijo(nodo.derecho)
        if nodo.es_operador:
            print(")", end="")


if __name__ == "__main__":
    arbol = ArbolExpresion()
    n12 = arbol.crear_operando(12)
    n8 = arbol.crear_operando(8)
    n3 = arbol.crear_operando(3)
    n5 = arbol.crear_operando(5)
    n4 = arbol.crear_operando(4)

    sub = arbol.crear_operador("-", n8, n3)       # (8 - 3)
    sum12 = arbol.crear_operador("+", n12, sub)   # 12 + (8 - 3)
    sum5 = arbol.crear_operador("+", n5, n4)      # (5 + 4)
    raiz = arbol.crear_operador("-", sum12, sum5) # (12 + (8 - 3)) - (5 + 4)

    print("Expresion infija:", end=" ")
    arbol.imprimir_infijo(raiz)
    print()
    print("Resultado:", arbol.evaluar(raiz))
Ejecutar en editor online
Retornar