Implementación de pilas con apuntadores en C

En este post muestro como implementar las funciones push y pop para el manejo de pilas, y dos problemas clásicos que se pide se solucionen utilizando pilas.

El siguiente archivo contiene la implementación de las funciones push y pop para ser utilizadas con caracteres

//Archivo pila_char.h
#include <stdio.h>
#include <stdlib.h>

typedef struct nodo_s
{
 char dato;
 struct nodo_s *siguiente;
} nodo_t;

typedef nodo_t *ptrNodo;
typedef nodo_t *ptrPila;

/*
    Agrega un nodo al inicio de la lista ligada
    *pila es el apuntador que apunta al primer nodo de la lista ligada (la cima de la pila)
*/
void push(ptrPila *pila, char x)
{
 // Crea un nuevo nodo
 ptrNodo nodo;
 nodo = (ptrNodo)malloc(sizeof(nodo_t));
 if (nodo != NULL)
    {
     nodo->dato = x;
     // El apuntador nodo->siguiente va a apuntar al primer nodo de la lista ligada
     nodo->siguiente = *pila;
     // pila va a apuntar al nuevo nodo, con esto hacemos que el nuevo nodo sea ahora el primer nodo de la lista ligada
     *pila=nodo;
    }
}

/*
    Elimina el primer nodo de la lista ligada
    *pila es el apuntador que apunta al primer nodo de la lista ligada (la cima de la pila)
*/
char pop(ptrPila *pila)
{
 // Crea un nuevo nodo
 ptrNodo nodo;
 char x;
 
 // El nuevo nodo va a apuntar al primer nodo de la lista ligada
 nodo = *pila;
 x = (*pila)->dato;
 // Ahora el segundo nodo de la lista ligada va a ser el primero
 *pila = (*pila)->siguiente;
 // Borra el primer nodo de la lista ligada
 free(nodo);
 // Regresa el valor que contenía el nodo que se eliminó
 return x;
}

/*
    Regresa 1 si no hay nodos en la lista ligada y cero en caso contrario
    *pila es el apuntador que apunta al primer nodo de la lista ligada (la cima de la pila)
*/
int pila_vacia(ptrPila *pila)
{
 return (*pila == NULL ? 1:0);
}

/*
   Muestra los datos de los nodos
*/ 
void nodos_pila(ptrNodo nodo)
{
 if (nodo == NULL)
     printf("La pila está vacia\n");
 else
     {
      while (nodo != NULL)
            {
             printf("%c\n",nodo->dato);
             nodo = nodo->siguiente;
            }
      printf("\n");
     }
}

El siguiente es un programa de ejemplo que permite analizar una cadena y determinar si los paréntesis o corchetes están balanceados, las funciones están hechas de tal forma que podemos agregar también llaves, etc. ya que sólo hay que indicar cuál es el caracter que abre y cuál es el caracter que cierra.

// Archivo pila_parentesis.c

#include <stdio.h>
#include "pila_char.h"

int verifica_balance(char expresion[], char cabre, char ccierra);

int main()
{
 char cadena[]="2*[x+q(3s-2)]/[((x+1)*x+(s-2))]";
 int i=0;
 
 // Muestra la cadena
 printf("La cadena a analizar es la siguiente:\n\n");
 while (cadena[i] != '\0')
       {
        printf("%c", cadena[i]);
        i++;
       }
 
 printf("\n\n");
 // Verifica si los paréntesis están balanceados
 if (verifica_balance(cadena, '(', ')') == 1)
     printf("Los paréntesis están balanceados\n");
 else
     printf("Los paréntesis NO están balanceados\n");
 
 // Verifica si los corchetes están balanceados
 if (verifica_balance(cadena, '[', ']') == 1)
     printf("Los corchetes están balanceados\n");
 else
     printf("Los corchetes NO están balanceados\n");
 
 return 0;
}

int verifica_balance(char expresion[], char cabre, char ccierra)
{
 int x=0, balanceados=1;
 ptrPila pila = NULL;
 
 // Recorre la cadena
 while (expresion[x] != '\0' && balanceados == 1)
       {
        // Si el elemento coincide con el caracter que abre, lo ingresa en la pila
        if (expresion[x]==cabre)
            push(&pila, expresion[x]);
        else
            // Si el elemento coincide con el caracter que cierra, lo saca de la pila
            if (expresion[x]==ccierra)
               {
                /* Si la pila está vacía, significa que los caracteres no están balanceados
                   porque se encontró un caracter que cierra sin que exista antes un caracter que abre
                */
                if (pila_vacia(&pila) != 1)
                    pop(&pila);
                else
                    balanceados = 0;
               }
        x++;
       }
 
 /* Si balanceados = 1 pero la pila no está vacía, los caracteres no están balanceados
    porque quedaron caracteres que abren sin tener su caracter que cierra
 */ 
 if (balanceados == 1 && pila_vacia(&pila) != 1)
     balanceados = 0;

 // Se asegura de dejar la pila vacia
 while (pila_vacia(&pila) != 1)
        pop(&pila);
 
 return balanceados; 
}

El siguiente archivo contiene la implementación de las funciones push y pop para ser utilizadas con enteros

// Archivo pila_int.h

#include <stdio.h>
#include <stdlib.h>

typedef struct nodo_s
{
 int dato;
 struct nodo_s *siguiente;
} nodo_t;

typedef nodo_t *ptrNodo;
typedef nodo_t *ptrPila;

/*
    Agrega un nodo al inicio de la lista ligada
    *pila es el apuntador que apunta al primer nodo de la lista ligada (la cima de la pila)
*/
void push(ptrPila *pila, int x)
{
 // Crea un nuevo nodo
 ptrNodo nodo;
 nodo = (ptrNodo)malloc(sizeof(nodo_t));
 if (nodo != NULL)
    {
     nodo->dato = x;
     // El apuntador nodo->siguiente va a apuntar al primer nodo de la lista ligada
     nodo->siguiente = *pila;
     // pila va a apuntar al nuevo nodo, con esto hacemos que el nuevo nodo sea ahora el primer nodo de la lista ligada
     *pila=nodo;
    }
}

/*
    Elimina el primer nodo de la lista ligada
    *pila es el apuntador que apunta al primer nodo de la lista ligada (la cima de la pila)
*/
int pop(ptrPila *pila)
{
 // Crea un nuevo nodo
 ptrNodo nodo;
 int x=0;
 
 // El nuevo nodo va a apuntar al primer nodo de la lista ligada
 nodo = *pila;
 x = (*pila)->dato;
 // Ahora el segundo nodo de la lista ligada va a ser el primero
 *pila = (*pila)->siguiente;
 // Borra el primer nodo de la lista ligada
 free(nodo);
 // Regresa el valor que contenía el nodo que se eliminó
 return x;
}

/*
    Regresa 1 si no hay nodos en la lista ligada y cero en caso contrario
    *pila es el apuntador que apunta al primer nodo de la lista ligada (la cima de la pila)
*/
int pila_vacia(ptrPila *pila)
{
 return (*pila == NULL ? 1:0);
}

void nodos_pila(ptrNodo nodo)
{
 if (nodo == NULL)
     printf("La pila está vacia\n");
 else
     {
      while (nodo != NULL)
            {
             printf("%d\n",nodo->dato);
             nodo = nodo->siguiente;
            }
      printf("\n");
     }
}

Como ejemplo, el clásico programa para hacer operaciones aritméticas en notación postfix

// Archivo pila_postfixexpr.c

#include <stdio.h>
#include "pila_int.h"

int main()
{
 char cadena[]="45+72-*5/";
 int i=0, num1=0, num2=0, result=0;
 ptrPila pila = NULL;
 
 // Muestra la cadena
 printf("La cadena a analizar es la siguiente:\n\n");
 while (cadena[i] != '\0')
       {
        printf("%c", cadena[i]);		
        i++;
       }
 
 i=0;
 printf("\n\n");
 // Recorre la cadena
 while (cadena[i] != '\0')
       {
        // Si el elemento no es un operador, lo ingresa en la pila
        if (cadena[i]!='+' && cadena[i]!='-' && cadena[i]!='*' && cadena[i]!='/')		   
            push(&pila, ((int)cadena[i])-48);   // El código ASCII de 0 es 48
        else
             {
              num2=pop(&pila);
              num1=pop(&pila);
              switch (cadena[i])
                     {
                      case '+':
                               result = num1+num2;
                               printf("suma %d + %d = %d\n",num1, num2, result);
                               push(&pila, result);
                               break;
                      case '-':
                               result = num1-num2;
                               printf("resta %d - %d = %d\n",num1, num2, result);
                               push(&pila, result);
                               break;
                      case '*':
                               result = num1*num2;
                               printf("multiplica %d * %d = %d\n",num1, num2, result);
                               push(&pila, result);
                               break;
                      case '/':
                               result = num1/num2;
                               printf("divide %d / %d = %d\n",num1, num2, result);
                               push(&pila, result);
                               break;
                     }			 
              }
        i++;
       }

 if (pila_vacia(&pila)!=1)
    {
     printf("\n\nLos elementos en la pila son los siguientes;\n\n");
     // Muestra los elementos que están en la pila
     nodos_pila(pila);
    }
 
 return 0;
}
About these ads

Etiquetas: , , , ,

4 comentarios to “Implementación de pilas con apuntadores en C”

  1. Berlin Says:

    Excelente post, muy util tu aportación, buscaré algunos problemas adicionales que puedan resolverse usando pilas dinámicas para mejorar mi doiminio de este topico.

  2. jiva Says:

    me podrias proporcionar thus libreris “Archivo pila_char.h”,
    “Archivo pila_parentesis.c “

    • rtmex Says:

      Claro, las puedes descargar directamente del post. Si pones el apuntador del mouse sobre el código, en la esquina superior derecha aparecen unos iconos, el segundo es para copiar el código al portapapeles, asi que si haces click en ese icono despues puedes pegar el código en cualquier editor de textos y guardarlo en tu computadora.

      Saludos

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

A %d blogueros les gusta esto: