Algoritmos e Estruturas de Dados

Stack (Pilha)

A stack (pilha) é uma das estruturas de dados mais populares em algoritmos. Numa stack, os elementos que entram por último são os primeiros a sair. Podemos compará-la a uma pilha de pratos, na qual só conseguimos remover o prato do topo. Para chegar aos pratos de baixo, temos de retirar todos os que estão acima.
Uma stack pode ser usada em muitas situações do dia a dia. Ao abrir sites num navegador, é possível clicar no botão “voltar” para regressar à página anterior. O histórico de páginas pode ser guardado numa stack, de modo que, quando carregamos em “voltar”, somos redirecionados para o elemento que está no topo. Se voltarmos a carregar em “voltar”, elimina-se a página do topo da stack e passamos para a página imediatamente abaixo.
notion image
Existem várias formas de implementar uma stack numa linguagem de programação como Python:
  1. Usar list – o elemento no topo será o último elemento da lista. Podemos adicionar com append, remover com pop e aceder ao elemento com [-1].
  1. Usar deque de collections – suporta adicionar e remover elementos tanto do início como do fim.
  1. LifoQueue de queue – fila do tipo “last in, first out”, que é essencialmente a definição de uma stack.
from queue import LifoQueue
stack = LifoQueue()

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

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

# ver topo
print(stack.queue[-1])  # imprime 1
print(stack.empty())    # verificar se está vazio -> imprime False
# Usando uma lista simples
stack = []

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

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

# ver topo
print(stack[-1])        # imprime 1
print(len(stack) == 0)  # verificar se está vazio -> imprime False

Desafio: Verificar se a sequência de parênteses é válida

Dada uma sequência de parênteses de uma expressão matemática (por exemplo, (()())), é necessário verificar se essa sequência é válida. Uma sequência de parênteses é considerada válida se cada parêntese de abertura tiver um correspondente de fecho e não houver parênteses extras ou em falta.

Entrada

A única linha da entrada contém uma linha b (1 ≤ |b| ≤ ) com a sequência de parênteses.

Saída

O programa deve imprimir Yes caso a sequência de parênteses seja válida, ou No caso contrário.

Exemplos

Entrada
Saída
()()
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