Algorithmus zum Umwandeln von Ausdruck in Binärbaum

Question

Ich habe eine Aufgabe, in der ich eine Formel habe, sagen wir x+(y*z) und ich muss es in einen Binärbaum umwandeln. Ich habe online geschaut und ich habe Stichworte wie infix und postfix gesehen, und sie werden helfen, den regulären Ausdruck in ein Formular zu konvertieren, das weiter einfach in einen Binärbaum umgewandelt werden kann.

Mein einziges Problem ist, dass ich diese infix oder postfix Methode nie gelernt habe, gibt es also eine andere Möglichkeit, es zu konvertieren, oder ist das der einzige Weg? Ich habe es versucht, indem ich gesucht habe, aber das waren die einzigen Ergebnisse, die ich bekommen habe.

Es ist ein schweres Problem für mich zu lösen, ohne Online-Ressourcen zu verwenden.

Answer 1

Infix und Postfix sind keine Methoden an sich so viel wie Notationen oder Möglichkeiten, die gleiche Formel darzustellen. x+(y*z) ist bereits in Infix-Notation (weil die Operatoren in Seite die Gleichung sind). Die anderen zwei Notationen sind Präfix (oder polnische Schreibweise), wobei die Operatoren vor den Operanden sind (also x+(y*z) ist + x * y z) und postfix (oder umgekehrte polnische Notation), wo die Operatoren hinter den Operanden sind (also x+(y*z) ist y x * x +). Postfixnotation ist nützlich, da es einfach über einen Stack implementiert werden kann (so berechnen y x * x + Sie y und x auf den Stapel gelegt, dann sehen wir * die x und y vom Stapel erscheint und legt x*y zurück in den Stapel, dann setzen wir x in den Stapel und dann + wir sehen, die z*y und x vom Stapel erscheint und legt x+(z*y) auf den Stapel und Boom wieder Ihre Berechnung)

es

Sie von Infixschreibweise zu postfix besser umwandeln kann es über die Shunting-yard algorithm (Wikipedia erklärt als ich könnte)

Sie können also einfach eine Gleichung in Postfix-Notation über einen Binärbaum darstellen, da Sie die Gleichung durchlaufen, indem Sie einem Stapel Operanden als Blätter hinzufügen, und wenn Sie zu einem Operator gelangen, knacken Sie die ersten beiden Knoten aus dem Stapel und erstellen ein neuer Knoten mit dem Operator als Eltern und den Operanden, da es Kinder ist. Dann schieb diesen Baum zurück auf den Stapel. Wiederholen Sie dies, bis Sie das Ende der Gleichung erreicht haben.

Answer 2

Es gibt viele Parsing-Bibliotheken für diese Art von Arbeit.

Zum Beispiel mit pyparsing:

from pyparsing import * 

def rearrange(tks): 
    T=tks[0] 
    T[0],T[1] = T[1],T[0] 
    return tks 

expr = Forward() 
arithOp = Word("+-*/", max=1) 
terminal = (Word(alphas, alphanums) 
      | Word(nums) 
      | Suppress("(") + expr + Suppress(")")) 
expr << Group(terminal + arithOp + terminal).setParseAction(rearrange) 

parseTree = expr.parseString("x+(y*z)") 
print parseTree 

druckt:

[['+', 'x', ['*', 'y', 'z']]]