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

具体的なポイント：

これらすべてをまとめると：

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_OPERATORSdictに直接配置することもできます。

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ブロック（「不明なオペランド」）、except IndexErrorブロックを含む1つのtryブロックでラップします。 （空のスタック）、..。

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

于 2010-10-05T17:27:17.363 に答える