Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Notação postfix

0 votos
67 visitas
perguntada Set 21 em Programação Computacional por Arthur Quintão (1 ponto)  
editado Set 23 por Arthur Quintão

(GOODRICH, Michael T., TAMASSIA, Roberto e GOLDWASSER, Michael H. Data Structures & Algorithms in Python, página 252, exercício C-6.22)

A notação postfix é uma forma não ambígua de escrever expressões sem parênteses.
Ela é definida de tal forma que: se "(exp1)op(exp2)" é uma expressão comum, então a versão postfix será "pexp1 pexp2 op", onde pexp1 é a versão postfix de exp1 e pexp2 é a versão postfix de exp2.

Por exemplo:

Versão normal: ((5+2)(8-3))/4
Versão *postfix
: 5 2 + 8 3 - * 4 /

Descreva uma forma não recursiva de resolver uma expressão no formato postfix.

Compartilhe

1 Resposta

0 votos
respondida Set 21 por Arthur Quintão (1 ponto)  
editado Set 23 por Arthur Quintão

Uma possível solução para o problema proposto, consiste na iteração de uma lista, retirando e adicionando elementos, até que reste somente um elemento.

Primeiramente, defina uma classe que realizará a função de uma calculadora, ou seja, uma classe que receba 2 inteiros quaisquer mais um operador.

Essa classe auxiliará caso haja queira introduzir novos operadores a "calculadora", sendo necessário somente uma pequena alteração no código, especificamente adicionar o novo operador ao dicionário ops.

class Op:

    def __init__(self, param1, param2, fn):

        self.a=param1
        self.b=param2
        self.fn=ops[fn]

    def calc(self):
        return self.fn(self.a,self.b)

ops = {
    '*':  lambda a,b: [a*b] ,         # multiplicação
    '/':  lambda a,b: [a//b],         # divisão inteira
    '+':  lambda a,b: [a+b],          # adição
    '-':  lambda a,b: [a-b],          # subtração

}

Definida a calculadora, defina uma lista que receberá cada um dos elementos da expressão postfix, isto é, que receberá os inteiros e os operadores

def cal_postfix():
    "o comando split, como o próprio nome alude, divide a string em cada um"
    "de seus elementos formando uma lista"
    expr= input ("Insira a expressão,com 1 espaço entre os elementos ")
    tokens=expr.split(" ")

Por exemplo, para expressão " 5 2 +" o valor da variável tokens será a seguinte lista ["5","2","+"].

Definida a lista dos elementos da expressão, vamos iterar essa lista.

Basicamente, defini os 4 possíveis comportamentos dos 3 primeiros elementos da lista, tal que, para cada situação, os elementos da operação realizada serão retirados da lista e o resultado dessa operação seria introduzida ao final da lista.

As possíveis situações são:

1.Os 2 primeiros elementos da lista são numéricos e o terceiro é um operador:

  • Retira-se da lista: os 3 primeiros elementos (2 numéricos e 1 operador)
  • Adiciona-se ao final da lista: o resultado da operação

2.O primeiro elemento é um operador e o segundo é um numérico:

  • Retira-se da lista: Os último 2 elementos + 1º elemento (2 numéricos e 1 operador)
  • Adiciona-se ao final da lista: o resultado da operação

3.O primeiro elemento é um numérico e o segundo é um elemento:

  • Retira-se da lista: Os 2 primeiros elementos + último elemento da lista (2 numéricos e 1 operador)
  • Adiciona-se ao final da lista: o resultado da operação

4.Os 3 primeiros elementos são numéricos:

  • Retira-se da lista: o primeiro elemento
  • Adiciona-se ao final da lista: o primeiro elemento retirado

    while len(tokens)!=1:
    
        if tokens[0].isnumeric() and tokens[1].isnumeric() and\
        tokens[2].isnumeric():
            """Se os 3 primeiros elementos da expressão são numéricos"""
            """ Adiciona o primeiro elemento ao final da lista"""
            tokens.append(tokens[0])
           """Elimina o primeiro elemento da lista"""
            tokens=tokens[1:]
    
    
        if tokens[0].isnumeric() and tokens[1].isnumeric():
            """Se os 2 primeiros elementos da expressão são numéricos e o 3º é um operador"""
    
            """Realiza a respectiva operação"""
            stack=Op(int(tokens[0]),int(tokens[1]),tokens[2])
    
            """Update a expressão, eliminando os 3 primeiros elementos"""
    
            tokens=tokens[3:]
    
            """Update a expressão, adicionando o resultado do cálculo\
            na última posição"""
    
            tokens.append(str(stack.calc()[0]))
    
    
        elif tokens[1].isnumeric() and type(tokens[0])==str:
            """Se o primeiro elemento é um operador e o segundo é um numérico"""
    
            """Realiza a respectiva operação, entre o penúltimo e o último\
            elemento da expressão"""
    
            stack=Op(int(tokens[-2]),int(tokens[-1]),tokens[0])
    
            """Update a expressão, eliminando o primeiro, o penúltimo e o último elemento"""
    
            tokens=tokens[1:-2]
    
            """Update a expressão, adicionando o resultado do cálculo\
            na última posição"""
            tokens.append(str(stack.calc()[0]))
    
    
        elif tokens[0].isnumeric() and type(tokens[1])==str:
           """Se o primeiro elemento é um numérico e o segundo é um operador"""
    
           """Realiza a respectiva operação, entre o primeiro e o último\
            elemento da expressão"""
    
           stack=Op(int(tokens[-1]),int(tokens[0]),tokens[1])
    
           """Update a expressão, eliminando os 2 primeiros elementos e o último elemento"""
    
           tokens=tokens[2:-1]
    
           """Update a expressão, adicionando o resultado do cálculo\
            na última posição"""
           tokens.append(str(stack.calc()[0]))
    

Pensei em simplificar o código para reduzir um pouco as notações dos estamentos if, entretanto dessa forma acho que ficou mais claro a lógica aplicada.

Considerando a expressão do enunciado do exercício, o output do algoritmo será:
['5', '2', '+', '8', '3', '-', '+', '4', '/']
['8', '3', '-', '+', '4', '/', '7']
['+', '4', '/', '7', '5']
['4', '/', '12']
['3']
3

No stackoverflow existe uma resposta bem mais elaborada do que a essa, tanto que a ideia da calculadora foi retirada dessa resposta. Para quem se interessar: https://stackoverflow.com/questions/22579121/stack-calculator-postfix-python

Código completo:

class Op:

    def __init__(self, param1, param2, fn):

        self.a=param1
        self.b=param2
        self.fn=ops[fn]

    def calc(self):
        return self.fn(self.a,self.b)

ops = {
    '*':  lambda a,b: [a*b] ,         # multiplicação
    '/':  lambda a,b: [a//b],         # divisão inteira
    '+':  lambda a,b: [a+b],          # adição
    '-':  lambda a,b: [a-b],          # subtração
}


def cal_postfix():
    "o comando split, como o próprio nome alude, divide a string em cada um"
    "de seus elementos formando uma lista"
    expr= input ("Insira a expressão,com 1 espaço entre os elementos ")
    tokens=expr.split(" ")


    while len(tokens)!=1:


        if tokens[0].isnumeric() and tokens[1].isnumeric() and\
        tokens[2].isnumeric():
            """Se os 3 primeiros elementos da expressão são numéricos"""
            """ Adiciona o primeiro elemento ao final da lista"""
            tokens.append(tokens[0])
           """Elimina o primeiro elemento da lista"""
            tokens=tokens[1:]


        if tokens[0].isnumeric() and tokens[1].isnumeric():
            """Se os 2 primeiros elementos da expressão são numéricos e o 3º é um operador"""

            """Realiza a respectiva operação"""
            stack=Op(int(tokens[0]),int(tokens[1]),tokens[2])

            """Update a expressão, eliminando os 3 primeiros elementos"""

            tokens=tokens[3:]

            """Update a expressão, adicionando o resultado do cálculo\
            na última posição"""

            tokens.append(str(stack.calc()[0]))


        elif tokens[1].isnumeric() and type(tokens[0])==str:
            """Se o primeiro elemento é um operador e o segundo é um numérico"""

            """Realiza a respectiva operação, entre o penúltimo e o último\
            elemento da expressão"""

            stack=Op(int(tokens[-2]),int(tokens[-1]),tokens[0])

            """Update a expressão, eliminando o primeiro, o penúltimo e o último elemento"""

            tokens=tokens[1:-2]

            """Update a expressão, adicionando o resultado do cálculo\
            na última posição"""
            tokens.append(str(stack.calc()[0]))


        elif tokens[0].isnumeric() and type(tokens[1])==str:
           """Se o primeiro elemento é um numérico e o segundo é um operador"""

           """Realiza a respectiva operação, entre o primeiro e o último\
            elemento da expressão"""

           stack=Op(int(tokens[-1]),int(tokens[0]),tokens[1])

           """Update a expressão, eliminando os 2 primeiros elementos e o último elemento"""

           tokens=tokens[2:-1]

           """Update a expressão, adicionando o resultado do cálculo\
            na última posição"""
           tokens.append(str(stack.calc()[0]))


    return tokens[0]

 if __name__=="__main__":
       solution=cal_postfix()
       print(solution)
comentou Set 27 por Fabrícia (1 ponto)  
Saberia me responde isso? Escreva um programa em python que leia n números do teclado e armazene os em uma lista. Em seguida, o programa deve imprimir na tela o menor elemento da lista.
comentou Out 17 por Camilaspinto (11 pontos)  
Oi Arthur,
Sobre sua solução, gostei da ideia do dicionário com a possibilidade de acrescentar operações e achei interessante o fato de ter utilizado apenas uma lista para fazer o cálculo da expressão.

Eu não identifiquei situação em que cairá no primeiro if ("Se os 3 primeiros elementos da expressão são numéricos"), já que pela notação postfix e pelo seu programa, antes que ocorra três elementos numéricos juntos, uma operação é realizada e o resultado é enviado para o final da lista.

No primeiro elif ("Se o primeiro elemento é um operador e o segundo é um numérico"), entendo que não há necessidade de verificar se o segundo elemento é numérico (tokens[1].isnumeric()), tanto que esse elemento não influencia na atribuição do objeto stack.

Entendo que possa considerar os elementos como float, ao invés de inteiro.

Segue solução alternativa, considerando a utilização de duas listas, que pretendo aprimorar com algumas ideias que vi na sua solução:


def oper(a,b,oper):

    a=float(a)
    b=float(b)
    if oper=='+':
        r=a+b
    elif oper=='-':
        r=a-b
    elif oper=='*':
        r=a*b
    elif oper=='/':
        r=a/b
    return r


def calc_postfix():
    for j in exp:
        q1.append(j)
        print(q1, q2)
        if str.isnumeric(j):
            continue
        else:
            if len(q1)==3:
                a=q1.pop(0)
                b=q1.pop(0)
                op=q1.pop(0)
                z=oper(a,b,op)
                q2.append(z)
            elif len(q1)==2:
                a=q2.pop(0)
                b=q1.pop(0)
                op=q1.pop(0)
                x=oper(a,b,op)
                q2.append(x)
            else:
                a=q2.pop(0)
                b=q2.pop(0)
                op=q1.pop(0)
                x=oper(a,b,op)
                q2.append(x)

    resultado=q2[0]
    print(resultado)

if __name__=="__main__":
    
    exp = ['7', '5', '+', '2', '-', '7', '4', '/', '*', '10', '/']
    q1=[]
    q2=[]
    calc_postfix()
...