Á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;
      }
}