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;
}
Etiquetas: aoperaciones aritméticas en notación postfix con pilas en c, checar paréntesis balanceados, función pop en c, función push en c, pilas en c con apuntadores
Código Fuente 
julio 28, 2012 a las 6:56 am |
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.
julio 28, 2012 a las 10:01 am |
Que bien que te haya sido útil, saludos y gracias por tus comentarios
agosto 29, 2012 a las 8:14 am |
me podrias proporcionar thus libreris «Archivo pila_char.h»,
«Archivo pila_parentesis.c «
agosto 30, 2012 a las 8:23 am |
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
junio 6, 2015 a las 11:54 am |
en el de paréntesis balanceados si metes :
{ [ ( ] } )
sabiendo todos que no están bien ordenados te da el visto bueno.
junio 7, 2015 a las 9:26 am |
Así es Jhon, si analizas la función verifica_balance, recibe la cadena y el caracter que cierra y el que abre y el programa manda a llamar esa función con cada juego de caracteres que quieres checar (paréntesis, corchetes, llaves, etc.). Esto permite verificar únicamente que existan el mismo número de paréntesis que abren y cierran. Para verificar que el orden de los diferentes caracteres que abren y cierran sea correcto, habría que modificar la función para que en lugar de que reciba un caracter que abre y un caracter que cierra, recibiera una cadena con todos los posibles caracteres que abren y otra con todos los posibles caracteres que cierran y programar que al ir recorriendo la cadena, el próximo caracter que cierra sea del mismo tipo del último caracter que abre.
Con la función modificada de esa forma, el programa sólo tendría que mandar a llamar a la función una vez, y no una vez por cada tipo de caracter del cual se quiera verificar si están balanceados o no, como actualmente lo hace.
Saludos
octubre 26, 2016 a las 10:53 pm |
Necesito realizar una aplicación con pilas cual me recomendarías estaba pensado en una pila que tuviera estructuras almacenadas pero no se me ocurre algo chevere…
enero 6, 2017 a las 5:18 am |
Hola es posible implementar los paréntesis balanceados pero utilizando una cola?