Ejercicio resuelto: pila con vector y paréntesis equilibrados en C

La solución separa dos niveles: la pila, que no sabe nada de paréntesis, y la función equilibrada, que solo usa la interfaz de la pila. La pila es una estructura con un vector datos y un contador cima que indica cuántos elementos hay; el siguiente hueco libre es siempre datos[cima].

apilar y desapilar devuelven 1 si la operación se realizó y 0 si no se pudo, y desapilar entrega el carácter por un puntero de salida. Así el llamador puede reaccionar a los fallos sin que la pila escriba fuera de sus límites.

#include <stdio.h>
#include <string.h>

#define MAX_PILA 32
#define MAX_LINEA 256

typedef struct {
    char datos[MAX_PILA];
    int cima; /* numero de elementos almacenados */
} Pila;

static void pila_iniciar(Pila *p) {
    p->cima = 0;
}

static int pila_vacia(const Pila *p) {
    return p->cima == 0;
}

static int pila_llena(const Pila *p) {
    return p->cima == MAX_PILA;
}

static int apilar(Pila *p, char c) {
    if (pila_llena(p)) {
        return 0;
    }
    p->datos[p->cima] = c;
    p->cima++;
    return 1;
}

static int desapilar(Pila *p, char *c) {
    if (pila_vacia(p)) {
        return 0;
    }
    p->cima--;
    *c = p->datos[p->cima];
    return 1;
}

static char apertura_de(char cierre) {
    switch (cierre) {
    case ')': return '(';
    case ']': return '[';
    case '}': return '{';
    default:  return '\0';
    }
}

static int equilibrada(const char *formula) {
    Pila p;
    char c;
    char tope;
    pila_iniciar(&p);
    for (size_t i = 0; formula[i] != '\0'; i++) {
        c = formula[i];
        if (c == '(' || c == '[' || c == '{') {
            if (!apilar(&p, c)) {
                return 0; /* demasiadas aperturas abiertas a la vez */
            }
        } else if (c == ')' || c == ']' || c == '}') {
            if (!desapilar(&p, &tope)) {
                return 0; /* cierre sin apertura */
            }
            if (tope != apertura_de(c)) {
                return 0; /* tipos distintos */
            }
        }
    }
    return pila_vacia(&p);
}

int main(void) {
    char linea[MAX_LINEA];
    int n;

    if (fgets(linea, sizeof linea, stdin) == NULL) {
        return 0;
    }
    if (sscanf(linea, "%d", &n) != 1) {
        return 0;
    }
    for (int k = 1; k <= n; k++) {
        if (fgets(linea, sizeof linea, stdin) == NULL) {
            linea[0] = '\0';
        }
        linea[strcspn(linea, "\r\n")] = '\0';
        printf("%d: %s\n", k, equilibrada(linea) ? "SI" : "NO");
    }
    return 0;
}

La estructura Pila contiene datos[MAX_PILA] y cima. pila_iniciar pone cima a 0. pila_vacia y pila_llena son comparaciones simples, pero usarlas en lugar de repetir la condición evita errores de límites.

En apilar se comprueba primero pila_llena; solo si hay hueco se escribe en datos[cima] y se incrementa cima. En desapilar el orden se invierte: se comprueba pila_vacia, se decrementa cima y entonces se lee datos[cima], que es el último elemento guardado. Ese orden es la clave: si primero se leyera y luego se decrementara, se estaría leyendo el hueco libre.

En equilibrada se recorre la cadena con el índice i. Si el carácter c es una apertura, se apila, y si apilar devuelve 0 (pila llena) se responde 0 directamente. Si es un cierre, se desapila en tope; si no había nada, es un cierre sin apertura (caso )(), y si tope no coincide con apertura_de(c) los tipos se cruzan (caso ([)]). Cualquier otro carácter no hace nada. Al acabar, la fórmula es correcta solo si la pila está vacía, lo que detecta (().

En main se lee cada línea con fgets en un buffer de 256 bytes y se corta en el primer \r o \n con strcspn; por eso un final de línea de Windows no altera el resultado. La fórmula más larga permitida (200 caracteres) cabe de sobra. Sobre los tests: la fórmula de 33 aperturas seguidas devuelve NO por desbordamiento (en la apertura número 33 apilar devuelve 0), mientras que la de 32 aperturas y 32 cierres devuelve SI, porque llena la pila exactamente sin pasarse. La línea vacía devuelve SI porque no se apila nada y la pila acaba vacía, y con n = 0 el bucle no se ejecuta y no se imprime nada.