beecrowd 1068 · Pilha

Balanço de Parênteses I

Precisamos verificar se toda abertura possui um fechamento posterior e se nenhum fechamento aparece antes da abertura correspondente.

Enunciado Código .py

Entrada

Expressões lidas até o fim do arquivo.

Saída

correct ou incorrect para cada expressão.

Estrutura

Uma pilha contendo apenas aberturas ainda não fechadas.

O raciocínio

A pilha guarda pendências. Quando aparece (, surge uma nova abertura pendente. Quando aparece ), precisamos retirar a abertura mais recente.

Duas condições são necessárias: a pilha nunca pode estar vazia ao encontrar ) e precisa terminar vazia depois do último caractere.

Mapa da solução

Crie uma pilha vazia

Ela representa quantos parênteses de abertura ainda aguardam fechamento.

Faça push ao encontrar abertura

O append('(') registra uma nova pendência.

Faça pop ao encontrar fechamento

Se a pilha estiver vazia, a ordem já é inválida; caso contrário, o par é consumido.

Confira o estado final

Pilha vazia e nenhuma falha significam correct.

Execução interativa

Percurso da expressão

Velocidade

decisão

Expressão

caractere atual em vermelho

Pilha de aberturas

Estado da decisão

Caractere
Operação
Expressão

Quem entrou

Quem saiu

Quem permaneceu

Ligação com o código

A pilha memoriza as aberturas que ainda aguardam fechamento. A função pode responder False imediatamente quando encontra um fechamento antecipado; ao final, a pilha precisa estar vazia.

Os demais caracteres não entram na pilha. Eles fazem parte da expressão, mas não interferem no balanceamento.

Código completo comentado

import sys


def esta_balanceada(expressao):
    """Verifica se os parênteses abrem e fecham na ordem correta."""
    pilha = []

    for caractere in expressao:
        if caractere == "(":
            # Guarda uma abertura que ainda precisa ser fechada.
            pilha.append(caractere)
        elif caractere == ")":
            # Sem abertura disponível, este fechamento é inválido.
            if not pilha:
                return False
            pilha.pop()

    # Uma pilha vazia significa que nenhuma abertura ficou sobrando.
    return not pilha


# O beecrowd fornece uma expressão por linha até o fim do arquivo.
for linha in sys.stdin:
    expressao = linha.rstrip("\n")
    print("correct" if esta_balanceada(expressao) else "incorrect")

Complexidade

Cada caractere é examinado uma vez: tempo O(n). No pior caso, todos os caracteres relevantes são aberturas e permanecem empilhados: espaço O(n).