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()
4

3 回答 3

10

一般建议：

  • 避免不必要的类型检查，并依赖默认的异常行为。
  • has_key()长期以来一直不赞成使用in操作员：改用它。
  • 在尝试任何性能优化之前分析您的程序。对于任何给定代码的零努力分析运行，只需运行：python -m cProfile -s cumulative foo.py

具体点：

  • list 开箱即用。特别是，它允许您使用切片表示法( tutorial ) 以单步替换pop// dance 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()
于 2010-10-05T18:18:17.337 回答
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 习惯用法。

于 2010-10-05T17:11:25.517 回答
2

您可以直接映射运算符：{"+": operator.add, "-": operator.sub, ...}. 这更简单，不需要不必要的getattr，还允许添加额外的功能（无需破解操作员模块）。您还可以删除一些无论如何只使用一次的临时变量：

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

此外（更少的性能和更多的风格问题，也是主观的），我可能不会在循环中进行错误处理，并将它包装在一个带有except KeyError块（“未知操作数”）的 try 块中，一个except IndexError块（空堆栈），...

但准确吗？它会给出错误的结果吗？

于 2010-10-05T17:27:17.363 回答