jul 10 2010
Uso de la Notación Postfija en la diagonalización de matrices [ I ]
La notación postfija o notación polaca inversa (eso sonó a pose del kamasutra), es un método algebraico alternativo de introducción de datos. Su nombre viene por analogía con la relacionada notación polaca, una notación de prefijo introducida en 1920 por el matemático polaco Jan Lukasiewicz, en donde cada operador está antes de sus operandos [Wikipedia].
Nosotros normalmente escribimos en la forma infija, es decir:
OPERANDO1 OPERADOR OPERANDO2
5 + 2
La forma postfija consiste en poner el operador al final, lo que seria equivalente a:
OPERANDO1 OPERANDO2 OPERADOR
5 2 +
La notación postfija también puede ser representada en el recorrido en post-orden de un árbol binario que contenga de forma ordenada la expresión algebraica que estamos representando, es decir, si recorremos de la forma IZQUIERDA – DERECHA – RAIZ.
Bueno, ya tenemos planteada la teoría, ahora vamos con una aplicación básica, la cual consiste en resolver una expresión algebraica con signos de colección, por ejemplo:
(1*(2+5))*3
Existen 2 algoritmos que pueden encontrar en la web para esto.
El primero, convierte la expresión infija en postfija y la segunda opera la expresión postfija y saca el resultado.
En este post solo voy a detallar el primer algoritmo, osea de como convertir la expresión infija en postfija, y vendría a ser el siguiente:
Algoritmo de infija a posfija.
Entrada: Expresión Infija: Infija
Salida: Expresión Postija: Posfija
Proceso
i =0
pila p
apilar( p , ’ ( ’ )
infija = ‘ ) ’
Postfija = vacio
Mientras ( p no sea vacio )
Si ( infija [i] es digito )
Posfija += infija
Fin Si
Si ( infija [i] = = ‘ ( ’ )
Apilar ( p, infija [i] )
Fin Si
Si ( infija [i] es operador )
c = tope_de_pila ( p )
Si (c es operador )
Si ( precendencia( c, infija [i])==0 || precedencia(c , infija[i] == 1) )
c = desapilar ( p )
Posfija += c
Fin Si
Fin Si
Fin Si
Si ( infija [ i ] = =’ ) ‘ )
c2 = desapilar( p )
Mientras ( c2 != ‘ ( ’ )
Posfija += c2
c2 = desapilar ( p )
Fin Mientras
Fin Si
i + +
Fin Mientras
Devolver posfija
Fin del Algoritmo
Este algoritmo específicamente resuelve expresiones algebraicas con signos de colección como el paréntesis y con operaciones de un solo digito en cada operando.
Cuando leí este algoritmo en mi libro de “C how to program”, proponía modificarlo para que pueda operar expresiones de mas de un digito en sus operandos, y pues supongo q debe haber varias formas de hacerlo, pero yo elegí la de poner un delimitador de campo del tipo: “p” para positivo y “n” para negativo, de tal forma que la expresión:
12*2-(1*2)
Tendría como equivalente a:
p12*p2-(p1*n2)
Para que así mi algoritmo pueda identificar cuando termina cada numero y q signo se antepone a él.
Esto no fue muy complicado de hacer, solo hay que modificar ciertas partes del algoritmo anterior para poder agregarle mas dígitos a cada operando.
Por ahora les dejaré el código del programa hecho en java (netbeans), en el cual mediante la clase diagonalizacion.Main podrán probar esto de la notación postfija e infija. La diagonalización de la matriz, la conseguí usando como base este algoritmo, y aunque si bien solo cumple para polinomios con raíces enteras, es una buena practica –creo yo- de como aplicar la notación postfija en infjija. Explicaré mas detalladamente como diagonalizar la matriz con la notación postfija e infija en un próximo post, a continuación les dejaré un link de donde bajar el programa en netbeans.
Expresion Infija-Postfija
Saludos!
