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

Question

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

#!/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 делает хороший стек из коробки.В частности, он позволяет использовать обозначение среза ( tutorial ), чтобы заменить танец 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]

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

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

затем

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

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

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

Answer 3

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

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

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

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