3 (2pt). Implemente uma função que utilize a estrutura de dados pilha para verificar se uma expressão comp por parênteses está bem formada, ou seja, se todos os parênteses abertos possuem um correspondente fechado na ordem correta.
Assuma que a estrutura de pilha já está corretamente implementada e disponível para uso. A função deve retornar 1 (verdadeiro)se a expressão estiver bem formada. Deve retornar 0 (falso) caso contrário. A expre de entrada s conterá apenas os caracteres ‘(’ e ‘)’.
Exemplos:
ver_parent("())"); // retorna 0 (falso) - fechamento sem abertura correspondente
ver_parent("
"); // retorna 1 (verdadeiro) - parênteses corretamente balanceados
ver_parent("())"); // retorna 0 (falso) - fechamento sem abertura correspondente
ver_parent("
Passo 1
O enunciado pede que você implemente uma função que verifique se uma expressão de parênteses está bem formada, usando uma pilha já disponível. Mais precisamente:
- Pergunta: implementar uma função que retorne
\ (verdadeiro) se a expressão estiver bem formada e \ (falso) caso contrário. - Informações dadas:
- A string de entrada (vou chamá‑la de
) conterá apenas os caracteres e . - A estrutura de pilha já está corretamente implementada e pode ser usada (ou seja, existem operações básicas como empilhar, desempilhar e testar se está vazia).
- A string de entrada (vou chamá‑la de
- Exemplo fornecido:
-
— deve retornar \ porque há um sem correspondente aberto. -
— deve retornar \ porque está balanceado.
-
Passo 2
Ideia geral e invariância (o que a pilha vai representar):
- Vamos usar a pilha para guardar cada parêntese aberto
que ainda não foi fechado. - Invariância importante: após processar os primeiros
caracteres de , o número de elementos na pilha é exatamente o número de parênteses abertos entre esses caracteres que ainda não encontraram um fechamento correspondente. - Estratégia simples:
- Percorrer
\ do início ao fim. - Para cada caractere:
- Se for
, empilhar. - Se for
, então: - Se a pilha estiver vazia, tem um fechamento sem abertura => retornar
\ imediatamente. - Caso contrário, desempilhar um
(isso corresponde ao pareamento).
- Se a pilha estiver vazia, tem um fechamento sem abertura => retornar
- Se for
- Ao final do percurso:
- Se a pilha estiver vazia, todos os abertos foram fechados => retornar
. - Se ainda houver elementos na pilha, há aberturas sem fechamento => retornar
.
- Se a pilha estiver vazia, todos os abertos foram fechados => retornar
- Percorrer
Passo 3
Explicando as operações da pilha (pra você saber o que chamar na implementação):
- stack_init(&st): inicializa uma pilha vazia (cria estrutura, ponteiros, etc.).
- stack_push(&st, x): coloca o elemento
no topo da pilha. - stack_pop(&st): remove o elemento do topo da pilha.
- stack_is_empty(&st): retorna verdadeiro se a pilha estiver vazia.
- stack_destroy(&st): libera recursos da pilha (boa prática chamar no fim).
Essas operações têm sentido imediato: empilhar um
significa “temos uma abertura esperando fechamento”; desempilhar quando aparece
significa “fechamos a abertura mais recente” (ordem LIFO).
Passo 4
Pseudocódigo detalhado linha a linha (vou explicar cada linha para você conseguir escrever sem erro durante a prova):
- Inicializar a pilha:
- Isso cria a pilha vazia. Em pseudocódigo: stack_init(&st).
- Fazer um loop que percorre cada caractere de
: - Para cada caractere
em : - Se
for : - Chamar stack_push(&st, ‘(’). Comentário: armazenamos uma abertura aguardando fechamento.
- Senao (então
é porque a entrada só tem esses dois tipos): - Se stack_is_empty(&st) for verdadeiro:
- Retornar
. Explicação: encontramos um fechamento sem abertura correspondente.
- Retornar
- Senao:
- Chamar stack_pop(&st). Comentário: fechamos a abertura mais recente.
- Se stack_is_empty(&st) for verdadeiro:
- Se
- Para cada caractere
- Depois do loop:
- Se stack_is_empty(&st) for verdadeiro: retornar
(tudo balanceado). - Senao: retornar
(restaram aberturas sem fechamento).
- Se stack_is_empty(&st) for verdadeiro: retornar
- Recomendo chamar stack_destroy(&st) antes de retornar para limpar memória (se a API exigir).
Passo 5
Complexidade e justificativa de corretude (para você lembrar na prova):
- Complexidade de tempo: cada caractere de
\ é processado uma vez e cada processamento faz no máximo uma operação de pilha (push ou pop). Logo, tempo , onde \ é o comprimento de . - Complexidade de espaço: no pior caso (string só com
), a pilha armazena \ elementos, então espaço extra . - Correção (intuição): a pilha garante que fechamentos correspondem à última abertura não fechada (LIFO), que é exatamente a regra para parênteses bem formados. Se algum fechamento não tem abertura correspondente, detectamos porque a pilha estará vazia no momento; se sobram aberturas, a pilha não estará vazia ao final.
Passo 6
Exemplos passo a passo (simulações) — isso ajuda você a memorizar o comportamento:
Exemplo 1:
- Estado inicial: pilha vazia.
- Processa primeiro caractere
: empilha => pilha tem 1 elemento. - Processa segundo caractere
: pilha não está vazia, desempilha => pilha volta a vazia. - Processa terceiro caractere
: pilha está vazia, mas encontramos => retorno imediato \ (falso). - Conclusão: retorna
\ (como esperado).
Exemplo 2:
- Estado inicial: pilha vazia.
- Processa
: empilha (tamanho 1). - Processa
: empilha (tamanho 2). - Processa
: desempilha (tamanho 1). - Processa
: desempilha (tamanho 0). - Fim da string: pilha vazia => retorna
\ (verdadeiro). - Conclusão: retorna
\ (como esperado).
Exemplo especial: string vazia
- Não entra no loop, pilha fica vazia => retorna
. Uma expressão sem parênteses é considerada bem formada.
Passo 7
Dicas rápidas pra prova (memorização e armadilhas):
- Cheque a pilha vazia sempre antes de desempilhar; esse é o erro clássico.
- Lembre que a ordem importa: sempre desempilhar o mais recente — por isso a pilha é a estrutura certa.
- Não precisa contar totais de aberturas e fechamentos separadamente — a pilha faz isso de forma ordenada pra você.
- Se a questão disser que a string pode conter outros caracteres, você ignoraria os que não são parênteses; aqui a entrada só tem
e .
Resposta
// Implementação em C supondo API de pilha já disponível:
// Funções supostas: stack_init(Stack *), stack_push(Stack *, char),
// stack_pop(Stack *), stack_is_empty(Stack *), stack_destroy(Stack *).
int ver_parent(const char *s) {
Stack st;
stack_init(&st);
for (const char *p = s; *p != '\0'; ++p) {
if (*p == '(') {
stack_push(&st, '(');
} else { // então *p == ')', pois entrada só tem '(' e ')'
if (stack_is_empty(&st)) {
stack_destroy(&st);
return 0; // fechamento sem abertura correspondente
}
stack_pop(&st);
}
}
int resultado = stack_is_empty(&st) ? 1 : 0;
stack_destroy(&st);
return resultado;
}