Thông tin này có thể được thực hiện hiệu quả hơn và chính xác hơn không?

Question

Đây là một trình thông dịch ký hiệu Python postfix sử dụng một ngăn xếp để đánh giá các biểu thức. Có thể làm cho chức năng này hiệu quả hơn và chính xác hơn không?

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

gợi ý chung:

• Tránh kiểm tra kiểu không cần thiết, và dựa vào hành vi ngoại lệ mặc định.
• has_key() từ lâu đã bị từ chối vì lợi ích của toán tử in: sử dụng toán tử đó thay thế.
• Profile chương trình của bạn, trước khi thử bất kỳ tối ưu hóa hiệu suất nào. Đối với một số không nỗ lực profiling chạy của bất kỳ mã nào đó, chỉ cần chạy: python -m cProfile -s cumulative foo.py

điểm cụ thể:

• listmakes a good stack ra khỏi hộp. Cụ thể, nó cho phép bạn sử dụng ký hiệu slice (tutorial) để thay thế điệu nhảy pop/pop/append chỉ bằng một bước.
• ARITHMETIC_OPERATORS có thể tham khảo trực tiếp triển khai toán tử, không có số getattr.

Đưa tất cả điều này với nhau:

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

Chức năng có thể được sử dụng trực tiếp như ngăn xếp:

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

Bạn cũng có thể đặt các chức năng điều hành trực tiếp vào ARITHMETIC_OPERATORS bạn Dict:

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

sau đó

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

Mục tiêu của se không phải là để làm cho mọi thứ hiệu quả hơn (mặc dù nó có thể có hiệu ứng đó) nhưng để làm cho chúng rõ ràng hơn cho người đọc. Loại bỏ các mức độ không cần thiết của các trình bao bọc và hàm bao. Điều đó sẽ có xu hướng làm cho mã của bạn ít obfuscated. Nó cũng sẽ cung cấp các cải tiến (tầm thường) về hiệu suất, nhưng không tin rằng trừ khi bạn đo lường nó.

Ngẫu nhiên, việc sử dụng danh sách dưới dạng ngăn xếp khá là common Python độc đáo.

Answer 3

Bạn có thể trực tiếp lập bản đồ các toán tử: {"+": operator.add, "-": operator.sub, ...}. Điều này đơn giản hơn, không cần getattr không cần thiết và cũng cho phép thêm các chức năng bổ sung (không cần hack mô-đun vận hành). Bạn cũng có thể thả một vài biến tạm có thể chỉ sử dụng một lần anyway:

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

Ngoài ra (ít hơn của một buổi biểu diễn và nhiều hơn nữa của một vấn đề phong cách, cũng chủ quan), tôi sẽ propably không làm lỗi xử lý tại tất cả trong vòng lặp và quấn nó trong một khối thử với khối except KeyError ("Toán hạng không xác định"), một khối except IndexError (ngăn xếp trống), ...

Nhưng chính xác? Nó có cho kết quả sai không?