这个Python后缀表达式（逆波兰表达式）解释器能否被做得更高效和准确？

Question

这个Python后缀表达式（逆波兰表达式）解释器能否被做得更高效和准确？

7

这是一个使用栈来计算表达式的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()

- simeonwillbanks

3个回答

3

列表可以直接用作堆栈：

>>> 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中相当常见惯用语。

- nmichaels

很好的观点。用内置的list替换Stack抽象数据类型应该可以使postfix函数更快。在我的Mac上（OS X 10.5.8 / 2.6 GHz Intel Core 2 Duo / 4GB Mem），内置的堆栈运行时间为0.18秒或0.19秒。而使用Stack ADT则始终需要0.19秒。 - simeonwillbanks

2

您可以直接映射运算符：{"+": operator.add, "-": operator.sub, ...}。这样更简单，不需要不必要的getattr，还允许添加其他函数（而无需修改operator模块）。您还可以删除一些仅使用一次的临时变量。

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

此外（这是一个风格问题，而非性能问题，也很主观），我可能不会在循环中进行错误处理，而是将其包装在一个try块中，并使用except KeyError块（“未知操作数”），以及一个except IndexError块（空堆栈）……

但这样准确吗？它会产生错误的结果吗？

- user395760

同意错误处理的事情。Python异常不是C++异常。 - nmichaels

谢谢你的建议。所有的doctest都已通过，但它们可能不够全面。也许仍然存在着一个bug? - simeonwillbanks

2

stack.push(operators[val](stack.pop(), stack.pop()))存在缺陷，因为操作函数期望第一个输出操作数作为第二个参数。最初，我编写了这行代码：method(stack.pop(), stack.pop())，但是doctest失败了。 - simeonwillbanks

@simeon：抱歉，删掉.pop()，.pop()那个东西了 - 已经修复。 - user395760

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pi Delport · Accepted Answer

一般建议：

避免不必要的类型检查，并依赖于默认的异常行为。
has_key() 已经被废弃，应该使用 in 操作符: 代替它。
Profile 在进行任何性能优化之前，请对程序进行分析。对于任何给定代码的零努力分析运行，只需运行：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()