Ir al contenido principal

Árbol binario de expresión y Notación Posfija (II)

En una publicación anterior, hablaba sobre que es la notación posfija, para que puede ser útil y mostraba un pequeño ejemplo con una expresión aritmética simple:

(9 - (5 + 2)) * 3

Pues bien, hoy voy a mostraros como podemos crear el árbol binario correspondiente para analizar o evaluar esta expresión, haciendo uso del recorrido en postorden.

Lo primero que debemos hacer es crear el árbol, respetando las siguientes reglas:

⦁ Los nodos con hijos (padres) representarán los operadores de la expresión.
⦁ Las hojas (terminales sin hijos) representarán los operandos.
⦁ Los paréntesis generan sub-árboles.

A continuación podemos ver cómo queda el árbol para la expresión del ejemplo (9 - (5 + 2)) * 3:




Si queremos obtener la notación postfija a partir de este árbol de expresión, debemos recorrerlo en postorden (nodo izquierdo – nodo derecho – nodo central), obteniendo la expresión: 952+-3x

Así, si quisiéramos evaluar la expresión, podemos hacer uso de un algoritmo recursivo. A continuación tenemos el pseudocódigo que realiza esta tarea:

Recorrer en PostOrden(NODO)
    Si NODO es válido entonces
        Recorrer en PostOrden(NODO.Izquierdo)
        Recorrer en PostOrden(NODO.Derecho)
        Evaluar(NODO)

Escribir este algoritmo en alguno de los lenguajes de programación típicos (C, C++, C#, Javascript, Python, Perl, etc.) ya no tiene ningún misterio. Por ejemplo en C++, tendríamos algo como lo siguiente, obviamente no está completo, pero representa claramente la idea principal:
...
void MathHelpers::PostOrden(Arbol* pNodo)
{
     if (pNodo)
    {
         PostOrden(pNodo->Izq);
         PostOrden(pNodo->Der);
         pNodo->Eval;
    }
}
void Arbol::Eval()
{
     switch(pNodo->Operador)
     {
         case ‘-‘:
             this->Valor = this->Izq - this->Der;
         break;
         case ‘+’:
             this->Valor = this->Izq + this->Der;
         break;
         case ‘x’:
             this->Valor = this->Izq * this-Der;
         break;
         case ‘/’:
             this->Valor = this->Izq / this->Der;
         break;
      }
}

Comentarios

  1. La verdadera expresión sería (9-(5+2))*3

    ResponderEliminar
  2. Si Ramón, si has leído el artículo verás que esa es exactamente la expresión indicada y en postorden sería: 952+-3x

    ResponderEliminar
    Respuestas
    1. Lo que pasa que la expresion en el dibujo de fondo azul, donde esta el arbol, la expresion esta mal, ya que dice (9-(5+2)*3), checalo por que te confunde. saludos

      Eliminar
    2. Hola Hector y muchas gracias! Infografía corregida. Un saludo.

      Eliminar
  3. ¿Hay algún algoritmo que dada una expresión algebraica me cree la notación polaca prefija?

    ResponderEliminar

Publicar un comentario

Entradas populares de este blog

Como usar el TL431 (muy facil)

En este artículo, no vamos a entrar en el funcionamiento interno de este IC, ni tampoco en sus características técnicas, puesto que para esos fines ya existe su hoja de datos correspondiente. Más bien, lo que pretendo aquí es dejar constancia de como podemos utilizar este IC desde un punto de vista práctico, útil y sobre todo de una manera sencilla, con el objetivo de que cualquiera pueda utilizarlo. Si has llegado hasta aquí, probablemente ya sabes que por internet hay mucha información sobre este IC, pero también bastante confusa o excesivamente técnica, sin mostrar tan siquiera un ejemplo de funcionamiento, o como calcular sus pasivos. Pues se acabó, a partir de hoy y después de leer este post, ya te quedará claro como utilizar el TL431 para obtener una tensión de referencia estable y precisa. Vamos al grano y que mejor que empezar aclarando que el TL431 NO ES EXACTAMENTE UN ZENER como se empeñan en decir en muchos sitios, es verdad que se le conoce como el Zener Progra

Expresión Regular para números en Notación Científica (1.5e-10)

No cabe duda que las expresiones regulares tienen un potencial de mucho valor a la hora de analizar textos, ya sea para marcado, búsqueda de patrones, o incluso la programación de un compilador, un analizador de frases, de expresiones matemáticas, etc.   En esta ocasión he tenido que echar mano de ellas para el análisis de textos matemáticos en los cuales aparecen números en Notación Científica (con exponentes del tipo 1.5E-10). Pues bien, una expresión regular que me está funcionando bastante bien es la siguiente:   [-+]?[0-9]*\.?[0-9]+([eE][-+]?[0-9]+)?    Esta expresión regular se puede descomponer en los siguientes bloques, para poder interpretarla con mayor facilidad:  El primer bloque [-+]? está indicando que el número podría estar precedido opcionalmente de un signo - o un signo + El segundo bloque [0-9]* indica que podría aparecer un número de 0 o más dígitos del 0 al 9  El tercer bloque indica que también de manera opcional podría aparecer un pun

Programadores de Malware ¿Malas prácticas?

Cuando uno se enfrenta al análisis de un nuevo malware, son muchos los frentes que podemos abrir y los enfoques que podemos darle. Como es lógico, un primer paso será identificar que es un malware de aquello que no lo es, y en ocasiones esto es preciso hacerlo con la mayor rapidez posible. Muchas veces no contamos con el tiempo necesario para hacer un análisis completo a priori, y lo único que necesitamos es tomar decisiones tempranas para iniciar todos los protocolos oportunos ante una nueva muestra "maléfica". Parece lógico pensar, que un código que inicialmente está ofuscado, empaquetado, o que hace uso de determinadas APIs del sistema, ya tiene una cierta probabilidad de ser malware y por lo tanto empezar a tratarlo de manera especial. Durante estos días he estado analizando un nuevo malware, posiblemente una variante de tantas que andan circulando en estos días por internet. En concreto, lo que tengo entre manos es un Ransomware, si compañeros, un especimen