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:
  1. Percorrer cada símbolo na expressão posfixa.
  2. Se o símbolo for um número, empilhe ele na pilha.
  3. 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.
  4. 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.

Exercícios relacionados