Escreva um programa que utilize uma pilha para verificar se expressões aritméticas estão com a parentização correta. O programa deve verificar expressões para ver se cada “abre parênteses” tem um “fecha parênteses” correspondente. Ex.:
Correto: ( ( ) ) - ( ( ) ( ) ) - ( ) ( )
Incorreto: ) ( - ( ) ( - ) ) ( (
Correto: ( ( ) ) - ( ( ) ( ) ) - ( ) ( )
Incorreto: ) ( - ( ) ( - ) ) ( (
Passo 1
Vamos criar um programa que use uma pilha para verificar se os parênteses de uma expressão estão balanceados.
Passo 2
Entendendo o problema: cada vez que vemos um “(” devemos armazená-lo na pilha e cada vez que vemos um “)” devemos desempilhar um “(” prévio. Se tentarmos desempilhar com a pilha vazia ou no fim ainda sobrar “(”s, a expressão está incorreta.
Passo 3
Implementando a pilha em Python: podemos usar uma lista e os métodos append() para empilhar e pop() para desempilhar.
Passo 4
Percorrendo a expressão: para cada caractere faça: se for “(”, empilhe; se for “)”, tente desempilhar e, se a pilha estiver vazia, marque erro.
No final da varredura, se a pilha estiver vazia, retorne True (balanceada); caso contrário, retorne False (desbalanceada).
No final da varredura, se a pilha estiver vazia, retorne True (balanceada); caso contrário, retorne False (desbalanceada).
Resposta
def esta_balanceada(expressao):
pilha = []
for ch in expressao:
if ch == ‘(’:
pilha.append(ch)
elif ch == ‘)’:
if not pilha:
return False
pilha.pop()
return len(pilha) == 0
pilha = []
for ch in expressao:
if ch == ‘(’:
pilha.append(ch)
elif ch == ‘)’:
if not pilha:
return False
pilha.pop()
return len(pilha) == 0
Exemplos de uso
expressoes = [’( ( ) )’, ‘( ( ) ( ) )’, ‘( ) ( )’, ‘) (’, ‘( ) ( - ) ) ( (’]
for expr in expressoes:
# remover espaços para focar só nos parênteses
expr_limpa = expr.replace(’ ', ‘’)
resultado = esta_balanceada(expr_limpa)
print(f"{expr} -> {‘Correto’ if resultado else ‘Incorreto’}")
for expr in expressoes:
# remover espaços para focar só nos parênteses
expr_limpa = expr.replace(’ ', ‘’)
resultado = esta_balanceada(expr_limpa)
print(f"{expr} -> {‘Correto’ if resultado else ‘Incorreto’}")