Saltar al contenido

Paréntesis válidos

Lección 2 de 9 · 5 min

Paréntesis válidos

Paso 1 de 14

Cada paréntesis de apertura va a la pila. Uno de cierre debe responder al abierto más recientemente.

La idea

Haz push de cada símbolo de apertura. Cuando llega uno de cierre, debe coincidir con el del tope de la pila (stack), el abierto más recientemente. Cualquier otra cosa significa que el string (cadena) está roto. Una pasada, O(n), y una entrada válida termina con la pila vacía.

Ejemplo del mundo real

Un editor de código que revisa tu marcado mientras escribes. Cierra un </section> con un <div> todavía abierto y la línea se marca al instante, porque la etiqueta que cierras debe ser la última que abriste, no cualquiera que siga pendiente.

El código

Te toca

Ordena los pasos.

  1. Devuelve True solo si la pila terminó vacía
  2. Empieza con una pila vacía
  3. Haz push de cada símbolo de apertura en la pila
  4. Ante un símbolo de cierre, haz pop del tope y compara las parejas

Mini quiz

1 / 3

¿Qué te dice una pila vacía al final del recorrido?