このPython Postfix表記（逆ポリッシュ表記）インタープリターをより効率的かつ正確にすることはできますか？

Question

これは、式を評価するためにスタックを使用するPython Postfix Notation Interpreterです。この機能をより効率的かつ正確にすることは可能ですか？

#!/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()

Answer 1

一般的な提案：

• 不必要なタイプチェックを避け、デフォルトの例外動作に依存します。
• has_key() 長い間支持されて廃止されてきました in オペレーター：代わりにそれを使用します。
• プロフィール パフォーマンスの最適化を試みる前のプログラム。特定のコードのゼロエフォルトプロファイリング実行の場合、実行するだけです。 python -m cProfile -s cumulative foo.py

具体的なポイント：

• list 良いスタックを作ります 箱から出して。特に、使用できます スライス表記 (チュートリアル）を交換します pop/pop/append 1つのステップで踊ります。
• 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()

Answer 2

リストは、スタックとして直接使用できます。

>>> stack = []
>>> stack.append(3) # push
>>> stack.append(2)
>>> stack
[3, 2]
>>> stack.pop() # pop
2
>>> stack
[3]

また、オペレーター機能をarithmetic_operators dictに直接配置することもできます。

ARITHMETIC_OPERATORS = {"+":operator.add,
                        "-":operator.sub,
                        "*":operator.mul,
                        "/":operator.div, 
                        "%":operator.mod,
                        "**":operator.pow,
                        "//":operator.floordiv}

それから

if operators.has_key(val):
    method = operators[val]

これらの目標は、物事をより効率的にすることではなく（その効果があるかもしれませんが）、読者にとってより明白にすることです。不必要なレベルの間接とラッパーを取り除きます。これにより、コードが難読化される傾向があります。また、パフォーマンスの（些細な）改善も提供しますが、測定しない限り、それを信じないでください。

ちなみに、リストをスタックとして使用することはかなりです 一般 慣用パイソン。

Answer 3

オペレーターを直接マップできます。 {"+": operator.add, "-": operator.sub, ...}. 。これはより簡単で、不必要なものは必要ありません getattr また、追加の機能を追加することもできます（オペレーターモジュールをハッキングせずに）。とにかく1回しか使用されていないいくつかの一時的な変数をドロップすることもできます。

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

また（パフォーマンスが少なく、スタイルの問題が発生し、主観的でもあります）、ループでエラー処理をまったく実行しないでください。 except KeyError block（ "不明なオペランド"）、an except IndexError ブロック（空のスタック）、...

しかし、正確ですか？それは間違った結果を与えますか？