5_15_Arboles_desafio_5
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
# 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)
Python
INFO