Das deutsche Python-Forum

Hallo Python-Forum,

nach langer Zeit habe ich mich mal wieder Python (3) zugewendet und ein kleines Beispiel-Programm geschrieben, zum traversieren von Bäumen. Allerdings ist es mehr oder weniger nur eine Übersetzung, wie ich es auch in anderen Sprachen realisieren würde. Ich weiß also nicht ob es guter oder schlechter Python-Stil ist und suche Anregungen zur Verbesserung:

Code: Alles auswählen

#!/usr/bin/env python

class Node:
    def __init__(self, v, l, r):
        self.value  = v
        self.left   = l
        self.right  = r

    def traverse_prefix(self):
        out = '( '
        out += self.value + ' '
        if isinstance(self.left, Node):
            out += self.left.traverse_prefix() + ' '
        else:
            out += str(self.left) + ' '
        if isinstance(self.right, Node):
            out += self.right.traverse_prefix() + ' '
        else:
            out += str(self.right) + ' '
        out += ')'
        return out

    def traverse_postfix(self):
        out = ''
        if isinstance(self.left, Node):
            out += self.left.traverse_postfix() + ' '
        else:
            out += str(self.left) + ' '
        if isinstance(self.right, Node):
            out += self.right.traverse_postfix() + ' '
        else:
            out += str(self.right) + ' '
        out += self.value + ' '
        return out

    def traverse_infix(self):
        out = '( '
        if isinstance(self.left, Node):
            out += self.left.traverse_infix() + ' '
        else:
            out += str(self.left) + ' '
            
        out += self.value + ' '
        
        if isinstance(self.right, Node):
            out += self.right.traverse_infix() + ' '
        else:
            out += str(self.right) + ' '
        out += ')'
        return out
    
    def to_list(self, list = []):
        if isinstance(self.left, Node):
            list.append(self.left.to_list(list))
        else:
            list.append(self.left)
        if isinstance(self.right, Node):
            list.append(self.right.to_list(list))
        else:
            list.append(self.right)
        list.append(self.value)

class Stack:
    def __init__(self):
        self.items = []
        self.operator = {
            "*":    lambda x, y: self.items.append(x * y),
            "+":    lambda x, y: self.items.append(x + y),
            "/":    lambda x, y: self.items.append(x / y),
            "-":    lambda x, y: self.items.append(x - y),
            }
              
    def push(self, value):
        if isinstance(value, int) or isinstance(value, float):
            self.items.append(value)
        elif value in self.operator:
            y, x = self.items.pop(), self.items.pop()
            self.operator[value](x , y)
        else:
            pass
    
if __name__ == '__main__':
    tree = Node('/', Node('*', 2, Node('+', 4, 5)), 8)
    print(tree.traverse_prefix())
    print(tree.traverse_postfix())
    print(tree.traverse_infix())

    stack = Stack()
    items = []
    tree.to_list(items)
    for item in items:
        print("pushing " + str(item) + " on evaluating stack ...")
        stack.push(item)
        print("stack now looks like " + str(stack.items))
    print(str(stack.items))

"isistance" ist definitv kein guter Python-Stil.
Setzt die Nachfolger auf ``None``, wenn es keinen gibt.
Dann kannst du einfach auf Wahrheitswert überprüfen.

Code: Alles auswählen

self.left = None
self.right = Node(3, None, None)

if self.left:
  # child exist
else:
  # no child
if self.right:
  ...

Bei deinem Push kannst du mit einer Exception auf einen Zahlenwert überprüfen:

Code: Alles auswählen

try:
  int(value)
except ValueError:
  # guess operator
else:
  # numerical value

An der Stelle mit dem Funktionsaufruf aus dem Dict würde ich noch auf KeyError überprüfen.

BTW: Ist es bei der Implementierung von Bäumen nicht auch üblich, den Vorgänger/Parent zu speichern?

Edit: Noch was: NIEMALS mutable Datentypen als Default-Parameter, wenn man sich der Seiteneffekte nicht bewusst ist (bei Methode Node.to_list).

Hallo.

Dein Code ist ein wenig umständlich. Mal ehrlich: Wie viel hast du davon beim Schreiben zwischen den Methoden kopiert? Mal ein Vorschlag:

Code: Alles auswählen

class Node:
    def __init__(self, v, l, r):
        self.value  = v
        self.left   = l
        self.right  = r

    @staticmethod
    def traverse(element, output):
        try:
            return output.format(value=element.value,
                                 left=Node.traverse(element.left, output),
                                 right=Node.traverse(element.right, output))
        except AttributeError:
            return str(element)

    def traverse_prefix(self):
        return Node.traverse(self, "( {value} {left} {right} )")

    def traverse_postfix(self):
        return Node.traverse(self, "{left} {right} {value}")

    def traverse_infix(self):
        return Node.traverse(self, "( {left} {value} {right} )")

Noch ein paar weitere Tipps:

- Vermeide "isinstance", das widerspricht Python, bzw. dem verwendeten Duck-Typing. Es kommt nicht auf den Typ an, sondern auf die Schnittstelle. Fange also besser eine Exception ab, für den Fall, dass eine andere Schnittstelle als erwartet verwendet wird.

- Deine "to_list"-Methode habe ich jetzt nicht angepasst, daran kannst du dich selber mal versuchen. Eine mutable-Objekt als Default-Argument zu verwenden ist eine schlechte Idee. Dieses wird nämlich nur einmal zu Erzeugung der Funktion erstellt. Rufst du deine Funktion zweimal mit dem Standardparameter auf, wird beim zweiten Aufruf der veränderte Wert des ersten Aufrufst verwendet! Die Lösung ist die Übergabe von None, die Funktion erstellt dann ggf. eine Liste.
Auch solltest du Funktionen nicht so schreiben, dass diese Parameter verwenden. Rückgabewerte sind die Lösung!
Ach ja: "list" ist ein ganz schlechter Name, da du damit den buil-in Typ "list" verdeckst. Außerdem ist "list" ein sehr nichtssagender Bezeichner.

- "Stack" habe ich mir nicht weiter angeschaut, hier mal ein Vorschlag (ungetestet):

Code: Alles auswählen

import operator

OPERATOR = {
    "*": operator.mul,
    "+": operator.add,
    "/": operator.div,
    "-": operator.sub
}

class Stack(list):
    def push(self, value):
        try:
            function = OPERATOR[value]
            y, x = self.pop(), self.pop()
            value = function(x, y)
        except KeyError:
            pass

        self.items.append(value)

Allgemein hast du sehr viel doppelten Code drin, das solltest du dir abgewöhnen.

EyDu hat geschrieben: Ach ja: "list" ist ein ganz schlechter Name, da du damit den buil-in Typ "list" verdeckst. Außerdem ist "list" ein sehr nichtssagender Bezeichner.

Dass du bei format.format auch einen Built-in überschreibst, hätte dir auffallen müssen

Aber ansonsten wirklich guter Ansatz.

Edit: Ok, schon verbessert.

ice2k3 hat geschrieben:Dass du bei format.format auch einen Built-in überschreibst, hätte dir auffallen müssen

Das ist es mir auch schon.

@ice2k3: Ja, meist würde man einen Verweis auf die parent-Node berücksichtigen. Ich war mir nur unsicher, ob womöglich die GarbageCollection Probleme mit zirkulären Bezügen hat?!

@alle: Vielen herzlichen Dank für die Anregungen! Das hilft mir weiter ein wenig tiefer in die Sprache einzutauchen. Ich muss da wohl noch einiges lernen.

Den GC ignorierst du einfach mal, um den brauchst du dir noch keine Sorgen machen

Ich sehe hier aber auch keinen Vorteil die Eltern zu jeden Knoten zu Speichern. Das könnte man vielleicht in einer abgeleiteten Klasse machen.

EyDu hat geschrieben:

Code: Alles auswählen

    @staticmethod
    def traverse(element, output):
        try:
            return output.format(value=element.value,
                                 left=Node.traverse(element.left, output),
                                 right=Node.traverse(element.right, output))
        except AttributeError:
            return str(element)

Nachdem ich jetzt ein paar Stunden drüber geschlafen habe, habe ich eben schrittweise mit IDLE (tolles Werkzeug!) die obige Klassenmethode nachvollzogen. Das ist wirklich sehr elegant! Nochmal vielen Dank! :D

Hallo.

Bevor du es selber schmerzlich herausfindest: IDLE hat die ein oder andere Macke. Verwende daher besser den (interaktiven) Interpreter auf der Konsole.

Edit: Was ich gestern vergessen habe: Wenn du es noch allgemeiner haben willst, dann übergibst du an Stelle des Format-Strings eine Funktion.

Das deutsche Python-Forum

Bäume traversieren - Anregungen gesucht

Bäume traversieren - Anregungen gesucht