可以使此Python后缀表示法(反波兰表示法)解释器更高效，更准确吗? [英] Can this Python postfix notation (reverse polish notation) interpreter be made more efficient and accurate?

问题描述

这是一个Python后缀表示法解释器，该解释器利用堆栈来评估表达式.是否可以使此功能更高效，更准确?

Here is a Python postfix notation interpreter which utilizes a stack to evaluate the expressions. Is it possible to make this function more efficient and accurate?

#!/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运算符:改用它.
在尝试进行任何性能优化之前，先
• 配置文件您的程序.对于任何给定代码的零努力分析运行，只需运行:python -m cProfile -s cumulative foo.py

• Avoid unnecessary type checks, and rely on default exception behavior.
• has_key() has long been deprecated in favor of the in operator: use that instead.
• Profile your program, before attempting any performance optimization. For a zero-effort profiling run of any given code, just run: python -m cProfile -s cumulative foo.py

具体点:

• list 做成一个好的堆栈的盒子.特别是，它允许您使用切片符号((教程)用一个步骤替换pop/pop/append舞蹈.
• ARITHMETIC_OPERATORS可以直接引用操作员实现，而无需getattr间接访问.

• list makes a good stack out of the box. In particular, it allows you to use slice notation (tutorial) to replace the pop/pop/append dance with a single step.
• ARITHMETIC_OPERATORS can refer to operator implementations directly, without the getattr indirection.

将所有这些放在一起:

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后缀表示法(反波兰表示法)解释器更高效，更准确吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！