Может ли этот почтальон Python Postfix (обратный польский нотацию) быть сделан более эффективным и точным?

Question

Вот интерпретатор почты Python PostFix, который использует стек для оценки выражений. Можно ли сделать эту функцию более эффективной и точной?

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

Общие предложения:

• Избегайте ненужных проверок типа и полагайтесь на поведение исключения по умолчанию.
• has_key() давно устарел в пользу in Оператор: используйте это вместо этого.
• Профиль Ваша программа, прежде чем пытаться любую оптимизацию производительности. Для пробега профилирования нулевого усилия любой заданный код просто запустите: python -m cProfile -s cumulative foo.py

Конкретные точки:

• list делает хороший стек из коробки. В частности, это позволяет использовать вас нарезание (руководство) заменить pop/pop/append танцуй с одним шагом.
• ARITHMETIC_OPERATORS может обратиться к реализациям оператора напрямую, без getattr косвенность.

Положить все это вместе:

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

Списки могут быть использованы непосредственно как стеки:

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

Вы также можете поставить оператора функции непосредственно в ваши Ariithmetic_Operators Dict:

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

тогда

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

Целью этого является не для того, чтобы сделать все более эффективными (хотя это может иметь этот эффект), но сделать их более очевидными для читателя. Избавиться от ненужных уровней косвенности и обертков. Это будет иметь тенденцию сделать ваш код менее запутанным. Он также предоставит (тривиальные) улучшения в производительности, но не верь, что если вы не измеряете его.

Кстати, использование списков как стеки довольно общий идиоматический питон.

Answer 3

Вы можете напрямую карту операторов: {"+": operator.add, "-": operator.sub, ...}. Отказ Это проще, не нуждается в ненужном getattr А также позволяет добавлять дополнительные функции (без взлома модуля оператора). Вы также можете бросить несколько временных переменных, которые обычно используются только один раз:

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

Также (меньше производительности и большего количества стилей, также субъективного), я бы не проводил обрабатывать ошибку вообще в цикле и обернуть его в одном блоке except KeyError блок («неизвестный операнд»), except IndexError Блок (пустой стек), ...

Но точнее? Это дает неправильные результаты?