Programacion C++

CLASE-PILAS:

UNA PILA ES UN TIPO ESPECIAL DE LISTA ABIERTA EN LA QUE SÓLO SE PUEDEN INSERTAR Y ELIMINAR NODOS EN UNO DE LOS EXTREMOS DE LA LISTA. ESTAS OPERACIONES SE CONOCEN COMO "PUSH" Y "POP", RESPECTIVAMENTE "EMPUJAR" Y "TIRAR". ADEMÁS, LAS ESCRITURAS DE DATOS SIEMPRE SON INSERCIONES DE NODOS, Y LAS LECTURAS SIEMPRE ELIMINAN EL NODO LEÍDO.

UNA PILA (STACK EN INGLÉS) ES UNA LISTA ORDINAL O ESTRUCTURA DE DATOS EN LA QUE EL MODO DE ACCESO A SUS ELEMENTOS ES DE TIPO LIFO (DEL INGLÉS LAST IN FIRST OUT, ÚLTIMO EN ENTRAR, PRIMERO EN SALIR) QUE PERMITE ALMACENAR Y RECUPERAR DATOS. ESTA ESTRUCTURA SE APLICA EN MULTITUD DE OCASIONES EN EL ÁREA DE INFORMÁTICA DEBIDO A SU SIMPLICIDAD Y ORDENACIÓN IMPLÍCITA DE LA PROPIA ESTRUCTURA.

PARA EL MANEJO DE LOS DATOS SE CUENTA CON DOS OPERACIONES BÁSICAS: APILAR (PUSH), QUE COLOCA UN OBJETO EN LA PILA, Y SU OPERACIÓN INVERSA, RETIRAR (O DESAPILAR, POP), QUE RETIRA EL ÚLTIMO ELEMENTO APILADO.

EN CADA MOMENTO SÓLO SE TIENE ACCESO A LA PARTE SUPERIOR DE LA PILA, ES DECIR, AL ÚLTIMO OBJETO APILADO (DENOMINADO TOS, TOP OF STACK EN INGLÉS). LA OPERACIÓN RETIRAR PERMITE LA OBTENCIÓN DE ESTE ELEMENTO, QUE ES RETIRADO DE LA PILA PERMITIENDO EL ACCESO AL SIGUIENTE (APILADO CON ANTERIORIDAD), QUE PASA A SER EL NUEVO TOS.

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). DADA UNA PILA P, FORMADA POR LOS ELEMENTOS A, B, C, ..., K (P=(A,B,C,...,K)), SE DICE QUE A, QUE ES EL ELEMENTO MÁS INACCESIBLE DE LA PILA, ESTÁ EN EL FONDO DE LA PILA (BOTTOM) Y QUE K, POR EL CONTRARIO, EL MÁS ACCESIBLE, ESTÁ EN LA CIMA (TOP).

LAS RESTRICCIONES DEFINIDAS PARA LA PILA IMPLICAN QUE SI UNA SERIE DE ELEMENTOS A, B, C, D, E, F SE AÑADEN, EN ESTE ORDEN, A UNA PILA ENTONCES EL PRIMER ELEMENTO QUE SE ELIMINE (BORRE) DE LA ESTRUCTURA DEBERÁ SER E. POR TANTO, RESULTA QUE EL ÚLTIMO ELEMENTO QUE SE INSERTA EN UNA PILA ES EL PRIMERO QUE SE BORRA. POR ESA RAZÓN, SE DICE QUE UNA PILA ES UNA LISTA O ESTRUCTURA LINEAL DE TIPO LIFO (LAST IN FIRST OUT, EL ÚLTIMO QUE ENTRA ES EL PRIMERO QUE SALE).

ESTRUCTURA PILA:

A B C D E F ... ←BORRADO→INSERCIÓN

POR ANALOGÍA CON OBJETOS COTIDIANOS, UNA OPERACIÓN APILAR EQUIVALDRÍA A COLOCAR UN PLATO SOBRE UNA PILA DE PLATOS, Y UNA OPERACIÓN RETIRAR A RETIRARLO.

LAS PILAS SUELEN EMPLEARSE EN LOS SIGUIENTES CONTEXTOS:

• EVALUACIÓN DE EXPRESIONES EN NOTACIÓN POSTFIJA (NOTACIÓN POLACA INVERSA).

• RECONOCEDORES SINTÁCTICOS DE LENGUAJES INDEPENDIENTES DEL CONTEXTO

• IMPLEMENTACIÓN DE RECURSIVIDAD.

ESTAS CARACTERÍSTICAS IMPLICAN UN COMPORTAMIENTO DE LISTA LIFO (LAST IN FIRST OUT), EL ÚLTIMO EN ENTRAR ES EL PRIMERO EN SALIR.

EL SÍMIL DEL QUE DERIVA EL NOMBRE DE LA ESTRUCTURA ES UNA PILA DE PLATOS. SÓLO ES POSIBLE AÑADIR PLATOS EN LA PARTE SUPERIOR DE LA PILA, Y SÓLO PUEDEN TOMARSE DEL MISMO EXTREMO.

EL NODO TÍPICO PARA CONSTRUIR PILAS ES EL MISMO QUE VIMOS EN EL CAPÍTULO ANTERIOR PARA LA CONSTRUCCIÓN DE LISTAS:

struct nodo \{

int dato;

struct nodo *siguiente;

};

DECLARACIONES DE TIPOS PARA MANEJAR PILAS EN C:

LOS TIPOS QUE DEFINIREMOS NORMALMENTE PARA MANEJAR PILAS SERÁN CASI LOS MISMOS QUE PARA MANEJAR LISTAS, TAN SÓLO CAMBIAREMOS ALGUNOS NOMBRES:

typedef struct _nodo \{

int dato;

struct _nodo *siguiente;

} tipoNodo;

typedef tipoNodo *pNodo;

typedef tipoNodo *Pila;

TIPONODO ES EL TIPO PARA DECLARAR NODOS, EVIDENTEMENTE.

PNODO ES EL TIPO PARA DECLARAR PUNTEROS A UN NODO.

PILA ES EL TIPO PARA DECLARAR PILAS.

ES EVIDENTE, A LA VISTA DEL GRÁFICO, QUE UNA PILA ES UNA LISTA ABIERTA. ASÍ QUE SIGUE SIENDO MUY IMPORTANTE QUE NUESTRO PROGRAMA NUNCA PIERDA EL VALOR DEL PUNTERO AL PRIMER ELEMENTO, IGUAL QUE PASA CON LAS LISTAS ABIERTAS.

TENIENDO EN CUENTA QUE LAS INSERCIONES Y BORRADOS EN UNA PILA SE HACEN SIEMPRE EN UN EXTREMO, LO QUE CONSIDERAMOS COMO EL PRIMER ELEMENTO DE LA LISTA ES EN REALIDAD EL ÚLTIMO ELEMENTO DE LA PILA.

PILA COMO TIPO ABSTRACTO DE DATOS:

A MODO DE RESUMEN TIPO DE DATOS, LA PILA ES UN CONTENEDOR DE NODOS Y TIENE DOS OPERACIONES BÁSICAS: PUSH (O APILAR) Y POP (O DESAPILAR). 'PUSH' AÑADE UN NODO A LA PARTE SUPERIOR DE LA PILA, DEJANDO POR DEBAJO EL RESTO DE LOS NODOS. 'POP' ELIMINA Y DEVUELVE EL ACTUAL NODO SUPERIOR DE LA PILA. UNA METÁFORA QUE SE UTILIZA CON FRECUENCIA ES LA IDEA DE UNA PILA DE PLATOS EN UNA CAFETERÍA CON MUELLE DE PILA. EN ESA SERIE, SÓLO LA PRIMERA PLACA ES VISIBLE Y ACCESIBLE PARA EL USUARIO, TODAS LAS DEMÁS PLACAS PERMANECEN OCULTAS. COMO SE AÑADEN LAS NUEVAS PLACAS, CADA NUEVA PLACA SE CONVIERTE EN LA PARTE SUPERIOR DE LA PILA, ESCONDIDOS DEBAJO DE CADA PLATO, EMPUJANDO A LA PILA DE PLACAS. A MEDIDA QUE LA PLACA SUPERIOR SE ELIMINA DE LA PILA, LA SEGUNDA PLACA SE CONVIERTE EN LA PARTE SUPERIOR DE LA PILA. DOS PRINCIPIOS IMPORTANTES SON ILUSTRADOS POR ESTA METÁFORA: EN PRIMER LUGAR LA ÚLTIMA SALIDA ES UN PRINCIPIO, LA SEGUNDA ES QUE EL CONTENIDO DE LA PILA ESTÁ OCULTO. SÓLO LA PLACA DE LA PARTE SUPERIOR ES VISIBLE, POR LO QUE PARA VER LO QUE HAY EN LA TERCERA PLACA, EL PRIMER Y SEGUNDO PLATOS TENDRÁN QUE SER RETIRADOS.

OPERACIONES:

UNA PILA CUENTA CON 2 OPERACIONES IMPRESCINDIBLES: APILAR Y DESAPILAR, A LAS QUE EN LAS IMPLEMENTACIONES MODERNAS DE LAS PILAS SE SUELEN AÑADIR MÁS DE USO HABITUAL.

• CREAR: SE CREA LA PILA VACÍA. (CONSTRUCTOR)

• TAMAÑO: REGRESA EL NUMERO DE ELEMENTOS DE LA PILA. (SIZE)

• APILAR: SE AÑADE UN ELEMENTO A LA PILA.(PUSH)

• DESAPILAR: SE ELIMINA EL ELEMENTO FRONTAL DE LA PILA.(POP)

• CIMA: DEVUELVE EL ELEMENTO QUE ESTA EN LA CIMA DE LA PILA. (TOP O PEEK)

• VACÍA: DEVUELVE CIERTO SI LA PILA ESTÁ VACÍA O FALSO EN CASO CONTRARIO (EMPTY).

OPERACIÓN CREAR_PILA

LA CREACIÓN DE LA PILA SE REALIZARÁ MEDIANTE EL CONSTRUCTOR POR DEFECTO. LA TAREA QUE DEBERÁ REALIZAR SERÁ DECIR QUE NO EXISTEN ELEMENTOS EN LA PILA:

stack: Pila

stack.Cima ← 0

En C++:

Pila::Pila (void)

{

cima = 0;

}

OPERACIÓN PILA_VACIA:

• ESTA OPERACIÓN PERMITIRÁ DETERMINAR SI ES POSIBLE ELIMINAR ELEMENTOS.

• LA PILA ESTARÁ VACIA SI LA CIMA ESTÁ APUNTANDO AL VALOR CERO.

ALGORITMO PILA_VACIA

Entrada

stack: Pila

Salida

(CIERTO, FALSO)

Inicio

Si ( stack.Cima = 0 ) entonces

Devolver ( CIERTO )

Sino

Devolver ( FALSO )

Fin_si

Fin

bool Pila::PilaVacia (void)

{

return cima == 0;

}

OPERACIÓN DE INSERCIÓN DE INFORMACIÓN (APILAR):

LA OPERACIÓN DE INSERCIÓN NORMALMENTE SE CONOCE POR SU NOMBRE INGLÉS PUSH, O APILAR. LA OPERACIÓN APLICADA SOBRE UN PILA Y UN VALOR X, INSERTA X EN LA CIMA DE LA PILA. ESTA OPERACIÓN ESTÁ RESTRINGIDA POR EL TIPO DE REPRESENTACIÓN ESCOGIDO. EN ESTE CASO, LA UTILIZACIÓN DE UN ARRAY IMPLICA QUE SE TIENE UN NÚMERO MÁXIMO DE POSIBLES ELEMENTOS EN LA PILA, POR LO TANTO, ES NECESARIO COMPROBAR, PREVIAMENTE A LA INSERCIÓN, QUE REALMENTE HAY ESPACIO EN LA ESTRUCTURA PARA ALMACENAR UN NUEVO ELEMENTO. CON ESTA CONSIDERACIÓN, EL ALGORITMO DE INSERCIÓN SERÍA:

bool Pila::Apilar (Valor x)

{

bool error;

if (cima == MAX)

error = true;

else

{

error = false;

info[cima] = x;

cima++;

}

return error;

}

OPERACIÓN DE CONSULTA DE INFORMACIÓN (CIMA_PILA):

LA OPERACIÓN DE CONSULTA DE LA INFORMACIÓN, SÓLO PUEDE ACCEDER AL ELEMENTO QUE ESTÉ SITUADO EN LA CIMA DE LA PILA, Y PROPORCIONAR SU VALOR. EL ALGORITMO SE LIMITARÁ A DEVOLVER EL ELEMENTO QUE ESTÁ SITUADO EN LA POSICIÓN CIMA DE LA PILA, SI EXISTE INFORMACIÓN ALMACENADA EN LA PILA.

bool Pila::CimaPila (Valor & x)

{

bool error;

if (cima == 0)

error = true;

else

{

error = false;

x = info[cima - 1];

}

return error;

}

OPERACIÓN DE ELIMINACIÓN DE INFORMACIÓN (DESAPILAR):

LA OPERACIÓN DE BORRADO ELIMINA DE LA ESTRUCTURA EL ELEMENTO SITUADO EN LA CIMA. NORMALMENTERECIBE EL NOMBRE DE POP EN LA BIBLIOGRAFÍA INGLESA. EL ALGORITMO DE BORRADO SERÍA:

bool Pila::Desapilar (void)

{

bool error;

if (cima == 0)

error = true;

else

{

error = false;

cima--;

}

return error;

}

IMPLEMENTACIÓN:

UN REQUISITO TÍPICO DE ALMACENAMIENTO DE UNA PILA DE N ELEMENTOS ES O(N). EL REQUISITO TÍPICO DE TIEMPO DE O(1) LAS OPERACIONES TAMBIÉN SON FÁCILES DE SATISFACER CON UN ARRAY O CON LISTAS ENLAZADAS SIMPLES.

LA BIBLIOTECA DE PLANTILLAS DE C++ ESTÁNDAR PROPORCIONA UNA "PILA" CLASE TEMPLATED QUE SE LIMITA A SÓLO APILAR/DESAPILAR OPERACIONES. JAVA CONTIENE UNA BIBLIOTECA DE LA CLASE PILA QUE ES UNA ESPECIALIZACIÓN DE VECTOR. ESTO PODRÍA SER CONSIDERADO COMO UN DEFECTO, PORQUE EL DISEÑO HEREDADO GET () DE VECTOR MÉTODO LIFO IGNORA LA LIMITACIÓN DE LA PILA.

IMPLEMENTACIÓN MEDIANTE CURSORES:

IMPLEMENTACIÓN MEDIANTE ESTRUCTURAS DINÁMICAS

UNO DE LOS MAYORES PROBLEMAS EN LA UTILIZACIÓN DE ESTRUCTURAS ESTÁTICAS, ESTRIBA EN EL HECHO DE TENER QUE DETERMINAR, EN EL MOMENTO DE LA REALIZACIÓN DEL PROGRAMA, EL VALOR MÁXIMO DE ELEMENTOS QUE VA A PODER CONTENER LA ESTRUCTURA.

UNA POSIBLE SOLUCIÓN A ESTE PROBLEMA ES LA UTILIZACIÓN DE ESTRUCTURAS DINÁMICAS ENLAZADAS (UTILIZACIÓN DE PUNTEROS) TAL Y COMO SE EXPLICÓ EN EL PRIMER CUATRIMESTRE. POR TANTO, LA CLASE PILA CONTENDRÁ, EN ESTA IMPLEMENTACIÓN, LA SIGUIENTE PARTE PRIVADA:

class Pila

{

public: ...

private:

Puntero cima;

};

Donde Puntero será:

typedef struct Nodo * Puntero;

Y el tipo Nodo será:

struct Nodo

{

Valor info;

Puntero sig;

};

IMPLEMENTACIÓN EN PYTHON:

class Stack(object):

def __init__(self):

self.stack_pointer = None

def push(self, element):

self.stack_pointer = Node(element, self.stack_pointer)

def pop(self):

e = self.stack_pointer.element

self.stack_pointer = self.stack_pointer.next

return e

def peek(self):

return self.stack_pointer.element

def __len__(self):

i = 0

sp = self.stack_pointer

while sp:

i += 1

sp = sp.next

return i

class Node(object):

def __init__(self, element=None, next=None):

self.element = element

self.next = next

if __name__ == '__main__':

# small use example

s = Stack()

for i in range(10):s.push(i)

for i in range(len(s)):print(s.pop())

IMPLEMENTACIÓN EN MAUDE:

LA PILANV ES LA PILA NO VACÍA, QUE DIFERENCIAMOS DE LA PILA NORMAL A LA HORA DE TOMAR EN CUENTA ERRORES. EL ELEMENTO X REPRESENTA EL TIPO DE VALOR QUE PUEDE CONTENER LA PILA: ENTERO, CARÁCTER, REGISTRO, ETC.

fmod PILA-GENÉRICA {X :: TRIV} is

sorts Pila{X} PilaNV{X}.

subsorts PilaNV{X} < Pila{X}.

***generadores:

op crear: -> Pila {X} [ctor].

op apilar : X$Elt Pila{X} -> PilaNV{X} [ctor].

***constructores

op desapilar : Pila{X} -> Pila{X}.

***selectores

op cima : PilaNV{X} -> X$Elt.

***variables

var P : Pila{X}.

var E : X$Elt.

***ecuaciones

eq desapilar (crear) = crear.

eq desapilar(apilar(E, P)) = P.

eq cima(apilar(E, P)) = E.

endfm

IMPLEMENTACIÓN EN VISUAL BASIC:

Public Class Stack

Private p_index As Integer

Private list As New ArrayList

Public Sub New()

p_index = -1

End Sub

ReadOnly Property count

Get

Return list.Count

End Get

End Property

Public Sub push(ByVal value As Object)

list.Add(value)

p_index += 1

End Sub

Public Function pop() As Object

Dim obj As Object = list.Item(p_index)

list.RemoveAt(p_index)

p_index -= 1

Return obj

End Function

Public Sub clear()

list.Clear()

p_index = -1

End Sub

Public Function peek() As Object

Return list.Item(p_index)

End Function

End Class

EN C++:

#ifndef PILA

#define PILA // define la pila

template <class T>

class Pila {

private:

struct Nodo {

T elemento;

Nodo* siguiente; // coloca el nodo en la segunda posicion

}* ultimo;

unsigned int elementos;

public:

Pila() {

elementos = 0;

}

~Pila() {

while (elementos != 0) pop();

}

void push(const T& elem) {

Nodo* aux = new Nodo;

aux->elemento = elem;

aux->siguiente = ultimo;

ultimo = aux;

++elementos;

}

void pop() {

Nodo* aux = ultimo;

ultimo = ultimo->siguiente;

delete aux;

--elementos;

}

T cima() const {

return ultimo->elemento;

}

bool vacia() const {

return elementos == 0;

}

unsigned int altura() const {

return elementos;

}

};

#endif

ESTRUCTURAS DE DATOS RELACIONADAS:

EL TIPO BASE DE LA ESTRUCTURA FIFO (EL PRIMERO EN ENTRAR ES EL PRIMERO EN SALIR)ES LA COLA, Y LA COMBINACIÓN DE LAS OPERACIONES DE LA PILA Y LA COLA ES PROPORCIONADO POR EL DEQUE. POR EJEMPLO, EL CAMBIO DE UNA PILA EN UNA COLA EN UN ALGORITMO DE BÚSQUEDA PUEDE CAMBIAR EL ALGORITMO DE BÚSQUEDA EN PRIMERA PROFUNDIDAD (EN INGLÉS, DFS) POR UNA BÚSQUEDA EN AMPLITUD (EN INGLÉS, BFS). UNA PILA ACOTADA ES UNA PILA LIMITADA A UN TAMAÑO MÁXIMO IMPUESTO EN SU ESPECIFICACIÓN.

ARQUITECTURA BÁSICA DE UNA PILA:

UNA PILA TÍPICA ES UN ÁREA DE LA MEMORIA DE LOS COMPUTADORES CON UN ORIGEN FIJO Y UN TAMAÑO VARIABLE. AL PRINCIPIO, EL TAMAÑO DE LA PILA ES CERO. UN PUNTERO DE PILA, POR LO GENERAL EN FORMA DE UN REGISTRO DE HARDWARE, APUNTA A LA MÁS RECIENTE LOCALIZACIÓN EN LA PILA; CUANDO LA PILA TIENE UN TAMAÑO DE CERO, EL PUNTERO DE PILA DE PUNTOS EN EL ORIGEN DE LA PILA.

LAS DOS OPERACIONES APLICABLES A TODAS LAS PILAS SON:

• UNA OPERACIÓN APILAR, EN EL QUE UN ELEMENTO DE DATOS SE COLOCA EN EL LUGAR APUNTADO POR EL PUNTERO DE PILA, Y LA DIRECCIÓN EN EL PUNTERO DE PILA SE AJUSTA POR EL TAMAÑO DE LOS DATOS DE PARTIDA.

• UNA OPERACIÓN DESAPILAR: UN ELEMENTO DE DATOS EN LA UBICACIÓN ACTUAL APUNTADO POR EL PUNTERO DE PILA ES ELIMINADO, Y EL PUNTERO DE PILA SE AJUSTA POR EL TAMAÑO DE LOS DATOS DE PARTIDA.

HAY MUCHAS VARIACIONES EN EL PRINCIPIO BÁSICO DE LAS OPERACIONES DE PILA. CADA PILA TIENE UN LUGAR FIJO EN LA MEMORIA EN LA QUE COMIENZA. COMO LOS DATOS SE AÑADIRÁN A LA PILA, EL PUNTERO DE PILA ES DESPLAZADO PARA INDICAR EL ESTADO ACTUAL DE LA PILA, QUE SE EXPANDE LEJOS DEL ORIGEN (YA SEA HACIA ARRIBA O HACIA ABAJO, DEPENDIENDO DE LA APLICACIÓN CONCRETA).

POR EJEMPLO, UNA PILA PUEDE COMENZAR EN UNA POSICIÓN DE LA MEMORIA DE MIL, Y AMPLIAR POR DEBAJO DE LAS DIRECCIONES, EN CUYO CASO, LOS NUEVOS DATOS SE ALMACENAN EN LUGARES QUE VAN POR DEBAJO DE 1000, Y EL PUNTERO DE PILA SE DECREMENTA CADA VEZ QUE UN NUEVO ELEMENTO SE AGREGA. CUANDO UN TEMA ES ELIMINADO DE LA PILA, EL PUNTERO DE PILA SE INCREMENTA.

LOS PUNTEROS DE PILA PUEDEN APUNTAR AL ORIGEN DE UNA PILA O DE UN NÚMERO LIMITADO DE DIRECCIONES, YA SEA POR ENCIMA O POR DEBAJO DEL ORIGEN (DEPENDIENDO DE LA DIRECCIÓN EN QUE CRECE LA PILA), SIN EMBARGO EL PUNTERO DE PILA NO PUEDE CRUZAR EL ORIGEN DE LA PILA. EN OTRAS PALABRAS, SI EL ORIGEN DE LA PILA ESTÁ EN LA DIRECCIÓN 1000 Y LA PILA CRECE HACIA ABAJO (HACIA LAS DIRECCIONES 999, 998, Y ASÍ SUCESIVAMENTE), EL PUNTERO DE PILA NUNCA DEBE SER INCREMENTADO MÁS ALLÁ DE 1000 (PARA 1001, 1002, ETC.) SI UN DESAPILAR OPERACIÓN EN LA PILA HACE QUE EL PUNTERO DE PILA SE DEJE ATRÁS EL ORIGEN DE LA PILA, UNA PILA SE PRODUCE DESBORDAMIENTO. SI UNA OPERACIÓN DE APILAR HACE QUE EL PUNTERO DE PILA INCREMENTE O DECREMENTE MÁS ALLÁ DEL MÁXIMO DE LA PILA, EN UNA PILA SE PRODUCE DESBORDAMIENTO.

LA PILA ES VISUALIZADA YA SEA CRECIENTE DE ABAJO HACIA ARRIBA (COMO PILAS DEL MUNDO REAL), O, CON EL MÁXIMO ELEMENTO DE LA PILA EN UNA POSICIÓN FIJA, O CRECIENTE, DE IZQUIERDA A DERECHA, POR LO QUE EL MÁXIMO ELEMENTO SE CONVIERTE EN EL MÁXIMO A "LA DERECHA". ESTA VISUALIZACIÓN PUEDE SER INDEPENDIENTE DE LA ESTRUCTURA REAL DE LA PILA EN LA MEMORIA. ESTO SIGNIFICA QUE ROTAR A LA DERECHA ES MOVER EL PRIMER ELEMENTO A LA TERCERA POSICIÓN, LA SEGUNDA A LA PRIMERA Y LA TERCERA A LA SEGUNDA. AQUÍ HAY DOS EQUIVALENTES VISUALIZACIONES DE ESTE PROCESO:

Manzana Plátano

Plátano ==rotar a la derecha==> Fresa

Fresa Manzana

Plátano ==rotar a la izquierda==> Fresa

Manzana Plátano

UNA PILA ES NORMALMENTE REPRESENTADA EN LOS ORDENADORES POR UN BLOQUE DE CELDAS DE MEMORIA, CON LOS "DE ABAJO" EN UNA UBICACIÓN FIJA, Y EL PUNTERO DE PILA DE LA DIRECCIÓN ACTUAL DE LA "CIMA" DE CÉLULAS DE LA PILA. EN LA PARTE SUPERIOR E INFERIOR SE UTILIZA LA TERMINOLOGÍA CON INDEPENDENCIA DE QUE LA PILA CRECE REALMENTE A LA BAJA DE DIRECCIONES DE MEMORIA O DIRECCIONES DE MEMORIA HACIA MAYORES.

APILANDO UN ELEMENTO EN LA PILA,SE AJUSTA EL PUNTERO DE PILA POR EL TAMAÑO DE ELEMENTOS (YA SEA DECREMENTAR O INCREMENTAR, EN FUNCIÓN DE LA DIRECCIÓN EN QUE CRECE LA PILA EN LA MEMORIA), QUE APUNTA A LA PRÓXIMA CELDA, Y COPIA EL NUEVO ELEMENTO DE LA CIMA EN ÁREA DE LA PILA. DEPENDIENDO DE NUEVO SOBRE LA APLICACIÓN EXACTA, AL FINAL DE UNA OPERACIÓN DE APILAR, EL PUNTERO DE PILA PUEDE SEÑALAR A LA SIGUIENTE UBICACIÓN NO UTILIZADO EN LA PILA, O TAL VEZ APUNTE AL MÁXIMO ELEMENTO DE LA PILA. SI LA PILA APUNTA AL MÁXIMO ELEMENTO DE LA PILA, EL PUNTERO DE PILA SE ACTUALIZARÁ ANTES DE QUE UN NUEVO ELEMENTO SE APILE, SI EL PUNTERO QUE APUNTA A LA PRÓXIMA UBICACIÓN DISPONIBLE EN LA PILA, QUE SE ACTUALIZARÁ DESPUÉS DE QUE EL MÁXIMO ELEMENTO SE APILE EN LA PILA.

DESAPILANDO ES SIMPLEMENTE LA INVERSA DE APILAR. EL PRIMER ELEMENTO DE LA PILA ES ELIMINADO Y EL PUNTERO DE PILA SE ACTUALIZA, EN EL ORDEN OPUESTO DE LA UTILIZADA EN LA OPERACIÓN DE APILAR.

EXPRESIÓN DE EVALUACIÓN Y ANÁLISIS SINTÁCTICO:

SE CALCULA EMPLEANDO LA NOTACIÓN POLACA INVERSA UTILIZANDO UNA ESTRUCTURA DE PILA PARA LOS POSIBLES VALORES. LAS EXPRESIONES PUEDEN SER REPRESENTADAS EN PREFIJO, INFIJO, POSTFIJO. LA CONVERSIÓN DE UNA FORMA DE LA EXPRESIÓN A OTRA FORMA NECESITA DE UNA PILA. MUCHOS COMPILADORES UTILIZAN UNA PILA PARA ANALIZAR LA SINTAXIS DE LAS EXPRESIONES, BLOQUES DE PROGRAMA, ETC. ANTES DE TRADUCIR EL CÓDIGO DE BAJO NIVEL. LA MAYORÍA DE LOS LENGUAJES DE PROGRAMACIÓN SON DE CONTEXTO LIBRE DE LOS IDIOMAS QUE LES PERMITE SER ANALIZADOS CON MÁQUINAS BASADAS EN LA PILA.

POR EJEMPLO, EL CÁLCULO: ((1 + 2) * 4) + 3, PUEDE SER ANOTADO COMO EN NOTACIÓN POSTFIJA CON LA VENTAJA DE NO PREVALECER LAS NORMAS Y LOS PARÉNTESIS NECESARIO:

1 2 + 4 * 3 +

LA EXPRESIÓN ES EVALUADA DE IZQUIERDA A DERECHA UTILIZANDO UNA PILA:

• APILAR CUANDO SE ENFRENTAN A UN OPERANDO Y

• DESAFILAR DOS OPERANDOS Y EVALUAR EL VALOR CUANDO SE ENFRENTAN A UNA OPERACIÓN.

• APILAR EL RESULTADO.

DE LA SIGUIENTE MANERA (LA PILA SE MUESTRA DESPUÉS DE QUE LA OPERACIÓN SE HAYA LLEVADO A CABO):

ENTRADA OPERACIÓN PILA

1 Apilar operando 1

2 Apilar operando 1, 2

+ Añadir 3

4 Apilar operando 3, 4

* Multiplicar 12

3 Apilar operando 12, 3

ALGORITMO PARA EVALUAR EXPRESIONES:

INICIO

LEER LA EXPRESIÓN

MIENTRAS HAYA ELEMENTOS EN LA EXPRESIÓN HACER OBTENER EL SIGUIENTE ELEMENTO DE LA EXPRESIÓN.

SI(1) EL ELEMENTO ES UN IDENTIFICADOR DE OPERANDO ENTONCES

APILAR (ELEMENTO)

SINO(1) {* ES UN OPERADOR *}

OP ← NÚMERO DE OPERANDOS DEL OPERADOR

REPETIR OP VECES

DESAPILAR Y ALMACENAR

FIN_REPETIR

APLICAR EL OPERADOR SOBRE LOS OPERANDOS DESAPILADOS

APILAR (RESULTADO DE LA OPERACIÓN)

FIN_SI(1)

FIN_MIENTRAS

SI(2) PILA_VACIA ENTONCES

"ERROR. DEMASIADOS OPERADORES"

SINO(2)

SI(3) LA PILA TIENE MÁS DE UN VALOR APILADO ENTONCES

"ERROR. DEMASIADOS OPERANDOS"

SINO(3)

DEVOLVER ( DESAPILAR )

FIN_SI(3)

FIN_SI(2)

FIN

ESTE ALGORITMO PLASMADO EN CÓDIGO C++ SERÍA:

int Evaluar (Expresion exp)

{

Pila s;

int res;

Elemento token, e1_aux, e2_aux;

while (!exp.ExpresionVacia() )

{

token = exp.SigElemento ();

if (token.EsOperando() )

s.Apilar (token);

else

{

s.CimaPila (e1_aux);

s.Desapilar ();

s.CimaPila (e2_aux);

s.Desapilar ();

res = token.Operar (e1_aux, e2_aux);

s.Apilar (res);

}

if (s.PilaVacia () )

{

res = 0;

cerr << “Error: Demasiados operadores”;

}

else

{

s.CimaPila (res);

s.Desapilar ();

if (!s.PilaVacia() )

cerr << “Error: Demasiados operandos”;

}

return res;

}

{

s.CimaPila (e1_aux);

s.Desapilar ();

s.CimaPila (e2_aux);

s.Desapilar ();

res = token.Operar (e1_aux, e2_aux);

s.Apilar (res);

}

Programacion C++

jueves, 13 de diciembre de 2012

No hay comentarios:

Publicar un comentario