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