Algoritmos y Estructuras de Datos

Pila (Stack)

La pila es una de las estructuras de datos más populares en algoritmos. Al usar pilas, los elementos que se añaden en último lugar son los primeros en ser removidos. Es como una pila de platos: solo puedes quitar el plato de arriba hasta que hayas sacado todos los que están sobre él.
Una pila puede emplearse en numerosas situaciones del mundo real. Por ejemplo, al abrir sitios web en un navegador, puedes hacer clic en el botón de retroceso para volver a la página anterior. El historial de páginas podría almacenarse en una pila, y al pulsar el botón de retroceso regresas a la parte superior de esa pila. Si lo presionas de nuevo, la página en la parte superior se elimina y pasas automáticamente a la que está justo debajo.
notion image
Existen varias maneras de implementar una pila en un lenguaje de programación como Python:
  1. Utilizando list - el elemento superior de la cola será el último elemento de la lista. Podemos añadir con append, quitar con pop y obtener el elemento con [-1].
  1. Utilizando deque de collections - ofrece la posibilidad de añadir y eliminar elementos tanto al inicio como al final.
  1. LifoQueue de queue - cola de tipo último en entrar, primero en salir, que en esencia define la estructura de una pila.
from queue import LifoQueue
stack = LifoQueue()

# insertar
stack.put(1)
stack.put(2)
stack.put(3)

# extraer
print(stack.get())      # imprime 3
print(stack.get())      # imprime 2

# ver tope
print(stack.queue[-1])  # imprime 1
print(stack.empty())    # comprobar si está vacía -> imprime False
# Usando una lista simple
stack = []

# insertar
stack.append(1)
stack.append(2)
stack.append(3)

# extraer
print(stack.pop())      # imprime 3
print(stack.pop())      # imprime 2

# ver tope
print(stack[-1])        # imprime 1
print(len(stack) == 0)  # comprobar si está vacía -> imprime False

Desafío: Comprobar si la secuencia de paréntesis es válida

Dada una secuencia de paréntesis de una expresión matemática (por ejemplo, (()())), se requiere determinar si es válida. Una secuencia de paréntesis es válida si cada paréntesis de apertura tiene su correspondiente paréntesis de cierre y no hay paréntesis adicionales de ningún tipo.

Entrada

La única línea de la entrada contiene una sola cadena b (1 ≤ |b| ≤ ) con la secuencia de paréntesis.

Salida

El programa debe imprimir Yes si la secuencia de paréntesis es válida y No en caso contrario.

Ejemplos

Entrada
Salida
()()
Yes
())()(
No
((()())())
Yes
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue