这是一个 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()
最佳答案
一般建议:
- 避免不必要的类型检查,并依赖默认的异常行为。
-
has_key()
长期以来一直不赞成使用in
运算符:请改用它。 - Profile你的程序,在尝试任何性能优化之前。对于任何给定代码的零努力分析运行,只需运行:
python -m cProfile -s cumulative foo.py
具体要点:
列表
makes a good stack盒子外面。特别是,它允许您使用切片符号 ( 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()
关于python - 这个 Python 后缀表示法(逆波兰表示法)解释器能否变得更高效和准确?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3865939/