Pilas Estaticas Equipo 4

Vista previa del material en texto

Centro Universitario de Ciencias
Exactas e Ingenierías
Ingeniería informática
SEMINARIO DE SOLUCIÓN DE PROBLEMAS DE ESTRUCTURAS DE DATOS I
Equipo 4
- Ruiz Estrada Montserrat
- Sanchez De La Cruz Diego Oswaldo
- Sanchez Gomez Edgardo Enrique
- Sevilla Nungaray David
- Valenciano Tadeo Jeremy Esau
- Vázquez Bojórquez Ricardo David
●
Pilas estáticas 
Introducción
Tipo de dato abstracto (TDA) que almacena elementos del mismo tipo. Los elementos
se almacenan de forma continua, es decir, sin ningún espacio entre ellos. Almacenar y
retirar elementos de la pila solo se puede hacer por un extremo de la estructura. El
comportamiento de este TDA se llama LIFO (“Last In First Out”), “El último en entrar es
el primero en salir”
Algunos de los métodos de la pila son:
Inicializa.
Esta operación asegura que la pila esté vacía en su estado inicial, dejándola lista para
operar sobre ella. Recibe la pila y no regresa nada.
Vacía.
Revisa el estado de la pila, si está vacía regresa verdadero, si existe algún elemento
dentro regresa falso.
1
Llena.
Revisa el estado de la pila, si está llena regresa verdadero, si el número de elementos
dentro es menor a la cantidad máxima regresa falso.
Empuja (push).
Coloca un nuevo elemento en el tope de la pila, ERROR si la pila está llena. Recibe el
elemento a empujar (insertar) y la pila en donde se hará, no regresa nada.
Quita (pop).
Elimina un elemento del tope de la lista, ERROR si la pila está vacía. Recibe la pila
donde se eliminará, no regresa nada.
Tope (top).
Obtiene y regresa el valor del tope de la pila. ERROR si la pila está vacía. No devuelve
nada.
2
Ejercicio 1.
Librerías incluidas.
Iniciamos incluyendo las librerías necesarias para el proyecto tal como se muestra en la
imagen.
3
Excepciones para la Pila.
El proyecto cuenta con un archivo dedicado a arrojar excepciones, es decir errores de
procesos realizados en la pila, por lo que sí nos marca un error que ya definimos, tal
como es la pila llena o vacía, el programa nos mandará un mensaje de error indicando
en donde estuvo la falla.
4
Declaración de Clase tipo Pila.
Se creó una clase de tipo de dato abstracto llamado pila, el cual nos servirá para la
conversión de una expresión infija a una posfija de forma correcta; por lo que se creó
con sus respectivos métodos que le permiten realizar las acciones que corresponden a
una pila; cabe mencionar que se implementó el uso de plantillas, para facilitar el trabajo
cuando se desee utilizar para distintos tipos de datos.
5
Declaración de Clase tipo Cola.
La cola es otro tipo de dato abstracto que nos ayudará a la conversión de notación infija
a posfija, por lo que se creó igualmente el objeto con sus respectivos métodos y
operaciones, igualmente utilizando plantillas.
Declaración de Clase Convert.
6
Esta clase se crea con la finalidad de realizar todo el proceso de conversión, por lo que
se incluye la cola y la pila, así como una cadena que almacenará la expresión en
notación infija, acompañada de sus métodos correspondientes para el proceso.
7
Implementación de Pila.
Constructor
Se encarga de crear el objeto, en este caso inicializando el atributo top en -1.
Constructor copia
Se activa cuando se desea copiar una pila a otra pila, incluyendo todos los datos con
los que se encuentra en ese momento, por lo que copia elemento por elemento de una
pila a otra, apoyado del método copyAll.
8
Método isEmpty
Únicamente retorna verdadero si la pila está vacía, es decir que no tiene datos, lo cual
se define que esta en este estado si top es igual a -1, y de igual forma retorna falso si
no lo esta.
9
Método isFull
Únicamente retorna verdadero si la pila se encuentra llena, es decir que ya contiene la
cantidad máxima de datos para la cuál fue creada, lo cual se define que esta en este
estado si top es igual al tamaño de la pila menos uno, y de igual forma retorna falso si
no lo esta.
10
Método push
Es el método encargado de insertar datos a la pila, para lo cual primero pregunta si
está llena con el método isFull, y en caso de ser positivo o verdadero, arroja un
mensaje que indica que excede la cantidad de datos permitidos; sin embargo, si
detecta falso, inserta el elemento que recibe, en la pila llamada data, en la posición que
sigue del valor de top, para así incrementar top en uno.
11
Este método notificará que no hay datos suficientes si se cumple el condicional if. En
caso de ser así, se llamará a la función ‘getTop’ y se retornará el último valor de la pila.
12
El método ‘convert’ empieza con un do-while, el cual se repetirá si la condición de que
aux sea igual a S.
Se le pedirá al usuario que ingrese una expresión infija para después pasarla a postfija.
Mientras que ‘myQueue’ esté vacía, se sacará a ‘myQueue’ de la cola.
13
El ciclo se ejecutará hasta que i sea menor que la longitud del infijo. Aplicando una
condición para invocar a un método que nos transforme nuestra notación a postfija si
es operando se pondrá en la pila y así siguiendo los pasos mediante los if else para
terminar nuestra expresión en otra notación y terminando con una sola cadena, así
terminando los pasos de conversión.
14
En esta parte del código realizamos las operaciones para realizar la conversión de tipo
de notación, al cambiar la prioridad de los operadores, primero tenemos a isOperator
que toma a los operadores que son los signos de +,-,/, etc, después tenemos al
método isOperand que toma a las letras o números, continuamos con un método para
el paréntesis que abre y después el último método para el paréntesis que cierra las
operaciones.
15
16
En el método ‘operatorHigher’, se ejecutará un switch. En caso de que se ingrese un
signo de más o menos, se igualará el valor de high a 1. En caso de que el dato
ingresado sea un asterisco o diagonal, el valor de high será de 2. En caso de una
potencia, high valdrá 3.
Sí op es igual a ^, el valor regresado será verdadero, después falso.
el método ‘hasHigherPrecedence’ tiene los parametros de tipo char ‘operator1’ y
operator2’.
Se declaran las variales de tipo entero high1 y high2 y se igualan a
operatorHigher(operator1) y operatorHigher(operator2) respectivamente.
Se abre un condicional si high1 y high2 valen lo mismo. En caso de ser así, se abré
otro condicional, para que isRightAssociative(high1) regrese falso. En caso contrario
regrese verdadero.
Capturas del Código Funcionando
17
Ejercicio 2.
Declaración de las librerías y de las Excepciones
Hacemos uso de las librerías string, cmath y exception las cuales nos ayudaran a
manejar de una manera adecuada las excepciones de insuficiencia de datos de nuestra
pila, además de que la librería string nos ayudará con el manejo de cadenas en nuestro
programa. Por último, pero no menos importante, el uso de la librería cstdlib nos
ayudará con el manejo de caracteres en el cambio de notación.
18
19
Declaración de la Pila con uso de Templates.
Hacemos uso de las templates debido a que facilitaran la declaración de pilas en un
futuro, crearemos una clase llamada Stack la cual contendrá los elementos privados
como lo es nuestro arreglo de datos y nuestro tope, este último elemento es el más
importante debido a que sin él, nuestro arreglo no sería una pila. Dentro de nuestra
clase tipo template contamos con algunos de los métodos públicos más relevantes que
definen a una pila como lo son push, pop y getTop.
Implementación de método copyAll.
Este método será el encargado de copiar todos los elementos de la pila a otra, esto con
ayuda de un bucle while que valide que mientras que nuestro auxiliar sea menor o igual
al último elemento de la pila que recibe como parámetro.
20
Implementación de los métodos Vacía y Llena.
El método vacía se encargará de revisar si nuestro elemento tope es igual a -1, es caso
de ser cierto retornara verdadero. Por otra parte, nuestro método Lleno será el
encargado de comprobar si nuestro tope es igual al tamaño máximo de nuestra pila, en
caso de ser cierto retornarael valor de 1.
21
Implementación del ToString
Este método es el encargado de imprimir nuestra cola de la manera correcta, esto
debido a que el programador no puede acceder de manera directa a los datos
almacenados dentro de la pila. Es por esto que con ayuda de un ciclo while se
imprimirá una cadena de tipo String la cual se concatenara hasta llegar al último
elemento y la retornara.
22
Implementación del método pushStack
Este método es el encargado de empujar los datos que el usuario desee ingresar a la
pila. En caso de que la pila se encuentre llena se mostrará un error de excepción el
cual dirá que se encontró un desbordamiento de datos al momento de ingresar más
datos a la pila. Al final se incrementará nuestro tope para respetar la continuidad de
datos.
23
Implementación del método pushStack
Este método es el encargado de desapilar el último elemento de nuestra pila, en caso
de que nuestra pila se encuentre vacía se desplegará un error de Insuficiencia de
datos. En caso de que la pila cuente con elementos entonces nuestro tope disminuirá
en -1.
Implementación del método getTop y sobrecarga de operadores.
El método getTop será el encargado de regresar el valor que se encuentra en el tope
de nuestra pila, en caso de que no se encuentre ningún valor en el tope, es decir que
nuestra pila está vacía, entonces se desplegará un error de Insuficiencia de datos en el
método getTop.
Nuestra sobrecarga de operadores nos permitirá modificar el comportamiento del
operador de igualación solo en objetos de tipo Stack, esto junto con la ayuda del
método copyAll nos permitirá igualar pilas en nuestro programa.
24
Implementación del método evaluateStack
Este método será el encargado de evaluar nuestra expresión, crearemos una pila que
nos será de ayuda para determinar la jerarquía y el orden de los operadores.
Con ayuda de un ciclo, verificaremos mediante un switch cada uno de los elementos de
nuestra expresión para determinar si es un operador o un operando.
En caso de que sea un operador de cualquier tipo (+, -, /, *) se les asignará
temporalmente ese valor a nuestras variables auxiliares y después se desapilaran,
posteriormente se apilara el resultado de la operación entre nuestros operandos a
nuestra pila Auxiliar. En caso de que se encuentre un espacio vacío se evaluará el
siguiente espacio.
Al final de nuestro método se retornará el valor Tope de nuestra pila Auxiliar la cual
contendrá el resultado de aplicar todas las operaciones necesarias.
Mostrar Menú
Esta función es la encargada de mostrar el menú y capturar la expresión que el usuario
desea evaluar, después que el usuario inserto la expresión que desea evaluar, es
25
cuando se llama al método evaluateStack el cual es el encargado de transformar la
expresión ingresada y después retornarla.
Capturas del Código Funcionando
26
Ejercicio 3.
En la parte principal del código incluimos las librerías, asignamos el tamaño de la
variable y utilizamos un comando para acortar partes del código(using namespace std)
esto puede ser opcional, pero nosotros si lo incluimos en el código.
27
En esta clase como atributo privado se declaró un string.
Por la parte de los métodos públicos, se declararon como explicit ‘PilaException’ con el
parámetro constante de tipo char y apuntador ‘message’.
28
29
Al igual que en los ejercicios anteriores, definimos la clase pila, agregamos sus
atributos privados ‘pila’ y ‘tope’ de tipo enteros.
Como métodos públicos se usaron ‘Pila’,’Pila’ con un parámetro constante y por
referencia, ‘vacía’ y ’llena’ de tipo booleano, ‘validarNumero’ de tipo entero, ‘push’ de
tipo vacío,’pop’ y getTope’ de tipo enteros.
30
En esta parte desarrollamos el método para poder eliminar los elementos repetidos,
creando un ciclo hasta que índice sea menor o igual a tope y buscando cada elemento
para después compararlo con sus demás datos de la pila para más tarde proceder a
eliminar los elementos repetidos de esta misma.
Tenemos 2 partes, la de vacía que nos ayuda cuando ya no tenemos elementos en la
pila, y también tenemos la llena que es lo contrario, nos marcaría cuando tenemos
datos de más, para cada uno de estos métodos tenemos una acción a realizar.
31
En esta parte es cuando ejecutamos las 2 opciones de arriba con la ayuda de un if,
llena nos ayuda a evitar el desbordamiento de datos además de hacer un push, y
vacía nos manda a insuficiencia de datos para después hacer un pop(Comandos de las
pilas) Para al salir de alguna de estas 2 opciones dependiendo el estado de la pila nos
moveremos hacia el resultado y nos retorna el dato. 
32
Aquí tenemos 2 métodos el primero es que si la pila está vacía lanzamos a la clase
PilaException para mandar un mensaje y retorna el tope de la pila. Después tenemos
el método de validar número el cual con base en una condición y un ciclo nos marca
que si vacía es diferente a lo que está dentro de la pila retorna 0 y avance a la
siguiente posición.
33
Dentro de la función principal main, declaramos dos variables de tipo entero, una
servirá para almacenar los números que el usuario ingresa para guardarlos dentro de la
pila resultante, y la otra servirá para cuando el programa le pregunte al usuario si
quiere volver a introducir otro número, y después se declararan dos objetos de la clase
pila, que llamaremos ‘a’ y ‘b’, la pila ‘a’ servirá como resultante y la ‘b’ como auxiliar
para almacenar datos repetidos. Luego, se le pedirá al usuario que le dé al programa
un número, por consiguiente, el número que ingrese el usuario se guardará en la
variable de número y pasará como parámetro para el método validarNumero, si este
método retorna 1, entonces el número ingresado se guarda en la pila resultante, pero si
detecta que es repetido, se guarda en la pila auxiliar, y finalmente el programa le
pregunta al usuario si quiere introducir otro número.
34
Una vez que el usuario elige ya no meter más números a la pila, entonces se
imprimirán las dos pilas, la pila a, que es la pila resultante de la operación, es decir, la
que no tiene números repetidos, y la pila b, que es la que tiene los números repetidos
ingresados por el usuario.
35
Capturas del Código Funcionando
36