Czy mogę napisać funkcję wykonującą obliczenia symboliczne w Pythonie 2.7?

Question

W tej chwili przechodzę z Java do Pythona i podjęłam się zadania stworzenia kalkulatora, który może wykonywać operacje symboliczne na wyrażeń matematycznych opatrzonych inffikacją (bez używania modułów niestandardowych, takich jak Sympy). Obecnie jest zbudowany, aby akceptować łańcuchy, które są rozdzielane spacjami i może wykonywać tylko operatory (,), +, -, * i /. Niestety, nie mogę znaleźć podstawowego algorytmu do uproszczenia wyrażeń symbolicznych.

Na przykład, biorąc pod uwagę ciąg '2 * ((9/6) + 6 * x)' my programu należy przeprowadzić następujące czynności:

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

Ale nie mogę uzyskać program do ignorowania x podczas rozprowadzania 2. Ponadto, w jaki sposób można obsłużyć 'x * 6/x' tak zwraca ' 6 'po uproszczeniu?

EDYCJA: Aby wyjaśnić, przez "symboliczne" miałem na myśli, że pozostawi litery takie jak "A" i "f" na wyjściu podczas wykonywania pozostałych obliczeń.

EDYCJA 2: I (w większości) zakończyłem kod. Zamieszczam go tutaj, jeśli ktoś natknie się na ten post w przyszłości, lub jeśli ktoś z was był ciekawy.

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

Potrzebujesz więcej przetwarzania, zanim przejdziesz do operacji na symbolach. Formularz, do którego chcesz się dostać, to drzewo operacji z wartościami w węzłach liścia. Najpierw musisz wykonać łańcuch leksykalny na łańcuchu, aby uzyskać elementy - chociaż jeśli zawsze masz elementy oddzielone spacjami, wystarczy podzielić tylko ciąg znaków. Następnie musisz przeanalizować tę tablicę żetonów, używając wymaganej gramatyki.

Jeśli potrzebujesz teoretyczne informacje na temat gramatyki i analizowania tekstu, zacznij tutaj: http://en.wikipedia.org/wiki/Parsing Jeśli potrzebujesz czegoś bardziej praktycznego, przejdź do http://pyparsing.wikispaces.com/Documentation (nie trzeba korzystać z modułu pyparsing sama, ale ich dokumentacja ma wiele ciekawy info) lub http://www.nltk.org/book

Od 2 * ((9/6) + 6 * x), trzeba dostać się do drzewa tak:

 * 
2   + 
     / * 
     9 6 6 x 

Następnie można odwiedzić każdy węzeł i zdecydować, czy chcesz ją uprościć. Stałe operacje będą najprostsze do wyeliminowania - wystarczy obliczyć wynik i zamienić węzeł "/" na 1,5, ponieważ wszystkie dzieci są stałymi.

Istnieje wiele strategii do kontynuowania, ale w zasadzie trzeba znaleźć sposób na przejście przez drzewo i modyfikowanie go, dopóki nie pozostanie nic do zmiany.

Jeśli chcesz wydrukować wynik, wystarczy ponownie przejść drzewo i utworzyć wyrażenie, które go opisuje.

Answer 2

Jeśli analizujesz wyrażenia w Pythonie, możesz rozważyć składnię Pythona dla wyrażeń i przeanalizować je za pomocą ast module (AST = abstrakcyjne drzewo składni).

Zalety stosowania składni języka Python: nie trzeba tworzyć osobnego języka do tego celu, wbudowany jest analizator składni, podobnie jak oceniający.Wady: w drzewie parsowania jest bardzo dużo złożoności, której nie potrzebujesz (możesz tego uniknąć, używając wbudowanych klas NodeVisitor i NodeTransformer do wykonania swojej pracy).

>>> 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())))" 

Oto przykład, że klasa spacery drzewo Python analizowania i robi rekurencyjną stały składane (dla operacji binarnych), aby pokazać coś takiego można zrobić dość łatwo.

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())))"