Bäume

[PaulDo]

Folgende Aufgabe liegt mir vor: 9+(3 x 5 - 4) + (7 x 2 / (8 x 4-2)+4 )x 5. Wie packe ich diesen Ausdruck in einen Baum? Also Roof ist +. Links kommt die 9. Links + dann x dann 5. Aber danach habe keine Idee mehr?

 

[httpdigest]

      +
     / \
    9   +
       / \
      -   \
     / \   \
    x   4   x
   / \     / \
  3   5   +   5
         / \
        x   4
       / \
      7  '/'
         / \
        2   -
           / \
          x   2
         / \
        8   4

 

[fhoffmann]

Da da Assoziativgesetz für die Addition gilt ( (a + b) + c = a + (b + c) ) ist der Baum nicht eindeutig.

 

[httpdigest]

Dasselbe gilt auch für * und /.
a * b / c = (a * b) / c = a * (b / c)

 

[PaulDo]

      +
     / \
    9   +
       / \
      -   \
     / \   \
    x   4   x
   / \     / \
  3   5   +   5
         / \
        x   4
       / \
      7  '/'
         / \
        2   -
           / \
          x   2
         / \
        8   4

Könntest Du mal versuchen, mir diesen Weg zu beschreiben? Danke im Voraus.

 

[httpdigest]

Könntest Du mal versuchen, mir diesen Weg zu beschreiben? Danke im Voraus.

Naja:
1. du schaust dir den Ausdruck an und identifizierst erstmal den Operator mit der geringsten Priorität/Bindung auf oberster Ebene
2. du entscheidest dich bei mehreren solcher Operatoren auf derselben Ebene für eine "Klammerung" (also ob der Baum "links-lastig" oder "rechts-lastig" wird), also ob du 1 + 2 + 3 als (1 + 2) + 3 oder als 1 + (2 + 3) im Baum repräsentieren willst
3. du teilst den Ausdruck an dem gewünschten Operator, den du unter 2. identifiziert hast, in zwei Teilausdrücke A und B auf, wobei A der Teil links vom Operator aus 2. ist, und B der Teil rechts vom Operator aus 2.
4. du erzeugst einen Knoten mit dem Namen des Operators aus 2.
5. du wendest diese Teilschritte 1. bis 5. auf die in 3. aufgeteilten Teilausdrücke A und B an, wobei der für A entstandene Teilbaum dann das linke Kind des Knotens aus 4. wird und der für B entstandene Teilbaum das rechte Kind des Knotens aus 4.

Fertig. Und dann muss man noch etwas mit dem Layouting rumspielen, wenn man das ganze in Form eines solchen "ASCII-Art" Diagramms schreiben will.

 

[KonradN]

Alternativ kann man auch den umgekehrten Weg gehen und den Baum sozusagen von unten nach oben statt von oben nach unten aufzubauen.

Das hat den Vorteil, dass Du genau so vorgehen kannst wie bei dem Ausrechnen.

Du hast also z.B. eine Aufgabe wie (2 + 4) * 7 + 3 * (2 + 3)

Wie rechnest Du das aus? Was musst Du zuerst ausrechnen, um zum richtigen Ergebnis zu kommen?

Klammern kommen zuerst, also als erstes musst Du 2+4 und 2+3 Rechnen. Damit hast Du die ersten Zwei Teilbäume - jeweils ein Knoten mit + und die Blätter sind einmal 2 und 4 und einmal 2 und 3.

Was kommt dann? Beim ersten Teilbaum kommt das * 7 und beim zweiten Teilbaum das 3 *

Also hast Du jeweils den Operator als Knoten und rechts und links kommen die Operanden dran. Diesmal ist halt der erste Teilbaum und die 7 und beim zweiten dann die 3 und der zweite Teilbaum.

Dann kommt am Ende noch die Addition.

Das ist von der Logik her evtl. leichter zu verstehen. Und damit wird auch die Umsetzung relativ einfach, wenn man es implementieren müsste.

Aber das ist jetzt eine sehr subjektive Sichtweise, da dies halt genau meiner Herangehensweise entsprechen würde, wenn ich sowas rechnen müsste.

Da ist halt nur wichtig, dass man die fachliche Seite beherrscht ... Und da fällt mir nur ein: 25 - 5/5 = 4! Sowas muss man halt können und verstehen!

 

[mihe7]

Da werfe ich mal eine weitere Methode in den Raum, die eigentlich nichts anderes ist als die beiden anderen (die mathematischen Gesetze gelten): schreibe die Rechnung mit Funktionen statt Operatoren.

Aus a+b+c*d wird dann z. B. add(a, add(b, mult(c,d))) und schon hast Du den Baum dastehen.

  +
 / \
a   +
   / \
  b   *
     / \
    c   d

 

[MarvinsDepression]

Der Vorschlag gefällt mir. Da sind wir doch gleich bei der Polnischen Notation, glaube ich. Am Taschenrechner nutze ich auch immer UPN, wo's geht (geht eigentlich immer).
Man kann sich auch einen Spaß machen und ...

Aus a+b+c*d wird dann z. B. add(a, add(b, mult(c,d))) und schon hast Du den Baum dastehen.

... nennen die Methoden dann noch getSummOfTwoValues(...) oder getFirstValueDivideBy2ndValue(...) und nennen die Variablen beim Wert, also valueOfNine und valueOfSeven ...
Das wird kein Baum, das wird ein Fest 😆

 

[mihe7]

Da sind wir doch gleich bei der Polnischen Notation

Ja, oder halt Präfixnotation, weil der Operator vor den Operanden steht. Ich habe absichtlich Funktionen gewählt, weil sich die Leute damit eher auskennen und vermutlich leichter tun.

 

[PaulDo]

Alternativ kann man auch den umgekehrten Weg gehen und den Baum sozusagen von unten nach oben statt von oben nach unten aufzubauen.

Das hat den Vorteil, dass Du genau so vorgehen kannst wie bei dem Ausrechnen.

Du hast also z.B. eine Aufgabe wie (2 + 4) * 7 + 3 * (2 + 3)

Wie rechnest Du das aus? Was musst Du zuerst ausrechnen, um zum richtigen Ergebnis zu kommen?

Klammern kommen zuerst, also als erstes musst Du 2+4 und 2+3 Rechnen. Damit hast Du die ersten Zwei Teilbäume - jeweils ein Knoten mit + und die Blätter sind einmal 2 und 4 und einmal 2 und 3.

Was kommt dann? Beim ersten Teilbaum kommt das * 7 und beim zweiten Teilbaum das 3 *

Also hast Du jeweils den Operator als Knoten und rechts und links kommen die Operanden dran. Diesmal ist halt der erste Teilbaum und die 7 und beim zweiten dann die 3 und der zweite Teilbaum.

Dann kommt am Ende noch die Addition.

Das ist von der Logik her evtl. leichter zu verstehen. Und damit wird auch die Umsetzung relativ einfach, wenn man es implementieren müsste.

Aber das ist jetzt eine sehr subjektive Sichtweise, da dies halt genau meiner Herangehensweise entsprechen würde, wenn ich sowas rechnen müsste.

Da ist halt nur wichtig, dass man die fachliche Seite beherrscht ... Und da fällt mir nur ein: 25 - 5/5 = 4! Sowas muss man halt können und verstehen!

Danke, so kann ich es nachvollziehen. Aber die Aufgabe 25-5/5 = 4 verstehe ich nicht. Ich würde erst 5/5 rechnen = 1 und 25-1 = 24. Warum wäre das falsch?

 

[yfons123]

public class Main {
    public static void main(String[] args) {
        System.out.println(25-5/5);
    }
}

Danke, so kann ich es nachvollziehen. Aber die Aufgabe 25-5/5 = 4 verstehe ich nicht. Ich würde erst 5/5 rechnen = 1 und 25-1 = 24. Warum wäre das falsch?

eclipse mit java 17 würde es auch so rechnen

 

[KonradN]

Danke, so kann ich es nachvollziehen. Aber die Aufgabe 25-5/5 = 4 verstehe ich nicht. Ich würde erst 5/5 rechnen = 1 und 25-1 = 24. Warum wäre das falsch?

Das war ein kleiner Joke ... Du rechnest richtig nur eben hast Du das ! vergessen. Das Ergebnis ist nicht 4 sondern 4! und 4! = 1*2*3*4 = 24

 

[PaulDo]

Anbei die Lösung der Uni: