这个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 形成良好的堆栈 盒子外面。特别是，它允许您使用 切片表示法 (教程）来替换 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)).    

另外（执行的少，更多的是风格的问题，也是主观的），我会propably不做错误处理所有在环路并与except KeyError块（“未知操作”包装在一个try块），一个except IndexError块（空栈），...

但是，准确？它是否给错误的结果？