Informatiker Board | übergreifende Themen

Informatiker Board » Themengebiete » übergreifende Themen » Präfix und Postfix

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Präfix und Postfix

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Phoney
Jungspund

Dabei seit: 13.12.2006
Beiträge: 20

Präfix und Postfix

Zitatantwort auf diesen Beitrag erstellen

Hallo Ich hab hier zwei Beispiele gegeben, wo Infix in Postfix und Präfix umgewandelt wurde. Ich verstehe aber nicht, wie das gehen soll.
1. Beispiel

Infix : 4+5*2+9/10

Postfix: 4 5 2 * + 9 10 / +

Präfix: + + 4 * 5 2 / 9 10

Ich meine mich an irgendeine Regel erinnern zu können, die sagte: Bei Präfix Operanden zu erst. Jedenfalls finde ich da nichts konkretes, wie man von Infux nach Postfix oder Präfix kommt. Dazu recherchieren konnte ich lediglich, dass das hier Baumtraversierungsarten sind. Dazu würde ich gerne den Baum der Infix-Notation malen, Aber auch da weiß ich nicht, wie das funktionieren soll.

2. Beispiel

Infix: 3 - 2 - 8 * 4 + 2 * 5

Postfix: 3 2 - 8 4 * - 2 5 * +

Präfix: + - - 3 2 * 8 4 * 2 5

Wie wandel ich das nun um? Kann man mir das erklären?
Vielleicht auch, wie ich den Infix-Baum male?

PS: Ich übe gerade nur und muss das nicht für die Schule oder so machen. Sonst hätte ich die Lösungen ja auch nicht smile

Gruß,
Phoney

29.09.2007 15:24

Nehmen Sie Phoney in Ihre Freundesliste auf

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Wie man den Baum aufstellt weißt du?

Wenn ja, dann traversiere ihn mal in depth-first-left-order und schon hast du die Präfix-Notation.

29.09.2007 16:06

Nehmen Sie Tobias in Ihre Freundesliste auf

Phoney
Jungspund

Dabei seit: 13.12.2006
Beiträge: 20

Nein, hier weiß ich leider nicht, wie man einen Baum aufstellt.

Ich meine, da steht etwas von Plus und so, wie soll ich das denn da einbrigen? Mir fällt da nur spontant die Regel ein, alles was größer dem Wurzelelement ist, sollte im rechten Zweig stehen, alles was kleiner gleich ist unten links. Aber im Graph dürfte die Wurzel hier ja ein Plus sein... Warum auch immer?
Wie stellt man denn den Baum zur Infix-Notation auf?

29.09.2007 17:46

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Nehmen wir die normale Infixnotation 4+5*2+9/10.

Als erste Erleichterung klammern wir mal den Ausdruck nach unseren Rechengesetzen (Punkt vor Strich):

4+5*2+9/10 = 4+(5*2)+(9/10)

Nun benutzen wir für die weitere Klammerung die Linksassoziativität:

4+(5*2)+(9/10) = (4 + (5*2)) + (9/10)

Allgemein: a + b + c = (a + b) + c.

Jetzt können wir den Baum konstruieren. Dafür schauen wir, was die äußerste (oder oberste) Regel der Gleichung ist. Das ist in (4 + (5*2)) + (9/10) die Addition und die beiden Summanden sind (4 + (5*2)) und (9/10).

D.h. die Wurzel des Baumes ist ein + und sie wird verbunden mit zwei Teilbäumen. Der linke Teilbaum entsteht aus dem Term (4 + (5*2)) und der rechte aus dem Term (9/10).

Der linke Teilbaum wird aus (4 + (5*2)) konstruiert. Hier ist die oberste Operation wieder die Addition und die beiden Nachfolger sind die 4 und der Teilbaum aus (5*2).

Und so führt man das fort, bis man den gesamten Term als Baum dargestellt hat.

Tobias hat dieses Bild (verkleinerte Version) angehängt:

30.09.2007 13:26

Phoney
Jungspund

Dabei seit: 13.12.2006
Beiträge: 20

Danke für die recht ausführliche Erklärung. Eine Frage habe ich aber noch
Wäre auch (5*2) + ((9/10)+4) möglich? Also dass der Baum wir die Plus 4 in den rechten Ast schreiben und dort ein Übergewicht haben? Also quasi wie der Linke Ast, nur dass wir auf der Rechten Seite jetzt

code:
1: 2: 3: 4: 5: 6: 7: 8:	+ 4 / 9 10

Das dürfte eigentlich nicht funktionieren, oder? Warum das Übergewicht im linken Ast, also warum ist der linke Ast länger als der REchte?

30.09.2007 20:47

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Das ist erlaubt. Addition ist sowohl links- als auch rechtsassoziativität. Also kannst du auch so klammern:

a + b + c = a + (b + c)

So entsteht dann ein "Übergewicht" auf der rechten Seite. Du kannst also Additionen klammern wie du willst.

30.09.2007 21:03

Phoney
Jungspund

Dabei seit: 13.12.2006
Beiträge: 20

Echt? Das überrascht mich jetzt aber. Die Tiefensuche funktioniert dann immernoch und ich erhalte dann auch noch immer die Präfixform? Hätte ich jetzt nicht gedacht.
Danke

30.09.2007 21:08

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

War hat behauptet, dass die Präfixform eindeutig ist?

30.09.2007 22:07

Phoney
Jungspund

Dabei seit: 13.12.2006
Beiträge: 20

Ich

Danke, nun ist alles klar Daumen hoch

30.09.2007 23:14

aaagul45
Grünschnabel

Dabei seit: 16.12.2014
Beiträge: 1

Jetzt können wir den Baum konstruieren. Dafür schauen wir, was die äußerste (oder oberste) Regel der Gleichung ist. Das ist in (4 + (5*2)) + (9/10) die Addition und die beiden Summanden sind (4 + (5*2)) und (9/10).
D.h. die Wurzel des Baumes ist ein + und sie wird verbunden mit zwei Teilbäumen. Der linke Teilbaum entsteht aus dem Term (4 + (5*2)) und der rechte aus dem Term (9/10).??
70-417 dump - testking.net

__________________
GuL

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von aaagul45: 16.12.2014 08:00.

16.12.2014 08:00

Nehmen Sie aaagul45 in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » übergreifende Themen » Präfix und Postfix