¿Se puede hacer que este intérprete de notación (notación polaca inversa) Python postfix sea más eficiente y preciso?

Question

Aquí hay un intérprete de notación de postfix de Python que utiliza una pila para evaluar las expresiones. ¿Es posible hacer que esta función sea más eficiente y precisa?

#!/usr/bin/env python 


import operator 
import doctest 


class Stack: 
    """A stack is a collection, meaning that it is a data structure that 
    contains multiple elements. 

    """ 

    def __init__(self): 
     """Initialize a new empty stack.""" 
     self.items = []  

    def push(self, item): 
     """Add a new item to the stack.""" 
     self.items.append(item) 

    def pop(self): 
     """Remove and return an item from the stack. The item 
     that is returned is always the last one that was added. 

     """ 
     return self.items.pop() 

    def is_empty(self): 
     """Check whether the stack is empty.""" 
     return (self.items == []) 


# Map supported arithmetic operators to their functions 
ARITHMETIC_OPERATORS = {"+":"add", "-":"sub", "*":"mul", "/":"div", 
         "%":"mod", "**":"pow", "//":"floordiv"} 


def postfix(expression, stack=Stack(), operators=ARITHMETIC_OPERATORS): 
    """Postfix is a mathematical notation wherein every operator follows all 
    of its operands. This function accepts a string as a postfix mathematical 
    notation and evaluates the expressions. 

    1. Starting at the beginning of the expression, get one term 
     (operator or operand) at a time. 
     * If the term is an operand, push it on the stack. 
     * If the term is an operator, pop two operands off the stack, 
     perform the operation on them, and push the result back on 
     the stack. 

    2. When you get to the end of the expression, there should be exactly 
     one operand left on the stack. That operand is the result. 

    See http://en.wikipedia.org/wiki/Reverse_Polish_notation 

    >>> expression = "1 2 +" 
    >>> postfix(expression) 
    3 
    >>> expression = "5 4 3 + *" 
    >>> postfix(expression) 
    35 
    >>> expression = "3 4 5 * -" 
    >>> postfix(expression) 
    -17 
    >>> expression = "5 1 2 + 4 * + 3 -" 
    >>> postfix(expression, Stack(), ARITHMETIC_OPERATORS) 
    14 

    """ 
    if not isinstance(expression, str): 
     return 
    for val in expression.split(" "): 
     if operators.has_key(val): 
      method = getattr(operator, operators.get(val)) 
      # The user has not input sufficient values in the expression 
      if len(stack.items) < 2: 
       return 
      first_out_one = stack.pop() 
      first_out_two = stack.pop() 
      operand = method(first_out_two, first_out_one) 
      stack.push(operand) 
     else: 
      # Type check and force int 
      try: 
       operand = int(val) 
       stack.push(operand) 
      except ValueError: 
       continue 
    return stack.pop() 


if __name__ == '__main__': 
    doctest.testmod() 

Answer 1

sugerencias generales:

• evitar controles de tipo innecesarios, y se basan en el comportamiento de excepción por defecto.
• has_key() ha quedado en desuso en favor del operador in: use eso en su lugar.
• Profile programa, antes de intentar cualquier optimización del rendimiento. Para un perfil de carrera cero esfuerzo de cualquier código dado, basta con ejecutar: python -m cProfile -s cumulative foo.py

puntos específicos:

• listmakes a good stack fuera de la caja. En particular, le permite usar la notación de división (tutorial) para reemplazar la danza pop/pop/append con un solo paso.
• ARITHMETIC_OPERATORS puede hacer referencia a las implementaciones del operador directamente, sin la direccionalidad getattr.

Juntando todo esto:

ARITHMETIC_OPERATORS = { 
    '+': operator.add, '-': operator.sub, 
    '*': operator.mul, '/': operator.div, '%': operator.mod, 
    '**': operator.pow, '//': operator.floordiv, 
} 

def postfix(expression, operators=ARITHMETIC_OPERATORS): 
    stack = [] 
    for val in expression.split(): 
     if val in operators: 
      f = operators[val] 
      stack[-2:] = [f(*stack[-2:])] 
     else: 
      stack.append(int(val)) 
    return stack.pop() 

Answer 2

Las listas pueden ser utilizados directamente como pilas:

>>> stack = [] 
>>> stack.append(3) # push 
>>> stack.append(2) 
>>> stack 
[3, 2] 
>>> stack.pop() # pop 
2 
>>> stack 
[3] 

También se puede poner las funciones de operador directamente en sus ARITHMETIC_OPERATORS dict:

ARITHMETIC_OPERATORS = {"+":operator.add, 
         "-":operator.sub, 
         "*":operator.mul, 
         "/":operator.div, 
         "%":operator.mod, 
         "**":operator.pow, 
         "//":operator.floordiv} 

continuación

if operators.has_key(val): 
    method = operators[val] 

El objetivo de no se trata de hacer las cosas más eficientes (aunque puede tener ese efecto) sino de hacerlas más obvias para el lector. Deshágase de niveles innecesarios de direccionamiento indirecto y envoltorios. Eso tenderá a hacer que su código esté menos ofuscado. También proporcionará mejoras (triviales) en el rendimiento, pero no lo crea a menos que lo mida.

Por cierto, el uso de listas como stacks es bastante common idiomático Python.

Answer 3

Puede mapear directamente los operadores: {"+": operator.add, "-": operator.sub, ...}. Esto es más simple, no necesita el innecesario getattr y también permite agregar funciones adicionales (sin hackear el módulo de operador). También podría caer algunas variables temporales que sólo se utilizan una vez de todos modos:

rhs, lhs = stack.pop(), stack.pop() 
stack.push(operators[val](lhs, rhs)).  

también (menos de un rendimiento y más una cuestión de estilo, también subjetiva), que sería además probablemente no hacer el manejo de errores en el todo en el ciclo y envolverlo en un bloque de prueba con un bloque except KeyError ("operando desconocido"), un bloque except IndexError (pila vacía), ...

¿Pero exacto? ¿Da resultados incorrectos?