这个Python后缀表达式解释器能否更高效和准确？
这里有一个用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()
3 个回答
2
你可以直接把运算符映射成这样：{"+": operator.add, "-": operator.sub, ...}。这样做更简单，不需要用到多余的getattr，而且还可以添加其他功能（不用去改动运算符模块）。
rhs, lhs = stack.pop(), stack.pop()
stack.push(operators[val](lhs, rhs)).
另外（这更多是风格上的问题，不太影响性能，也比较主观），我可能会选择在循环中不做错误处理，而是把所有的错误处理放在一个try块里，配合except KeyError（处理“未知操作数”），except IndexError（处理空栈）等。
那么，这样做准确吗？会不会得出错误的结果呢？
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 中是相当常见的写法。
10
一些通用建议：
- 尽量避免不必要的类型检查，直接依赖默认的异常处理方式。
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()