Medio · pila

Paréntesis equilibrados

No necesitas una biblioteca para tener una pila: un array más un índice que solo toca el final ya lo es. Este problema es la razón clásica de ese truco: los paréntesis se cierran por el más reciente abierto, y eso es justo lo que guarda una pila.

En una fraseApila los que abren; al llegar a uno que cierra, comprueba que coincide con la cima y desapílalo. YES si nunca hay desajuste y la pila queda vacía; NO en cualquier otro caso.

El problema

Entrada: Una línea de 1000 caracteres como mucho, solo con ( ) [ ] { }.

Salida: YES si los paréntesis están equilibrados y bien anidados, NO en caso contrario.

Ejemplos:

EntradaSalida
([{}])YES
(]NO
(((NO

Equilibrado significa dos cosas a la vez: cada cierre encuentra su apertura (nunca desapilar una pila vacía) y cada apertura termina cerrándose (la pila acaba vacía). Fallar cualquiera de las dos es NO.

Tu solución

main.cpp — tu solución
Entrada personalizada para «Ejecutar mi entrada»

La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.

¿Atascado? Pistas

Pista 1 — El único que puede cerrar ahora es el más reciente

Recorre de izquierda a derecha. Cada vez que veas (, [ o {, apúntalo. Cada vez que veas un cierre, debe emparejar con la última apertura pendiente — cualquier otra cosa (como ([)]) está rota, venga lo que venga después. Recordar en orden inverso de llegada es justo lo que hace una pila.

Pista 2 — Tres modos de fallo, tres comprobaciones

Llega un cierre con la pila vacía → NO. Llega un cierre y la cima no es de su tipo → NO. La línea termina con algo en la pila (como ((() → NO. Solo si no ocurre ninguno de los tres escribes YES. Tener las tres comprobaciones claras antes de escribir es media solución.

Pista 3 — Escribe bien la prueba de emparejo

Una forma compacta: un cierre empareja con la cima cuando (open == '(' && c == ')') || (open == '[' && c == ']') || (open == '{' && c == '}'). Guardando solo aperturas — nunca cierres — la pila se mantiene trivial; si te sorprendes apilando cierres, para y replantéate el bucle.

Solución (¡inténtalo primero!) 
#include <iostream>
using namespace std;

int main() {
    char s[1005];
    cin.getline(s, 1005);
    char stack[1005];
    int top = 0;

    int i = 0;
    while (s[i] != '\0') {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            stack[top] = c;
            top++;
        } else if (c == ')' || c == ']' || c == '}') {
            if (top == 0) { cout << "NO" << endl; return 0; }
            char open = stack[top - 1];
            bool match = (open == '(' && c == ')') ||
                         (open == '[' && c == ']') ||
                         (open == '{' && c == '}');
            if (!match) { cout << "NO" << endl; return 0; }
            top--;
        }
        i++;
    }

    cout << (top == 0 ? "YES" : "NO") << endl;
    return 0;
}

Ya has usado el modismo del array como pila, y sirve para mucho más que paréntesis: el historial de deshacer, el DFS y la evaluación de expresiones viven en él. El patrón hermano con texto no necesita pila alguna — dos índices que caminan el uno hacia el otro —, que es justo cómo funciona Cadena palíndromo.

Análisis profundo

Por qué funciona

Los paréntesis se cierran en orden inverso al de apertura — el último abierto, el primero en cerrar — que es la definición de una pila (LIFO). Un array más un entero top ya es una pila completa: apilar es stack[top++] = c, desapilar es top--, mirar la cima es stack[top-1].

El coste

O(n) de tiempo para una línea de n caracteres — cada carácter se apila o desapila como mucho una vez — y O(n) de espacio en el peor caso (una línea de puras aperturas).

Dónde falla

  • Desapilar una pila vacía: un ] suelto llega a un cierre sin nada que emparejar. Comprueba top == 0 antes de tocar stack[top-1], o leerás basura por debajo del índice cero.
  • Olvidar la comprobación de sobrantes. ((( escribe YES si solo reaccionas a los cierres — la pila debe quedar vacía, así que la última línea necesita top == 0.

Siguiente paso

La otra forma de medir la simetría de una cadena no necesita pila: dos índices caminando el uno hacia el otro en Cadena palíndromo.

Dos cosas para recordar

  • Una pila es un array más un índice que solo toca el final.
  • Tres formas de fallar: desapilar vacía, tipo que no empareja, sobrantes al final.
🐞 Esta versión falla: ábrela y pruébala

Cuenta aperturas y cierres pero ignora el tipo: ([)] pasa

#include <iostream>
using namespace std;

int main() {
    char s[1005];
    cin.getline(s, 1005);
    int open = 0;
    int i = 0;
    while (s[i] != '\0') {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') open++;
        else if (s[i] == ')' || s[i] == ']' || s[i] == '}') open--;
        i++;
    }
    cout << (open == 0 ? "YES" : "NO") << endl;
    return 0;
}