• Categories
• Programación de computadoras
• Notación
• Física y matemáticas
• Matemática
• Notación matemática

Citation preview

TECNOLÓGICO DE ESTUDIOS SUPERIORES DE JOCOTITLÁN

INGENIERÍA EN SISTEMAS COMPUTACIONALES

LENGUAJES Y AUTOMATAS II

“PRACTICA 1: NOTACION PREFIJA INFIJA Y POSTFIJA”

A L U M N O: VÍCTOR JAVIER RAMÍREZ DÍAZ,

DOCENTE: ING ERIKA CORTES NAZAR

JOCOTITLÁN, ESTADO DE MÉXICO A 03 DE OCTUBRE DE 2017

RESUMEN En el presente trabajo se aborda el tema sobre que es la notación y los diferentes tipos de notaciones que existen (infija, postfija, prefija), así como ejercicios sobre estas notaciones esto para el proyecto en la materia de lenguajes y autómatas II de la carrera de Ingeniería en Sistemas Computacionales, en el Tecnológico de Estudios Superiores de Jocotitlán. Se presentan algunos conceptos de estos temas, así mismo las soluciones de los errores de este tipo.

INDICE GENERAL Resumen……………………………………………………………… I Introducción…………………………………………………………..II Marco Teórico………………………………………………………...II Desarrollo……………………………………………………………..III Conclusiones…………………………………………………………V Referencias……………………………………………………………V

1

INTRODUCCION La presente investigación se refiere al tema de los diferentes tipos de notaciones y como nos van ayudar en el compilador, estos en algún momento nos van a causar algún conflicto a la hora de que se programen ya que en muchas ocasiones el desarrollador no detecta ciertas inconsistencias de este tipo normalmente en los datos y se cree que se ha desarrollado un buen compilador cuando no es así. Hay que señalar que las posibles operaciones que puedan llegar hacer en nuestro compilador y tomarlos en cuenta ya que en ocasiones solo se pueden hacer operaciones de dos variables y necesitamos realizarlas de más de 5 variables.

OBJETIVOS DE LA PRÁCTICA El maestro nos pidió realizar una práctica, en la cual tendríamos que identificar las diferentes notaciones para poder desarrollar un programa en donde expliquemos este concepto. MARCO TEORICO NOTACIONES Las notaciones son una forma especial en la que se pueden expresar una expresión matemática y puedan ser de 3 formas: infija, prefija y posfija. Los prefijos, Pre - Pos - In se refieren a la posición relativa del operador con respecto a los dos operandos. NOTACION INFIJA Es la notación común de fórmulas aritméticas y lógicas, en la cual se escriben los operadores entre los operandos en que están actuando (ej. 2 + 2). No es tan simple de analizar por las computadoras, como la notación prefija o la notación postfija, aunque muchos lenguajes de programación la utilizan debido a su familiaridad. NOTACION POSTFIJA Como su nombre lo indica se refiere a que el operador ocupa la posición después de los operandos sus características principales son: el orden de los operandos se conserva igual que la expresión infija equivalente no utiliza paréntesis ya que no es una operación ambigua. Su principio es el de evaluar los datos directamente cuando se introducen y manejarlos dentro de una estructura LIFO (Last In First Out), lo que optimiza los procesos a la hora de programar. Básicamente la diferencias con el método algebraico o notación de infijo es que, al evaluar los datos directamente al introducirlos, no es necesario ordenar la evaluación de los mismos, y que para ejecutar un comando, primero se deben introducir todos sus argumentos, así, para hacer una suma 'a+b=c' el RPN lo manejaría a b +, dejando el resultado 'c' directamente. 2

-La operación posfija no es exactamente lo inverso a la operación prefija equivalente: (A+B)*C AB+C* NOTACION PREFIJA Es una forma de notación para la lógica, la aritmética, y el álgebra. Su característica distintiva es que coloca los operadores a la izquierda de sus operandos sus características principales son: -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. DESARROLLO Hay otros dos formatos de expresión muy importantes que, al principio, pueden no parecer obvios. Considere la expresión infija A + B. ¿Qué pasaría si moviéramos el operador antes de los dos operandos? La expresión resultante sería + A B. Del mismo modo, podríamos mover el operador al final. Obtendríamos A B +. Estas expresiones se ven un poco extrañas. Estos cambios en la posición del operador con respecto a los operandos crean dos nuevos formatos de expresión, la notación prefija y la notación sufija (o postfija). La notación prefija requiere que todos los operadores precedan a los dos operandos sobre los que actúan. La notación sufija, por otro lado, requiere que sus operadores aparezcan después de los operandos correspondientes. Algunos ejemplos más deberían ayudar a hacer esto un poco más claro. A + B * C se escribiría como + A * B C en la notación prefija. El operador de multiplicación aparece inmediatamente antes de los operandos B y C, denotando que el * tiene precedencia sobre el +. El operador de adición aparece entonces antes de la A y del resultado de la multiplicación. En notación sufija, la expresión sería A B C * +. Una vez más, el orden de las operaciones se conserva ya que el * aparece inmediatamente después de la B y la C, denotando que el * tiene precedencia, con el + apareciendo después. Aunque los operadores se movieron y ahora aparecen antes o después de sus respectivos operandos, el orden de cada operando se mantuvo exactamente igual en relación con los demás.

3

Expresión infija

Expresión prefija

Expresión sufija

A+B

+AB

AB+

A+B*C

+A*BC

ABC*+

Ahora considere la expresión infija (A + B) * C. Recuerde que en este caso, la notación infija requiere los paréntesis para forzar que se lleve a cabo la adición antes de la multiplicación. Sin embargo, cuando A + B fue escrito en notación prefija, el operador de adición fue movido simplemente antes de los operandos, + A B. El resultado de esta operación se convierte en el primer operando para la multiplicación. El operador de multiplicación se mueve delante de toda la expresión, dándonos * + A B C. Igualmente, en notación sufija A B + obliga a que la adición ocurra primero. La multiplicación se puede hacer sobre ese resultado y el operando restante C. La expresión sufija correcta es entonces A B + C *.

Considere nuevamente estas tres expresiones, como lo muestra la tabla siguiente. Ha ocurrido algo muy importante. ¿A dónde se fueron los paréntesis? ¿Por qué no los necesitamos en las notaciones prefija y sufija? La respuesta es que los operadores ya no son ambiguos con respecto a los operandos sobre los que actúan. Solamente la notación infija requiere los símbolos adicionales. El orden de las operaciones dentro de las expresiones prefijas y sufijas está completamente determinado por la posición del operador y nada más. De muchas maneras, esto hace que la notación infija sea la notación menos deseable de usar.

Expresión infija

Expresión prefija

Expresión sufija

(A + B) * C

*+ABC

AB+C*

La siguiente tabla nos muestra algunos ejemplos adicionales de expresiones infijas y las expresiones equivalentes en notaciones prefija y sufija. Asegúrese de entender cómo son equivalentes en términos del orden de las operaciones que se están realizando.

4

Expresión infija

Expresión prefija

Expresión sufija

A+B*C+D

++A*BCD

ABC*+D+

(A + B) * (C + D)

*+AB+CD

AB+CD+*

A*B+C*D

+*AB*CD

AB*CD*+

A+B+C+D

+++ABCD

AB+C+D+

Conversión de expresiones infijas a notaciones prefija y sufija

La primera técnica que vamos a considerar utiliza la noción de una expresión completamente agrupada que se discutió anteriormente. Recordemos que A + B * C se puede escribir como (A + (B * C)) para mostrar explícitamente que la multiplicación tiene precedencia sobre la adición. Sin embargo, al observar más de cerca, puede verse que cada pareja de paréntesis también indica el comienzo y el final de un par de operandos con el operador correspondiente en la mitad. Observe el paréntesis derecho en la subexpresión (B * C) anterior. Si tuviéramos que mover el símbolo de multiplicación a esa posición y quitar el paréntesis izquierdo correspondiente, nos daría B C *, de hecho habríamos convertido la subexpresión a notación sufija. Si el operador de adición también es movido a la posición de su paréntesis derecho correspondiente y se elimina el paréntesis izquierdo que le corresponde, se produciría la expresión sufija completa

Traslado de operadores a la derecha para producir la notación sufija

Si hacemos lo mismo pero en lugar de mover el símbolo a la posición del paréntesis derecho, lo movemos a la izquierda, obtenemos la notación prefija. La posición de la pareja de paréntesis es en realidad una pista sobre la posición final del operador encerrado entre ellos.

Traslado de operadores a la izquierda para producir la notación prefija.

Así que, para convertir una expresión, independientemente de su complejidad, ya sea a notación prefija o a notación sufija, agrúpela completamente utilizando el orden de las operaciones. A continuación, mueva cada operador a la posición correspondiente de los 5

paréntesis izquierdo o derecho dependiendo de si desea obtener la expresión en notación prefija o en notación sufija. La siguiente es una expresión más compleja: (A + B) * C - (D - E) * (F + G). El siguiente esquema muestra la conversión a las notaciones sufija y prefija.

Conversión de una expresión compleja a notaciones prefija y sufija

-Conversión general de notación infija a notación sufija la expresión infija es una cadena de símbolos delimitados por espacios. Los símbolos de operaciones son *, /, + y -, junto con los paréntesis izquierdo y derecho, ( y ). Los símbolos de operandos son los identificadores de un solo carácter A, B, C, y así sucesivamente. Los siguientes pasos producirán una cadena de símbolos en el orden sufijo. 1. Crear una pila vacía llamada pilaOperadores para almacenar los operadores. Crear una lista vacía para almacenar la salida. 2. Corvertir la cadena de entrada de notación infija a una lista, usando el método split. 3. Recorrer la lista de símbolos de izquierda a derecha: o Si el símbolo es un operando, agregarlo al final de la lista de salida. o Si el símbolo es un paréntesis izquierdo, enviarlo a pilaOperadores. o Si el símbolo es un paréntesis derecho, extraer de pilaOperadores hasta que el correspondiente paréntesis izquierdo se haya extraído. Agregar cada operador al final de la lista de salida. o Si el símbolo es un operador *, /, +, ó -, incluirlo en pilaOperadores. No obstante, extraer previamente de la pila los operadores que tengan mayor o igual precedencia y agregarlos a la lista de salida. 4. Cuando la expresión de entrada ha sido procesada completamente, verificar pilaOperadores. Todos los operadores que aún estén almacenados en ella se deben enviar a la lista de salida. La siguiente imagen muestra el algoritmo de conversión trabajando sobre la expresión A * B + C * D. Observe que el primer operador * se elimina al verse el operador +. Además, el + permanece en la pila cuando aparece el segundo *, ya que la multiplicación tiene precedencia sobre la adición. Al final de la expresión infija, se extrae dos veces de la pila, eliminando ambos operadores y colocando el + como el último operador en la expresión sufija. 6

Conversión de A * B + C * D a notación sufija

Para codificar el algoritmo en Python, usaremos un diccionario llamado precedencia para almacenar los valores de precedencia para los operadores. Este diccionario mapeará cada operador a un entero que se pueda comparar con los niveles de precedencia de otros operadores (hemos utilizado arbitrariamente los números enteros 3, 2 y 1). El paréntesis izquierdo recibirá el valor más bajo posible. De esta manera cualquier operador que se compara con él tendrá mayor precedencia y se colocará encima de él. La línea 15 define los operandos como cualquier carácter en mayúsculas o dígito. La función de conversión completa se muestra en el ActiveCode 1.

A continuación se muestran algunos ejemplos de ejecución en la consola de Python. >>> infija_a_sufija("( A + B ) * ( C + D )") 'A B + C D + *' >>> infija_a_sufija("( A + B ) * C") 'A B + C *' >>> infija_a_sufija("A + B * C") 'A B C * +' >>> CONCLUSIONES 7

Ventajas 





 



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.

Desventajas 





La adopción casi universal de la notación algebraica en los sistemas educativos hace que no haya muchas razones prácticas inmediatas para que los alumnos aprendan la notación polaca inversa. No obstante, muchos estudiantes afirman que, una vez aprendida, la notación polaca inversa simplifica en gran manera el cálculo de expresiones complejas. Es difícil usar la notación polaca inversa al escribir a mano, dada la importancia de los espacios para separar operandos. Se requiere un caligrafía muy clara para evitar confundir, por ejemplo, 12 34+ (=46) de 123 4+ (=127) o 1 234+ (=235). Las calculadoras RPN son relativamente raras. Forzado a usar una calculadora algebraica, el usuario de una calculadora RPN típicamente comete errores más frecuentemente debido a sus hábitos de uso normales. No obstante, esto no es un problema tan grave en la actualidad, debido a que muchos sistemas operativos pueden emular calculadoras RPN.

Es importante tener en cuenta que tanto en el programa de conversión de expresiones sufijas como en el programa de evaluación de expresiones sufijas asumimos que no había errores en la expresión de entrada. Utilizando estos programas como punto de partida, usted puede fácilmente pensar cómo podría incluirse una detección de errores y la generación de informes 8

REFERENCIAS https://compilador.wikispaces.com/Notacion+Infija,+Postfija,Perfija+y+Polaca https://prezi.com/z4-i3-1pjvf0/lenguajes-y-automatas-ii/

9