Escreva um programa em Python que leia uma expressão na notação Posfixa e realize sua avaliação.
Passo 1
Beleza, vamos resolver esse exercício juntos! A parada aqui é escrever um programa em Python que leia uma expressão na notação posfixa e a avalie. Isso se encaixa no conteúdo de estruturas de dados, mais especificamente usando uma pilha para ajudar na avaliação das expressões. Vamos precisar entender o que é notação posfixa e como usar uma pilha para resolver isso.
Passo 2
Primeiro, vamos entender o que é notação posfixa. Também conhecida como notação pós-fixada ou notação polonesa reversa, ela escreve os operadores depois dos operandos. Por exemplo, a expressão infixa tradicional
3 + 4
em posfixa fica 3 4 +
. Essa forma facilita a avaliação usando pilhas porque a ordem das operações fica clara.Passo 3
Agora, vamos falar sobre pilhas. Uma pilha é uma estrutura de dados que segue o princípio LIFO (Last In, First Out), ou seja, o último a entrar é o primeiro a sair. Em Python, podemos simular uma pilha usando uma lista. Vamos usar a pilha para armazenar os operandos conforme vamos lendo a expressão posfixa.
Passo 4
Vamos pensar no algoritmo para avaliar uma expressão posfixa:
- Percorrer cada símbolo na expressão posfixa.
- Se o símbolo for um número, empilhe ele na pilha.
- Se o símbolo for um operador (
+
,-
,*
,/
), desempilhe os dois últimos números da pilha, aplique o operador e empilhe o resultado de volta na pilha. - No final, o único número restante na pilha será o resultado da expressão.
Passo 5
Agora, vamos transformar esse algoritmo em código Python. Vamos definir uma função que recebe a expressão posfixa como uma string, separa os elementos e usa uma pilha para calcular o resultado.
def avaliar_posfixa(expressao):
pilha = []
operadores = {'+', '-', '*', '/'}
# Divide a expressão em tokens separados por espaço
tokens = expressao.split()
for token in tokens:
if token not in operadores:
# Se for um número, converte para float e empilha
pilha.append(float(token))
else:
# Se for um operador, desempilha dois operandos
if len(pilha) < 2:
return "Erro: Expressão inválida."
b = pilha.pop()
a = pilha.pop()
# Aplica o operador
if token == '+':
resultado = a + b
elif token == '-':
resultado = a - b
elif token == '*':
resultado = a * b
elif token == '/':
if b == 0:
return "Erro: Divisão por zero."
resultado = a / b
pilha.append(resultado)
if len(pilha) != 1:
return "Erro: Expressão inválida."
return pilha[0]
Passo 6
Vamos entender o que cada parte do código faz:
- Inicialização da pilha:
pilha = []
cria uma lista vazia que vamos usar como pilha. - Conjunto de operadores:
operadores = {'+', '-', '*', '/'}
define quais símbolos são considerados operadores. - Divisão da expressão:
tokens = expressao.split()
separa a expressão em partes, assumindo que os elementos estão separados por espaço. - Percorrendo os tokens: Para cada
token
na expressão:- Se não for um operador, converte para número e adiciona à pilha.
- Se for um operador, remove os dois últimos números da pilha, aplica o operador e coloca o resultado de volta na pilha.
- Verificações de erro: O código verifica se há operandos suficientes e garante que a expressão não termine com mais de um número na pilha.
- Retorno do resultado: Se tudo estiver certo, retorna o único elemento que ficou na pilha, que é o resultado da expressão.
Passo 7
Vamos testar nossa função com um exemplo. Suponha que a expressão posfixa seja
"3 4 + 2 * 7 /"
, que corresponde à expressão infixa ((3 + 4) * 2) / 7
.expressao = "3 4 + 2 * 7 /"
resultado = avaliar_posfixa(expressao)
print("Resultado:", resultado)
Saída esperada:
Resultado: 2.0
Resposta
Pronto! O programa completo para avaliar uma expressão na notação posfixa em Python fica assim:
def avaliar_posfixa(expressao):
pilha = []
operadores = {'+', '-', '*', '/'}
tokens = expressao.split()
for token in tokens:
if token not in operadores:
pilha.append(float(token))
else:
if len(pilha) < 2:
return "Erro: Expressão inválida."
b = pilha.pop()
a = pilha.pop()
if token == '+':
resultado = a + b
elif token == '-':
resultado = a - b
elif token == '*':
resultado = a * b
elif token == '/':
if b == 0:
return "Erro: Divisão por zero."
resultado = a / b
pilha.append(resultado)
if len(pilha) != 1:
return "Erro: Expressão inválida."
return pilha[0]
# Exemplo de uso
expressao = "3 4 + 2 * 7 /"
resultado = avaliar_posfixa(expressao)
print("Resultado:", resultado)
Quando você executar esse código com a expressão fornecida, a saída será:
Resultado: 2.0
Isso significa que a expressão posfixa
"3 4 + 2 * 7 /"
foi avaliada corretamente, resultando em 2.0
.