Kann ich eine Funktion schreiben, die symbolische Berechnungen in Python 2.7 durchführt?

Question

Ich wechsel gerade von Java zu Python und habe die Aufgabe übernommen, zu versuchen, einen Taschenrechner zu erstellen, der symbolische Operationen an Infix-notierten mathematischen Ausdrücken durchführen kann (ohne die Verwendung von benutzerdefinierten Modulen wie Sympy). Derzeit ist er so aufgebaut, dass er Zeichenketten akzeptiert, die durch Leerzeichen getrennt sind, und nur die (, ), +, -, *, und / Operatoren ausführen kann. Leider kann ich den grundlegenden Algorithmus zur Vereinfachung symbolischer Ausdrücke nicht herausfinden.

Zum Beispiel sollte mein Programm bei der Eingabe der Zeichenkette '2 * ( ( 9 / 6 ) + 6 * x )' die folgenden Schritte durchführen:

1. 2 * ( 1.5 + 6 * x )
2. 3 + 12 * x

Aber ich bekomme das Programm nicht dazu, das x zu ignorieren, wenn die 2 verteilt wird. Zusätzlich, wie kann ich 'x * 6 / x' behandeln, so dass es nach der Vereinfachung '6' zurückgibt?

EDIT: Zur Klärung, mit "symbolisch" meinte ich, dass es Buchstaben wie "A" und "f" im Ergebnis belassen wird, während die übrigen Berechnungen durchgeführt werden.

EDIT 2: Ich habe den Code (weitgehend) fertiggestellt. Ich poste ihn hier, falls jemand in Zukunft auf diesen Beitrag stößt, oder wenn einer von euch neugierig war.

    def reduceExpr(useArray):

        # Verwende das native eval() von Python zum Berechnen, wenn keine Buchstaben erkannt werden.
        if (not hasLetters(useArray)):
            return [calculate(useArray)] # Unterscheidet sich von eval(), da der String-Version des Ergebnisses zurückgibt

        # Basisfall. Gibt useArray zurück, wenn die Liste nur ein String enthält.
        if (len(useArray) == 1):
            return useArray

        # Basisfall. Gibt die mit Leerzeichen verbundenen Elemente von useArray als Liste mit einem String zurück.
        if (len(useArray) == 3):
            return [' '.join(useArray)]

        # Überprüft, ob Klammern im Ausdruck vorhanden sind und setzt.
        # Zählt die Anzahl der Klammern und behält die Position der ersten gefundenen ( bei.
        parentheses = 0
        leftIdx = -1

        # Dieser Try/Except-Block ist im Grunde ein If/Else-Block. Da useArray.index('(') einen KeyError auslöst,
        # wenn '(' in useArray nicht gefunden werden kann, wird die nächste Zeile nicht ausgeführt und das Klammerpaar wird nicht erhöht.
        try:
            leftIdx = useArray.index('(')
            parentheses += 1
        except Exception:
            pass

        # Wenn ein KeyError zurückgegeben wurde, ist leftIdx = -1 und rightIdx = parentheses = 0.
        rightIdx = leftIdx + 1

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

        # Wenn das Klammernpaar nicht leer ist, führt es den Inhalt erneut durch; sonst entfernt es die Klammern.
        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:])

        # Wenn der Operator + oder - ist, behalte die ersten beiden Elemente und verarbeite den Rest der Liste zuerst
        if isAddSub(useArray[1]):
            return reduceExpr(useArray[:2] + reduceExpr(useArray[2:]))
        # Andernfalls, wenn der Operator * oder / ist, verarbeite zuerst die ersten 3 Elemente, dann den Rest der Liste
        elif isMultDiv(useArray[1]):
            return reduceExpr(reduceExpr(useArray[:3]) + useArray[3:])
        # Habe dies nur eingefügt, damit der Compiler nicht beschwert, dass die Funktion kein Return hat (da sie von einer anderen Funktion aufgerufen wurde).
        return None

Answer 1

Sie benötigen viel mehr Verarbeitung, bevor Sie Operationen an Symbolen durchführen. Die Form, die Sie erreichen möchten, ist ein Baum von Operationen mit Werten in den Blattknoten. Zuerst müssen Sie einen Lexer-Durchlauf auf dem String durchführen, um Elemente zu erhalten - obwohl es möglicherweise ausreicht, den String einfach aufzuteilen, wenn Sie immer Leerzeichen-getrennte Elemente haben. Dann müssen Sie dieses Array von Tokens mit einer von Ihnen benötigten Grammatik analysieren.

Wenn Sie theoretische Informationen zu Grammatiken und Parsing-Text benötigen, starten Sie hier: http://en.wikipedia.org/wiki/Parsing Wenn Sie etwas Praktischeres brauchen, gehen Sie zu https://github.com/pyparsing/pyparsing (Sie müssen das pyparsing-Modul selbst nicht verwenden, aber deren Dokumentation enthält viele interessante Informationen) oder http://www.nltk.org/book

Von 2 * ( ( 9 / 6 ) + 6 * x ) müssen Sie zu einem Baum wie diesem gelangen:

      *
2           +
         /     *
        9 6   6 x

Dann können Sie jeden Knoten besuchen und entscheiden, ob Sie ihn vereinfachen möchten. Konstante Operationen werden die einfachsten sein, die eliminiert werden können - berechnen Sie einfach das Ergebnis und ersetzen Sie den "/"-Knoten durch 1.5, weil alle Kinder Konstanten sind.

Es gibt viele Strategien, um fortzufahren, aber im Wesentlichen müssen Sie einen Weg finden, durch den Baum zu gehen und ihn zu modifizieren, bis nichts mehr geändert werden muss.

Wenn Sie das Ergebnis dann ausdrucken möchten, gehen Sie einfach noch einmal durch den Baum und erstellen Sie einen Ausdruck, der es beschreibt.

Answer 2

Wenn Sie Ausdrücke in Python analysieren, sollten Sie die Python-Syntax für die Ausdrücke in Betracht ziehen und sie mithilfe des ast Moduls (AST = abstrakter Syntaxbaum) parsen.

Die Vorteile der Verwendung der Python-Syntax: Sie müssen keine separate Sprache für den Zweck erstellen, der Parser ist eingebaut, ebenso wie der Auswerter. Nachteile: Im Parsebaum gibt es ziemlich viel zusätzliche Komplexität, die Sie nicht benötigen (einige davon können vermieden werden, indem Sie die eingebauten Klassen NodeVisitor und NodeTransformer verwenden, um Ihre Arbeit zu erledigen).

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

Hier ist eine Beispielklasse, die einen Python-Parsebaum durchläuft und rekursive Konstantenfaltung durchführt (für binäre Operationen), um Ihnen zu zeigen, welche Art von Dingen Sie ziemlich einfach tun können.

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