Hola.
El algoritmo a desarrollar es muy sencillo. Lo que tienes que hacer es tomar la expresión en notación polaca inversa y empezar a leerla por la derecha.
Date cuanta de que el árbol se va construyendo en un recorrido en profundidad.
Lo primero es crear un nodo inicial. A partir de él has de hacer lo siguiente:
- Si te encuentras con un operador (+,-,*,etc) creas un nodo de tipo, digamos, nodo_op, lo añades como hijo del nodo actual y pasas al nuevo nodo.
- Si te encuentras con un número creas un nodo de tipo nodo_num y lo añades como hijo al nodo actual (pero no pasas al nuevo nodo).
· Para los dos casos anteriores, si no hubiera más hijos libres en el nodo actual (ya que no puede haber más de dos) sigues el recorrido en profundidad del árbol hasta encontrar un nodo con un hijo libre.
Cuando hayas acabado de crear el árbol de la expresión, todas las hojas deberán ser nodos del tipo nodo_num, y el resto de nodos del tipo nodo_op.
Ahora sólo te resta ir recorriendo el árbol en profundidad con una función recursiva que vaya resolviendo los nodo_op. Algo de este estilo:
int resolver(nodo)
{
si nodo es de tipo nodo_num
devolver valor del nodo
si no
devolver resolver(hijo_izq) op resolver(hijo_dcho)
}
donde
op es la operación que está asociada al nodo_op actual.
Con esta explicación ya sólo te resta implementar tal cual lo que te he descrito.
Un saludo.
Ruben3d
