Escreva um programa para verificar se uma expressão matemática tem os parênteses agrupados de forma correta, isto é: (1) se o número de parênteses à esquerda e à direita são iguais e; (2) se todo parêntese aberto é seguido posteriormente por um fechamento de parêntese. ( Capítulo 2 do Livro Estrutura de Dados usando C).
Ex1: As expressões ((A+B) ou (A+B violam a condição 1

Passo 1

Beleza, vamos entender o que a questão está pedindo. Precisamos criar um programa que verifica se os parênteses em uma expressão matemática estão agrupados de forma correta. Isso significa duas coisas:
  1. Quantidade Igual: O número de parênteses abertos “(” deve ser igual ao de parênteses fechados “)”.
  2. Ordem Correta: Todo parêntese aberto deve ser fechado na ordem correta, ou seja, não pode fechar um parêntese que ainda não foi aberto.
Para resolver isso, vamos precisar entender um pouco sobre estruturas de dados, especificamente a pilha, que é muito útil para esse tipo de verificação.

Passo 2

Primeiro, vamos falar sobre a pilha. Imagine uma pilha de pratos: você adiciona pratos no topo e também remove do topo. Isso segue a regra LIFO (Last In, First Out), ou seja, o último que entra é o primeiro que sai. No nosso caso, vamos usar a pilha para acompanhar os parênteses.

Passo 3

A ideia é a seguinte:
  • Percorremos cada caractere da expressão.
  • Quando encontramos um parêntese aberto “(”, adicionamos ele na pilha.
  • Quando encontramos um parêntese fechado “)”, verificamos se há um parêntese aberto correspondente na pilha:
    • Se a pilha estiver vazia, significa que estamos tentando fechar um parêntese que nunca foi aberto, então a expressão está errada.
    • Se houver um parêntese aberto na pilha, removemos ele da pilha, indicando que esse parêntese foi fechado corretamente.

Passo 4

Após percorrer toda a expressão, fazemos uma última verificação:
  • Se a pilha estiver vazia, significa que todos os parênteses abertos foram fechados corretamente.
  • Se ainda houver parênteses na pilha, significa que faltou fechar alguns parênteses.

Passo 5

Vamos aplicar isso no exemplo dado: ((A+B).
  1. Primeiro caractere: ( → adiciona na pilha. Pilha: ["("]
  2. Segundo caractere: ( → adiciona na pilha. Pilha: ["(", "("]
  3. Terceiro caractere: A → não é parêntese, ignora.
  4. Quarto caractere: + → não é parêntese, ignora.
  5. Quinto caractere: B → não é parêntese, ignora.
  6. Sexto caractere: ) → verifica a pilha:
    • Há um “(” na pilha, então remove. Pilha: ["("]
Depois de percorrer toda a expressão, a pilha ainda tem um “(”, o que significa que há um parêntese aberto sem correspondência. Então, a expressão viola a condição 1 (quantidade igual de parênteses).

Resposta

A expressão ((A+B) viola a condição 1, pois o número de parênteses abertos e fechados não é igual.

Exercícios relacionados