Peut cette notation postfix Python (notation polonaise inverse de) interprète doit être plus efficace et précis?

Question

Voici un interprète de notation postfix Python qui utilise une pile pour évaluer les expressions. Est-il possible de rendre cette fonction plus efficace et précis?

#!/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

Suggestions générales:

• Évitez les contrôles de type inutiles, et compter sur le comportement d'exception par défaut.
• has_key() a longtemps été dépréciée en faveur de l'opérateur in: utilisez-le.
• Profil votre programme, avant de tenter une optimisation des performances. Pour une course de tout code donné profilage zéro effort, il suffit d'exécuter: python -m cProfile -s cumulative foo.py

Points spécifiques:

• list href="http://docs.python.org/tutorial/datastructures.html#using-lists-as-stacks" rel="noreferrer"> fait une bonne pile de la boîte. En particulier, il vous permet d'utiliser tranche la notation ( tutoriel ) pour remplacer le pop / pop / append danser avec une seule étape.
• ARITHMETIC_OPERATORS peut se référer à des implémentations de l'opérateur directement, sans indirection getattr.

Mettre tout cela ensemble:

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

Les listes peuvent être utilisées directement comme des piles:

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

Vous pouvez aussi mettre les fonctions de l'opérateur directement dans votre ARITHMETIC_OPERATORS dict:

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

puis

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

Le but de ces derniers est de ne pas les choses rendre plus efficaces (bien qu'il puisse avoir cet effet), mais pour les rendre plus évident pour le lecteur. Débarrassez-vous des niveaux inutiles de indirection et emballages. Cela a tendance à rendre votre code moins brouillées. Il sera aussi (trivial) l'amélioration des performances, mais ne croyez pas que si vous mesurez.

Soit dit en passant, en utilisant des listes comme des piles est assez commune idiomatiques Python.

Answer 3

Vous pouvez mapper directement les opérateurs: {"+": operator.add, "-": operator.sub, ...}. Ceci est plus simple, n'a pas besoin de getattr inutile et permet également d'ajouter des fonctions supplémentaires (sans piratage du module opérateur). Vous pouvez également déposer quelques variables temporaires qui ne sont utilisés qu'une fois de toute façon:

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

De plus (moins d'une performance et plus d'une question de style, aussi subjective), je propably ne faire la gestion des erreurs du tout dans la boucle et l'envelopper dans un bloc d'essai avec un bloc except KeyError ( « opérande inconnu » ), un bloc de except IndexError (pile vide), ...

Mais précis? Est-il donner des résultats erronés?