Aplicaciones de Pilas

6.
A
P
L
I
C
A
C
I
O
N
D
E
P
I
L
A
S

## Introducción.

Se hablará de la aplicación de las pilas donde se verá la notación infija, posfija, prefija de los cuales son operadores aritméticos, abarcado cada uno de sus aspectos, funcionamiento sus reglas básicas el cómo emplearlos además de que explicaremos detalladamente cada uno de estos y su conversión entre estos mismos además de que se mostraran ejemplos para el mayor entendimiento y un programa que nos ayude a ver en donde se aplicara. En este tema se estudiarán las pilas, su utilización y su implementación más habitual en C++.
Se sabe que las pilas son grupos ordenados de elementos donde se pueden modificar (operaciones básicas). Las aplicaciones de pilas complejas se pueden solucionar expresándose algebraicamente basados en operadores (infija, posfija, prefija). Cada expresión lleva un procedimiento donde los resultados de las expresiones se evaluarán con cada elemente de la pila que llevara.
Estas pilas ampliamente son para solucionar problemas utilizándose generalmente en compiladores y en programas. Su implementación se puede hacer mediante Arrays Y Mediante listas enlazadas.
La pila es una lista de elementos caracterizada porque las operaciones de inserción y eliminación de elementos se realizan solamente en un extremo de la estructura. El extremo donde se realizan estas operaciones se denomina habitualmente cima (top en la nomenclatura inglesa).
La estructura pila se conoce como LIFO (last-in, first-out, último en entrar, primero en salir), que significa “último elemento introducido, primero sacado”. Una vez entendido que es una pila veremos en donde se aplica y como se puede emplear en un programa como en un Los Navegadores en Internet almacenan en una pila las direcciones de los sitios más recientemente visitados o Los editores de texto proporcionan normalmente un botón deshacer que cancela las operaciones de edición recientes y restablece el estado anterior del documento.

## Aplicación de pilas

La idea principal que plantea el autor es que “Las pilas son utilizadas ampliamente para solucionar una amplia variedad de problemas. Se utiliza en compiladores, sistemas operativos y en programas de aplicación. Su implementación se puede hacer mediante Arrays Y Mediante listas enlazadas.” (Joyanes y Luis, 2008, p.450)
Una pila representa una estructura lineal de datos en la que se puede agregar o quitar elementos únicamente por uno de los dos extremos. En consecuencia, los elementos de una pila se eliminan en orden inverso al que se insertaron; es decir, el último elemento que se mete en la pila es el primero que se saca. Debido a esta característica, se le conoce como estructura LIFO (Last-Input, First-Output) el último en entrar es el primero en salir. (Caíro y Guardati, 2006, p.88)
Unos ejemplos de sus aplicaciones podrían ser los siguientes: Los Navegadores en Internet almacenan en una pila las direcciones de los sitios más recientemente visitados. Los editores de texto proporcionan normalmente un botón deshacer que cancela las operaciones de edición recientes y restablece el estado anterior del documento. Llamadas a subprogramas.
Se puede llamar a subprogramas Cuando se tiene un programa que llama a un subprograma, también conocido como módulo o función, internamente se usan pilas para guardar el estado de las variables del programa, así como las instrucciones pendientes de ejecución en el momento que se hace la llamada. Cuando termina la ejecución del subprograma, los valores almacenados en la pila se recuperan para continuar con la ejecución del programa en el punto en el cual fue interrumpido. Además de las variables se recupera la dirección del programa en la que se hizo la llamada, porque a esa posición se regresa el control del proceso.
Supongamos que se está procesando una función y en su interior llama a otra función. La función se abandona para procesar la función de la llamada, pero antes se almacena en una pila la dirección que apunta a la función. Ahora supongamos que esa nueva función llama a su vez a otra función. Igualmente, se almacena su dirección, se abandona y se atiende la petición. Así en tantos casos como existan peticiones. La ventaja de la pila es que no requiere definir ninguna estructura de control ni conocer las veces que el programa estará saltando entre funciones para después retomarlas, con la única limitación de la capacidad de almacenamiento de la pila. Conforme se van cerrando las funciones, se van rescatando las funciones precedentes mediante sus direcciones almacenadas en la pila y se va concluyendo su proceso, esto hasta llegar a la primera.

### Ejemplos en Computación “Llamado a funciones.”

1. El programa principal llama a una función.
2. La función llama a otra función.
3. La pila indica dónde debe regresar la función una vez que se termina la misma (lo indica la pila à última función que hizo el llamado, primera en volver).
4. Aplicación principal FUNCIONES RECURSIVAS.
5. Bucles anidados.
6. Último bucle en abrirse, primero en cerrarse.
7. Condiciones anidadas.
8. Última condición en abrirse, primera en cerrarse.

### Las Aplicaciones que tienen las pilas son las siguientes:

1. Llamadas a subprogramas
2. Recursividad
3. Tratamiento de Expresiones Aritméticas
4. Ordenación

### Por el momento nos enfocaremos en dos aplicaciones que son:

1. Llamadas a subprogramas
Cuando se tiene un programa que llama a un subprograma, también conocido como módulo o función, internamente se usan pilas para guardar el estado de las variables del programa, así como las instrucciones pendientes de ejecución en el momento que hace la llamada.
Cuando termina la ejecución del subprograma, los valores almacenados en la pila se recuperan para continuar con la ejecución del programa en el punto en el cual fue interrumpido. Además de las variables se recupera la dirección del programa la que se hizo la llamada, porque a esa posición se regresa el control del proceso.
2. Tratamiento de Expresiones aritméticas
• 1. A+B = Infija
• 2. AB+ = posfija
• 3. +AB = Prefija
Los operadores básicos son los siguientes que se muestra en la Figura 3:
Se debe de seguir este orden de prioridad en una operación aritmética.
Una vez entendido el orden jerárquico de los operadores podremos implementarlo en una operación ejemplo:
Son evaluados de izquierda a derecha (se evalúa primero el que primero aparece)
#5*4/2 = (5*4) /2 = 10 # (5+3) *2 = 16
Cuando aparecen varios operadores de potenciación juntos la expresión se evalúa de derecha a izquierda
--- 2^3^2 = 2^ (3^2) = 2^9 = 512

## Expresiones Básicas

Dada la expresión A + B se dice que ésta se encuentra en notación infija porque el operador (+) se encuentra entre los operandos (A y B).

# A+B

Dada la expresión AB + se dice que ésta se encuentra en notación postfija, porque el operador (+) se encuentra después de los operandos (A y B).

# AB+

Dada la expresión + AB se dice que ésta se encuentra en notación prefija, porque el operador (+) está precediendo a los operados (A y B).

# +AB

Nota: para la notación postfija y prefija no lleva paréntesis

## Reglas básicas

1. Los operandos se agregan directamente al resultado.
2. Un paréntesis izquierdo se mete a la pila y tiene prioridad o precedencia a cero (0).
3. Un paréntesis derecho saca los elementos de la pila y los agrega al resultado hasta sacar un paréntesis izquierdo.
4. Los operadores se insertan en la pila si:
a) La pila está vacía.
b) El operador en el tope de la pila tiene menor precedencia.
c) Si el operador en el tope tiene mayor precedencia se agrega al resultado (repetir esta operación hasta encontrar un operador con menor precedencia o la pila está vacía).
5. Cuando se termina de procesar la cadena que contiene la expresión infijo se vacía la pila pasando los elementos al resultado.

## 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.

## Notación prefija y postfija de una expresión aritmética

La idea principal que plantea el autor es que “La forma de escribir operaciones aritméticas sitúa el operador entre sus dos operados, conocida como notación infija. Esta forma de notación obliga en muchas ocasiones a utilizar paréntesis para indicar el orden de evaluación.” (Joyanes y Zahonero, 2007, p.325)

## Notación infija

Es la notación común de fórmulas aritméticas y lógicas, en la cual se escriben los operadores entre los operados 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. La Expresión o Notación Infija es la forma más común que utilizamos para escribir expresiones matemáticas.

# EXPRESIÓN INFIJA: X + Z * W

La notación infija puede estar completamente en paréntesis a diferencia de las las notaciones de prefijo o posfijo, es necesario rodear entre paréntesis a los grupos de operandos y operadores, para indicar el orden en el cual deben ser realizadas las operaciones y no hayan diferentes resultados al no realizarse correctamente.
En la ausencia de paréntesis, ciertas reglas de prioridad determinan el orden de las operaciones y los resultados pueden ser cambiantes.
EJEMPLO: 3*4=12 3*4+2=14 3*(4+2)=18
Ventaja: Es la forma natural de escribir expresiones aritméticas La notación infija puede estar completamente en paréntesis a diferencia de las las notaciones de prefijo o posfijo, es necesario rodear entre paréntesis a los grupos de operandos y operadores, para indicar el orden en el cual deben ser realizadas las operaciones y no hayan diferentes resultados al no realizarse correctamente.
En la ausencia de paréntesis, ciertas reglas de prioridad determinan el orden de las operaciones y los resultados pueden ser cambiantes.
EJEMPLO: 3*4=12 3*4+2=14 3*(4+2)=18
Ventaja: Es la forma natural de escribir expresiones aritméticas.

## Evaluar notación infija

- Las potencias tiene prioridad sobre cualquier operación.
- La multiplicación y la división tienen prioridad sobre la suma y la resta.
- Si se representa un paréntesis se deben realizar primero las operaciones dentro de este. si hay un paréntesis dentro de otro tiene prioridad el interno.

  ## Notación 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 las 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.
  El operador ocupa la posición después de los operandos.

  ## Características principales:

  • La operación posfija no es exactamente lo inverso a la operación prefija equivalente: (A+B)*C AB+C*
  • 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.
  Ventaja: La notación postfija (como la prefija) no necesita paréntesis.

  ## Conversión de infija a postfija

  • Se parte de una expresión en notación infija que tiene operandos, vienen representados por letras, números y operandos.
  • Se realiza utilizando una pila vacía donde se almacenan los operadores y paréntesis.
  • La expresión se lee de izquierda a derecha, carácter a carácter.
  • Los operadores se meten en la pila siempre que tengan mayor prioridad.
  • Si la prioridad es menor se saca el elemento cima de la pila.
  • Los paréntesis izquierdos siempre se meten a la pila.
  • Cuando se lee un paréntesis derecho se sacan todos los operadores de la pila, pasando a formar parte de la expresión, hasta llegar al paréntesis izquierdo, el cual se eliminan porque no forman parte de la expresión.
  • El proceso termina cuando ya no hay más elementos de la expresión y la pila este vacía.

  ### Ejemplo:

  ## Notación 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:
  La Expresión o Notación Prefija nos indica que el operador va antes de los operandos 1. Los operandos conservan el mismo orden que la notación infija equivalente.
  2. No requiere de paréntesis para indicar el orden de precedencia de operadores ya que él es una operación.
  3. Se evalúa de izquierda a derecha hasta que encontrémosle primer operador seguido inmediatamente de un par de operandos.
  4. 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. +A B C (A+B)*C

  ## Conversión de infija a prefija

  La conversión se hace de la misma forma que de infija a posfija, con las siguientes diferencias:
  • Se lee la expresión a evaluar de derecha a izquierda
  • El paréntesis que cierra entra a la pila y lo saca el paréntesis que abre.
  • Se invierte la solución.

  ## CONCLUSIÓN

  En conclusión en este tema de aplicaciones de pilas pudimos trabajar más a fondo cuales son las funciones que tienen las pilas dentro de la programación y entender cómo se deben utilizar estas mismas dentro de un programa, al igual que vimos que podemos trabajar con operaciones aritméticas y convertirlas unas a otras, como por ejemplo convertir notaciones infijas a prefijas pero aunque parezca un método fácil es a la vez muy laborioso, hay que tener en cuenta que este tipo de notaciones tiene tanto sus ventajas como sus desventajas , también nos pudimos percatar que a veces la falta de paréntesis o colocar mal un operador puede provocar un error dentro de nuestro programa.

  ## BIBLIOGRAFIA

  • Cairó, Osvaldo y Guardati, Silvia. (2006).Estructuras de datos (3ª. Edición). McGraw Hill, Pág.88
  • Joyanes, Sánchez y Zahonero. (2007).Estructura de datos en c++.McGraw Hill, Pag.325
  • Joyanes, Luis (2008).Fundamentos de programación (4ª Edición). McGraw Hill, Pag. 450)
  • LIDIA.Pilas y expresiones aritmeticas. Recuperado de: http://quegrande.org/ apuntes/EI/1/EDI/teoria/06-07/tad_-_pila_-_expresiones_aritmeticas.pdf
  • Sin autor.Algoritmos y estructuras de datos, Pilas. Recuperado de: http://informatica.uv.es/iiguia/AED/teoría/apuntes/cuatr2/AED.Tema.11.pdf
  • Sin autor. Estructura de datos. Recuperado de: https://upload.wikimedia.org /wikipedia/commons/5/51/APUNTES.pdf (26-29)
  • Nieves, E. (2012).Estructura datos pilas y colas. Recuperado de: https://es.slideshare.net/nieves1988/estructura-datos-pilas-y-colas
  • Rodrigo,P.(2013).Pila en C++. Recuperado de: https://www.programacion.com. Py/escritorio/c/pilas-en-c • Javi V.R, (2010).Evaluar expresiones aritméticas. Recuperado de: http://www.neptalium.com/blog/tag/notacion-prefija/
  • Andrade, T. (2017). Notacion Infija, Postfija, Prefija y Polaca. Recuperado de:https://compilador.wikispaces.com/Notacion+Infija,+Postfija,Perfija+y+Polaca.

  ## COMPLEMENTOS

  Aplicación de pila: Evaluación expresión postfija