Questo interprete di notazione (notazione polacca inversa) di notazione Python può essere reso più efficiente e preciso?

Question

Ecco un interprete di notazione postfix Python che utilizza uno stack per valutare le espressioni. È possibile rendere questa funzione più efficiente e accurata?

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

suggerimenti generali:

• Evita controlli di tipo non necessarie, e si basano sul comportamento dell'eccezione.
• has_key() è stato a lungo sconsigliato a favore dell'operatore in: utilizzare quello.
• Profile il tuo programma, prima di tentare qualsiasi ottimizzazione delle prestazioni. Per uno zero-sforzo profilatura run di qualsiasi codice, basta eseguire: python -m cProfile -s cumulative foo.py

punti specifici:

• listmakes a good stack fuori dalla scatola. In particolare, consente di utilizzare la notazione di segmento (tutorial) per sostituire lo pop/pop/append con un singolo passaggio.
• ARITHMETIC_OPERATORS può riferirsi direttamente alle implementazioni dell'operatore, senza il riferimento a getattr.

Mettendo insieme tutto questo:

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

Gli elenchi possono essere utilizzati direttamente come pile:

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

Si può anche mettere le funzioni operatore direttamente nelle ARITHMETIC_OPERATORS DICT:

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

poi

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

L'obiettivo del Se non è quello di rendere le cose più efficienti (anche se potrebbe avere quell'effetto) ma renderle più ovvie al lettore. Sbarazzarsi di livelli inutili di indirezione e involucri. Ciò tenderà a rendere il tuo codice meno offuscato. Fornirà anche (banali) miglioramenti nelle prestazioni, ma non credere che se non lo si misura.

Per inciso, l'uso di elenchi come stack equivale a common Python idiomatico.

Answer 3

È possibile mappare direttamente gli operatori: {"+": operator.add, "-": operator.sub, ...}. Questo è più semplice, non ha bisogno del non necessario getattr e consente anche l'aggiunta di ulteriori funzioni (senza hacking del modulo operatore). Si potrebbe anche cadere qualche variabili temporanee che vengono utilizzate solo una volta in ogni caso:

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

anche (meno di una performance e più di un problema di stile, anche soggettiva), mi sarebbe stata riordinata non faccio la gestione degli errori in tutto nel ciclo e avvolgerlo in un blocco try con un blocco except KeyError ("Operando sconosciuto"), un blocco (stack vuoto), ...

Ma preciso? Fornisce risultati errati?