---

Geschrieben von Phoney am 29.09.2007 um 15:24:

  Präfix und Postfix

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

Gruß,
Phoney

---

Geschrieben von Tobias am 29.09.2007 um 16:06:

 

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.

---

Geschrieben von Phoney am 29.09.2007 um 17:46:

 

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?

---

Geschrieben von Tobias am 30.09.2007 um 13:26:

 

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.

---

Geschrieben von Phoney am 30.09.2007 um 20:47:

 

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?

---

Geschrieben von Tobias am 30.09.2007 um 21:03:

 

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.

---

Geschrieben von Phoney am 30.09.2007 um 21:08:

 

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

---

Geschrieben von Tobias am 30.09.2007 um 22:07:

 

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

---

Geschrieben von Phoney am 30.09.2007 um 23:14:

 

Ich

Danke, nun ist alles klar

---

Geschrieben von aaagul45 am 16.12.2014 um 08:00:

 

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