5_15_Arboles_desafio_5

# Definimos una clase Nodo que representa cada nodo del árbol de expresiones
class Nodo:
    def __init__(self, valor):
        self.valor = valor  # El valor puede ser un número o un operador (+, -, *, /)
        self.izquierdo = None  # Puntero al nodo hijo izquierdo
        self.derecho = None  # Puntero al nodo hijo derecho

# Función que verifica si un carácter es un operador matemático
def es_operador(c):
    # Retorna True si el carácter es uno de los operadores aritméticos básicos
    return c in "+-*/"

# Función para construir un árbol de expresiones a partir de una expresión en notación postfija
def construir_arbol_expresion(expresion):
    # Usamos una pila para almacenar los nodos mientras construimos el árbol
    pila = []

    # Recorremos cada token en la expresión (asumimos que los tokens están separados por espacios)
    for c in expresion.split():
        if es_operador(c):  # Si el token es un operador, creamos un subárbol
            nodo = Nodo(c)  # Creamos un nodo que contiene el operador actual

            # Los dos últimos nodos en la pila se convierten en hijos del operador
            nodo.derecho = pila.pop()  # El segundo nodo extraído es el hijo derecho
            nodo.izquierdo = pila.pop()  # El primero es el hijo izquierdo

            # Insertamos el subárbol en la pila
            pila.append(nodo)
        else:
            # Si el token es un número, lo convertimos a entero y lo insertamos como nodo hoja
            pila.append(Nodo(int(c)))
    
    # Al final, la pila contendrá un único elemento, que es la raíz del árbol de expresiones
    return pila.pop()

# Función recursiva para evaluar el árbol de expresiones
def evaluar_arbol(nodo):
    # Caso base: si el nodo es una hoja, retornamos su valor (un número)
    if nodo.izquierdo is None and nodo.derecho is None:
        return nodo.valor
    
    # Evaluamos recursivamente los subárboles izquierdo y derecho
    valor_izquierdo = evaluar_arbol(nodo.izquierdo)
    valor_derecho = evaluar_arbol(nodo.derecho)
    
    # Realizamos la operación correspondiente basada en el valor del nodo
    if nodo.valor == '+':
        return valor_izquierdo + valor_derecho
    elif nodo.valor == '-':
        return valor_izquierdo - valor_derecho
    elif nodo.valor == '*':
        return valor_izquierdo * valor_derecho
    elif nodo.valor == '/':
        return valor_izquierdo / valor_derecho  # Suponemos que no hay división por cero

# Prueba del programa con la expresión "5 + 3 * 4"
# La expresión en notación postfija (RPN) es: "5 3 4 * +"
expresion = "5 3 4 * +"
arbol = construir_arbol_expresion(expresion)  # Construimos el árbol de expresiones
resultado = evaluar_arbol(arbol)  # Evaluamos el árbol

# Imprimimos el resultado de la evaluación
print("El resultado de la expresión es:", resultado)