COMPILADORES (Notacion Postfija, infija, )

NOTACION POSTFIJA

Para evaluar una expresión en notación infija en un valor específico para X se deben seguir las reglas matemáticas para la prioridad de las operaciones:

1. Las potencias tienen prioridad sobre cualquier operación
2. La multiplicación y la división tienen prioridad sobre la suma y la resta.
3. Si se presenta un paréntesis, se deben realizar primero las operaciones dentro de éste. Si hay un paréntesis dentro de otro tiene prioridad el paréntesis interno.

Por el contrario, en la notación postfija siempre se trabaja de izquierda a derecha; note además que la notación postfija no tiene paréntesis por la forma lineal en que se lee. Comparemos un ejemplo en donde se evalúa un valor en una expresión utilizando estas dos notaciones.

Ejemplo:

La postfija seria: 5 4 * 2 6 * 7 - -

NOTACION PREFIJA

Los operandos conservan el mismo orden que la notación infija equivalente.

• No requiere de paréntesis para indicar el orden de precedencia de operadores ya que el es una operación.
• Se evalúa de izquierda a derecha hasta que encontrémosle primer operador seguido inmediatamente de un par de operandos.
• Se evalúa la expresión binaria y el resultado se cambia como un nuevo
• operando.

• Se repite este hasta que nos quede un solo resultado.

Notación prefija: El orden es operador, primer operando, segundo.

Ejemplo:

+ab

POLACA INVERSA

• Los cálculos se realizan secuencialmente según se van introduciendo operadores, en vez de tener que esperar a escribir la expresión al completo. Debido a esto, se cometen menos errores al procesar cálculos complejos.

• El proceso de apilación permite guardar resultados intermedios para un uso posterior. Esta característica permite que las calculadoras RPN computen expresiones de complejidad muy superior a la que alcanzan las calculadoras algebraicas.

• No requiere paréntesis ni reglas de preferencia, al contrario que la notación algebraica, ya que el proceso de apilamiento permite calcular la expresión por etapas.

• En las calculadoras RPN, el cálculo se realiza sin tener que apretar la tecla "=" (aunque se requiere pulsar la tecla "Enter" para añadir cifras a la pila).

• El estado interno de la calculadora siempre consiste en una pila de cifras sobre las que se puede operar. Dado que no se pueden introducir operadores en la pila, la notación polaca inversa es conceptualmente más sencilla y menos dada a errores que otras notaciones.

• En términos educativos, la notación polaca inversa requiera que el estudiante comprenda la expresión que se está calculando. Copiar una expresión algebraica directamente a una calculadora sin comprender la aritmética dará un resultado erróneo.

Ejemplo:

La expresión algebraica 5+((1+2)*4)-3 se traduce a la notación polaca inversa como 5 1 2 + 4 * + 3 - y se evalúa de izquierda a derecha según se muestra en la siguiente tabla. La "Pila" es la lista de los valores que el algorimo mantiene en su memoria después de realizar la operación dada en la segunda columna.

COLAS DE PRIORIDAD

Una cola de prioridades es una estructura de datos en la que los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen.

OPERACIONES
Las operaciones de las colas de prioridad son las mismas que las de las colas genéricas:Crear: se crea la cola vacía.
Encolar: se añade un elemento a la cola, con su correspondiente prioridad. Desencolar: se elimina el elemento frontal de la cola. Frente: se devuelve el elemento frontal de la cola.
Ejemplos: de la vida diaria serían la sala de urgencias de un hospital, ya que los enfermos se van atendiendo en función de la gravedad de su enfermedad.