Archive

Posts Tagged ‘Notación Postfija’

Evaluar expresiones matemáticas

July 25th, 2010 No comments
Share Button

Existen tres notaciones básicas para representar expresiones matemáticas; infija, prefija y postfija.
La infija es la más conocida porque es la que más se utiliza, por ejemplo: (1+2)*(3-4).
En forma prefija se representaría como *+12-34, y en forma postfija sería 12+34-*.

La forma infija resulta muy sencilla para los humanos, estamos acostumbrados a ella y es muy simple. Sin embargo requiere del uso de paréntesis para establecer el orden correcto de las operaciones a realizar, y esto supone un engorro a la hora de programar un evaluador de expresiones.  El “truco” consiste en convertir la expresión de infja a postfija o prefija, de esta forma nos deshacemos de los paréntesis ya que las notaciones prefija y postfija no los necesitan.

Una vez convertida la expresión a notación postfija o prefija es muy fácil crear un árbol binario para calcular el resultado de la expresión.

Los más observadores ya se habrán dado cuenta de que la notación postfija es también conocida como RPN (“Reverse Polish Notation”, notación polaca inversa). Fué inventada por el filósofo y matemático polaco Lukasiewicz precisamente como una notación alternativa para evitar los paréntesis en la expresiones. Más de uno habrá usado esta notación en las calculadoras RPN, especialmente de HP, ¿verdad?

 

Conversión de notación infija a postfija

 

Vamos a ver con un ejemplo muy simple como, usando simplemente un stack (LIFO),  se puede convertir cualquier expresión infija (por compleja que sea) a notación postfija. Explicaré solamente la conversión de infija a postfija. La conversión a prefija es igual de sencilla pero lo dejo como ejercicio de pasatiempo para el que le apetezca.

Se va cogiendo cada elemento de la expresión (de izquierda a derecha) y se siguen estos pasos:

  1. Si el elemento es un número o variable se copia directamente a la salida.
  2. Si es un paréntesis izquierdo se mete en el stack.
  3. Si es un paréntesis derecho, se van sacando uno a uno todos los elementos del tope del stack (y copiándolos en la salida) hasta encontrar un paréntesis izquierdo en el stack. Finalmente ambos paréntesis se descartan.
  4. Si es un operador y en el tope del stack no hay un operador o hay un operador de menor precedencia entonces se añade el nuevo operador al stack.
  5. Si es un operador y en el tope del stack hay un operador de mayor o igual precedencia entonces se saca el operador del stack y se copia en la salida, y se repite la comparación del operador con el nuevo tope del stack.
  6. Cuando ya no quedan más elementos en la expresión se van sacando uno a uno todos los elementos del stack y se copian en la salida.

Usaré el ejemplo inicial en notación infija: (1+2)*(3-4)

  • ( Se mete en el stack.
    STACK[ ( ]  SALIDA[ ]
  • 1 Se copia en la salida.
    STACK[ ( ]  SALIDA[ 1 ]
  • + Operador, en el tope del stack no hay otro operador, se mete en el stack.
    STACK[ +( ]  SALIDA[ 1 ]
  • 2 Se copia en la salida.
    STACK[ +( ]  SALIDA[ 12 ]
  • ) Se sacan del stack y se copian en la salida todos los elementos hasta encontrar un paréntesis izquierdo.
    STACK[ ]  SALIDA[ 12+ ]
  • * Operador, en el tope del stack no hay otro operador, se mete en el stack.
    STACK[ * ]  SALIDA[ 12+ ]
  • ( Se mete en el stack.
    STACK[ (* ]  SALIDA[ 12+ ]
  • 3 Se copia en la salida.
    STACK[ (* ]  SALIDA[ 12+3 ]
  • - Operador, en el tope del stack no hay otro operador, se mete en el stack.
    STACK[ -(* ]  SALIDA[ 12+3 ]
  • 4 Se copia en la salida.
    STACK[ -(* ]  SALIDA[ 12+34 ]
  • ) Se sacan del stack y se copian en la salida todos los elementos hasta encontrar un paréntesis izquierdo.
    STACK[ * ]  SALIDA[ 12+34- ]
  • Ya no quedan más elementos en la expresión, se sacan todos del stack y se copian en la salida.
    STACK[ ]  SALIDA[ 12+34-* ]

El resultado final en notación postfija es 12+34-*

 

Evaluación de expresiones postfijas

 

Una vez que tenemos la expresión en notación postfija resulta muy sencillo evaluarla utilizando de nuevo un simple stack.
Vamos cogiendo cada elemento de la expresión en notación postfija (de izquierda a derecha);

  • Si el elemento es un operando (número, variable o constante) se mete en el stack.
  • Si el elemento es un operador (+, -, *, /, sin, sqrt…) se saca del stack tantos elementos como parámetros necesite el operador, se realiza la operación y el resultado se mete en el stack.
  • El proceso se repite hasta que no queden más elementos en la expresión. Al final del proceso habrá en el stack un sólo elemento que corresponde con el resultado final de la evaluación de la expresión.

Veamos como evaluar la expresión: 12+34-*

  • 1 Es un operando, se mete en el stack.
    STACK[ 1 ]
  • 2 Es un operando, se mete en el stack.
    STACK[ 21 ]
  • + Es un operador, como + es un operador binario (necesita dos elementos) se sacan del stack y se realiza la operación (1 + 2) y el resultado se mete en el stack.
    STACK[ 3 ]
  • 3 Es un operando, se mete en el stack.
    STACK[ 33 ]
  • 4 Es un operando, se mete en el stack.
    STACK[ 433 ]
  • - Es un operador binario, se sacan dos elementos del stack y se realiza la operación (3 – 4) y el resultado se mete en el stack.
    STACK[ (-1)3 ]
  • * Es un operador binario, se sacan dos elementos del stack y se realiza la operación (3 * (-1)) y el resultado se mete en el stack.
    STACK[ (-3) ]
  • Resultado final: -3

El que se haya fijado un poco en este ejemplo se habrá dado cuenta de que en las evaluaciones en notación postfija la extracción del stack de los operandos para realizar una operación debe invertirse. En la evaluación de expresiones prefijas no es necesario puesto que ya salen del stack en su orden correcto.

 

Evaluación de expresiones prefijas

 

Ahora veamos cómo evaluar expresiones prefijas usando el mismo ejemplo: *+12-34

Es común evaluar las expresiones prefijas utilizando un algoritmo más complejo que el de las postfijas y empleando para ello varios stacks. Esto no tiene mucho sentido y es innecesario complicarse la vida porque en realidad el proceso es exactamente el mismo pero en orden inverso (de derecha a izquierda), por lo tanto lo haremos igual que con las expresiones postfijas, usando un solo stack:

  • 4 Es un operando, se mete en el stack.
    STACK[ 4 ]
  • 3 Es un operando, se mete en el stack.
    STACK[ 34 ]
  • - Es un operador, como – es un operador binario (necesita dos elementos) se sacan del stack y se realiza la operación (3 – 4) y el resultado se mete en el stack.
    STACK[ (-1) ]
  • 2 Es un operando, se mete en el stack.
    STACK[ 2(-1) ]
  • 1 Es un operando, se mete en el stack.
    STACK[ 12(-1) ]
  • + Es un operador binario, se sacan dos elementos del stack y se realiza la operación (1 + 2) y el resultado se mete en el stack.
    STACK[ 3(-1) ]
  • * Es un operador binario, se sacan dos elementos del stack y se realiza la operación (3 * (-1)) y el resultado se mete en el stack.
    STACK[ (-3) ]
  • Resultado final: -3

 

Evaluación de expresiones mediante árboles

 

También se puede utilizar un árbol para evaluar las expresiones. Para crearlos usamos un stack y vamos cogiendo cada elemento de la expresión en notación postfija (de izquierda a derecha);

  • Si el elemento es un número o variable se crea un nodo con él y se mete en el stack.
  • Si el elemento es un operador binario se crea un nodo con dicho operador, se extraen del stack dos nodos y se le añaden como hijos, finalmente el nuevo nodo se añade al stack.
  • Si el elemento es un operador unuario se crea un nodo con dicho operador, se extrae del stack un nodo y se le añade como hijo, finalmente el nuevo nodo se añade al stack.
  • El proceso se repite hasta que no queden más elementos en la expresión.

arbol_binario

Para terminar, simplemente recorriendo recursivamente el árbol en inorden podemos calcular el resultado final de la expresión o incluso reconstruirla en su notación infija:

  1. Imprimimos paréntesis izquierdo.
  2. Visitamos subárbol izquierdo (*).
  3. Imprimimos la raíz.
  4. Visitamos subárbol derecho (*).
  5. Imprimimos paréntesis derecho.

(*): El proceso se repite recursivamente en los pasos 2 y 4.

 

Conversiones rápidas de notación infija a prefija y postfija

 

Para terminar vamos a ver cómo convertir cualquier expresión infija en prefija o postfija mentalmente de una forma muy fácil.

Supongamos que queremos convertir esta expresión: 1 – sqrt( 2 + sin( 3 ) ) * 4

Para convertirla a notación prefija añadimos todos los paréntesis redundantes que faltan y movemos los operadores al inicio de sus respectivos paréntesis (en el caso de las funciones sqrt y sin, son operadores unuarios que definen siempre sus propios paréntesis por lo tanto no es necesario moverlos ya que ya están al inicio de sus paréntesis):

prefix_expr

 

Finalmente solo tenemos que eliminar todos los paréntesis y ya tenemos la expresión infija convertida a notación polaca: - 1 * sqrt + 2 sin 3 4

Para convertirla a notación postfija es igual de fácil pero al revés; añadimos los paréntesis redundantes pero ahora movemos los operadores al final de sus paréntesis:

postfix_expr

 

Para terminar, eliminamos todos los paréntesis y ya está: 1 2 3 sin + sqrt 4 * -

Nota: Sea cual sea la conversión a realizar recuerda que los operandos jamás se mueven, sólo se desplazan los operadores!