Archive for 21 octubre 2011

Implementación de pilas con apuntadores en C

octubre 21, 2011

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;
}
Anuncios