Tôi có thể viết một hàm thực hiện các phép tính biểu tượng trong Python 2.7 không?

Question

Tôi hiện đang chuyển từ Java sang Python và đã thực hiện nhiệm vụ cố gắng tạo một máy tính có thể thực hiện các hoạt động biểu tượng trên biểu thức toán học được mã hóa (mà không sử dụng các mô-đun tùy chỉnh như Sympy). Hiện tại, nó được xây dựng để chấp nhận các chuỗi được phân tách bằng dấu cách và chỉ có thể thực hiện toán tử (,), +, -, * và /. Thật không may, tôi không thể tìm ra thuật toán cơ bản để đơn giản hóa các biểu thức biểu tượng.

Ví dụ, với chuỗi '2 * ((9/6) + 6 * x)', chương trình của tôi nên thực hiện các bước sau:

1. 2 * (1,5 + 6 * x)
2. 3 + 12 * x

Nhưng tôi không thể có được những chương trình để bỏ qua x khi phân phối 2. Bên cạnh đó, làm thế nào tôi có thể xử lý 'x * 6/x' để nó trở về ' 6 'sau khi đơn giản hóa?

EDIT: Để làm rõ, bằng "tượng trưng" tôi có nghĩa là nó sẽ để lại các chữ cái như "A" và "f" ở đầu ra trong khi thực hiện các phép tính còn lại.

CHỈNH SỬA 2: Tôi (chủ yếu) đã hoàn tất mã. Tôi đăng nó ở đây nếu có ai vấp phải bài viết này trong tương lai, hoặc nếu có ai trong số các bạn tò mò.

def reduceExpr(useArray): 

     # Use Python's native eval() to compute if no letters are detected. 
     if (not hasLetters(useArray)): 
      return [calculate(useArray)] # Different from eval() because it returns string version of result 

     # Base case. Returns useArray if the list size is 1 (i.e., it contains one string). 
     if (len(useArray) == 1): 
      return useArray 

     # Base case. Returns the space-joined elements of useArray as a list with one string. 
     if (len(useArray) == 3): 
      return [' '.join(useArray)] 

     # Checks to see if parentheses are present in the expression & sets. 
     # Counts number of parentheses & keeps track of first (found. 
     parentheses = 0 
     leftIdx = -1 

     # This try/except block is essentially an if/else block. Since useArray.index('(') triggers a KeyError 
     # if it can't find '(' in useArray, the next line is not carried out, and parentheses is not incremented. 
     try: 
      leftIdx = useArray.index('(') 
      parentheses += 1 
     except Exception: 
      pass 

     # If a KeyError was returned, leftIdx = -1 and rightIdx = parentheses = 0. 
     rightIdx = leftIdx + 1 

     while (parentheses > 0): 
      if (useArray[rightIdx] == '('): 
       parentheses += 1 
      elif (useArray[rightIdx] == ')'): 
       parentheses -= 1 
      rightIdx += 1 

     # Provided parentheses pair isn't empty, runs contents through again; else, removes the parentheses 
     if (leftIdx > -1 and rightIdx - leftIdx > 2): 
      return reduceExpr(useArray[:leftIdx] + [' '.join(['(',reduceExpr(useArray[leftIdx+1:rightIdx-1])[0],')'])] + useArray[rightIdx:]) 
     elif (leftIdx > -1): 
      return reduceExpr(useArray[:leftIdx] + useArray[rightIdx:]) 

     # If operator is + or -, hold the first two elements and process the rest of the list first 
     if isAddSub(useArray[1]): 
      return reduceExpr(useArray[:2] + reduceExpr(useArray[2:])) 
     # Else, if operator is * or /, process the first 3 elements first, then the rest of the list 
     elif isMultDiv(useArray[1]): 
      return reduceExpr(reduceExpr(useArray[:3]) + useArray[3:]) 
     # Just placed this so the compiler wouldn't complain that the function had no return (since this was called by yet another function). 
     return None 

Answer 1

Bạn cần xử lý nhiều hơn trước khi bạn đi vào hoạt động trên biểu tượng. Biểu mẫu bạn muốn nhận là một cây hoạt động với các giá trị trong các nút lá. Trước tiên, bạn cần phải thực hiện một lệnh lexer trên chuỗi để lấy các phần tử - mặc dù nếu bạn luôn có các phần tử được phân tách bằng dấu cách, nó có thể đủ để chỉ tách chuỗi đó. Sau đó, bạn cần phải phân tích cú pháp mảng thẻ đó bằng cách sử dụng một số ngữ pháp mà bạn yêu cầu.

Nếu bạn cần thông tin lý thuyết về ngữ pháp và phân tích cú pháp văn bản, hãy bắt đầu tại đây: http://en.wikipedia.org/wiki/Parsing Nếu bạn cần một cái gì đó thiết thực hơn, hãy truy cập http://pyparsing.wikispaces.com/Documentation (bạn không phải sử dụng mô-đun pyparsing, nhưng tài liệu của họ có nhiều điều thú vị thông tin) hoặc http://www.nltk.org/book

Từ 2 * ((9/6) + 6 * x), bạn cần để có được một cây như thế này:

 * 
2   + 
     / * 
     9 6 6 x 

Sau đó, bạn có thể truy cập mỗi nút và quyết định xem bạn muốn đơn giản hóa nó. Các phép toán liên tục sẽ là những thao tác đơn giản nhất để loại bỏ - chỉ tính toán kết quả và trao đổi nút "/" với 1.5 vì tất cả các con đều là hằng số.

Có nhiều chiến lược để tiếp tục, nhưng về cơ bản bạn cần phải tìm cách đi qua cây và sửa đổi nó cho đến khi không còn gì để thay đổi.

Nếu bạn muốn in kết quả sau đó, chỉ cần đi lại trên cây một lần nữa và tạo ra một biểu thức mô tả nó.

Answer 2

Nếu bạn phân tích cú pháp các biểu thức bằng Python, bạn có thể xem xét cú pháp Python cho các biểu thức và phân tích chúng bằng cách sử dụng ast module (AST = cây cú pháp trừu tượng).

Ưu điểm của việc sử dụng cú pháp Python: bạn không phải tạo ngôn ngữ riêng cho mục đích, trình phân tích cú pháp được tích hợp và bộ đánh giá cũng vậy.Nhược điểm: có khá nhiều phức tạp hơn trong cây phân tích cú pháp mà bạn không cần (bạn có thể tránh một số của nó bằng cách sử dụng được xây dựng trong NodeVisitor và NodeTransformer lớp học để làm công việc của bạn).

>>> import ast 
>>> a = ast.parse('x**2 + x', mode='eval') 
>>> ast.dump(a) 
"Expression(body=BinOp(left=BinOp(left=Name(id='x', ctx=Load()), op=Pow(), 
right=Num(n=2)), op=Add(), right=Name(id='x', ctx=Load())))" 

Dưới đây là một lớp ví dụ đi trên cây phân tích Python và lặp lại liên tục đệ quy (đối với hoạt động nhị phân), cho bạn thấy loại điều bạn có thể làm khá dễ dàng.

from ast import * 

class FoldConstants(NodeTransformer): 
    def visit_BinOp(self, node): 
     self.generic_visit(node) 
     if isinstance(node.left, Num) and isinstance(node.right, Num): 
      expr = copy_location(Expression(node), node) 
      value = eval(compile(expr, '<string>', 'eval')) 
      return copy_location(Num(value), node) 
     else: 
      return node 

>>> ast.dump(FoldConstants().visit(ast.parse('3**2 - 5 + x', mode='eval'))) 
"Expression(body=BinOp(left=Num(n=4), op=Add(), right=Name(id='x', ctx=Load())))"