Aufgaben zur Vorlesung

Aufgabe 1:

Die Methode actionPerformed der Schnittstelle ActionListener bekommt ein Objekt der Klasse ActionEvent übergeben. In dieser gibt es eine Methode getWhen, die den Zeitpunkt, zu dem das Ereignis aufgetreten ist als eine Zahl kodiert zurückgibt. Mit dieser Zahl können Sie die Klasse java.util.Date instanziieren, um ein Objekt zu bekommen, das Datum und Uhrzeit enthält.

Schreiben Sie jetzt eine Unterklasse von JTB, so daß beim Drücken des Knopfes, jetzt die aktuelle Uhrzeit im Textfeld erscheint.

Aufgabe 2:

Schreiben Sie eine kleine Guianwendung mit einer Textfläche und drei Knöpfen, die einen erweiterten Zähler darstellt:

Aufgabe 3:

Schreiben Sie Ihr Programm eines Zählers mit drei Knöpfen jetzt so, daß sie innere Klassen benutzen.

Aufgabe 4:

(Punkteaufgabe 2 Punkte) Schreiben Sie eine GUI-Komponente StrichKreis, die mit geraden Linien einen Kreis entsprechend untenstehender Abbildung malt. Der Radius des Kreises soll dabei dem Konstruktor der Klasse StrichKreis als int-Wert übergeben werden.

Testen Sie Ihre Klasse mit folgender Hauptmethode: 

public static void main(String [] args) {
  StrichKreis k = new StrichKreis(120);
  JFrame f = new JFrame();
  JPanel p = new JPanel();
  p.add(new StrichKreis(120));
  p.add(new StrichKreis(10));
  p.add(new StrichKreis(60));
  p.add(new StrichKreis(50));
  p.add(new StrichKreis(70));
  f.getContentPane().add(p);

  f.pack();
  f.setVisible(true);
}

Hinweis: In der Klasse java.lang.Math finden Sie Methoden trigeometrischer Funktionen. Insbesondere toRadians zum Umrechnen von Gardwinkel in Bogenmaß sowie sin und cos.

Aufgabe 5:

Erweitern Sie die Strichkreisklasse aus der letzten Aufgabe, so daß jeder Strich in einer anderen Farbe gezeichnet wird.

Aufgabe 6:

(2 Punkte) Implementieren Sie eine Analoguhr. Das Ziffernblatt dieser Uhr können Sie dabei mit den Methoden auf einem Graphics-Objekt zeichnen, oder Sie können versuchen eine Bilddatei zu laden und das Ziffernblatt als Bild bereitstellen. Als Anregung für ein Ziffernblatt können Sie sich das Bild des Ziffernblatts der handgefertigten Sekundenuhr des Uhrmachers G.Wiebking herunterladen.

Aufgabe 7:

Schreiben Sie eine Animation, in der zwei Kreise sich bewegen. Die Kreise sollen an den Rändern der Spielfläche abprallen und sie sollen ihre Richtung ändern, wenn sie sich berühren.

Aufgabe 8:

Schreiben Sie eine Animation, deren Verhalten über Mausklicks beeinflussen können.

Aufgabe 9:

Erzeugen Sie ein Baumobjekt, das einen Stammbaum Ihrer Familie darstellt. Die Knoten und Blätter sind mit Namen markiert. Die Wurzel ist mit Ihren Namen markiert. Kinderknoten sind mit den leiblichen Eltern der Person eines Knotens markiert.

Aufgabe 10:

Testen Sie die in diesem Abschnitt entwickelten Methoden auf Bäumen mit dem in der letzten Aufgabe erzeugten Baumobjekt.

Aufgabe 11:

Punkteaufgabe (4 Punkte):
Für diese Aufgabe gibt es maximal 4 auf die Klausur anzurechnende Punkte. Abgabetermin: wird noch bekanntgegeben.

Schreiben Sie die folgenden weiteren Methoden für die Klasse Tree. Schreiben Sie Tests für diese Methoden.

a) List leaves(): erzeugt eine Liste der Markierungen an den Blättern des Baumes.
b) String show(): erzeugt eine textuelle Darstellung des Baumes. Jeder Knoten soll eine eigene Zeile haben. Kinderknoten sollen gegenüber einem Elternknoten eingerückt sein.

Beispiel:

william
  charles
    elizabeth
    phillip
  diana
    spencer
Tipp: Benutzen Sie eine Hilfsmethode
String showAux(String prefix),
die den String prefix vor den erzeugten Zeichenketten anhängt.
c) boolean contains(a o): ist wahr, wenn eine Knotenmarkierung gleich dem Objekt o ist.
d) int maxDepth(): gibt die Länge des längsten Pfades von der Wurzel zu einem Blatt an.
e) List<a> getPath(a o): gibt die Markierungen auf dem Pfad von der Wurzel zu dem Knoten, der mit dem Objekt o markiert ist, zurück. Ergebnis ist eine leere Liste, wenn ein Objekt gleich o nicht existiert.
f) java.util.Iterator<a> iterator(): erzeugt ein Iterator über alle Knotenmarkierungen des Baumes.
Tipp: Benutzen Sie bei der Umsetzung die Methode flatten.
g) public boolean equals(Object other): soll genau dann wahr sein, wenn other ein Baum ist, der die gleiche Struktur und die gleichen Markierungen hat.
h) <b>boolean sameStructure(Tree<a> other): soll genau dann wahr sein, wenn der Baum other die gleiche Struktur hat. Die Markierungen der Knoten können hingegen unterschiedlich sein.

Aufgabe 12:

Schreiben Sie eine Methode List<Tree<a>> siblings(), die die Geschwister eines Knotens als Liste ausgibt. In dieser Liste der Geschwister soll der Knoten selbst nicht auftauchen.

Aufgabe 13:

Schreiben Sie eine modifizierende Methode
void deleteChildNode(int n),
die den n-ten Kindknoten löscht, und stattdessen die Kinder des n-ten Kindknotens als neue Kinder mit einhängt.
Beispiel:
          a
         / \
        /   \
       b     c
      / \   / \
     d   e  f  g
           /|\ 
          h i j
wird durch
deleteChildNode(1)
zu:
          a
         /|\
        / | \
       /  |  \
      /   |   \
     b    f    g
    /|   /|\
   d e  h i j

Aufgabe 14:

Überschreiben Sie die Methoden addLeaf und deleteChildNode in der Klasse BinTree, so daß sie nur eine Ausnahme werfen, wenn die Durchführung der Modifikation dazu führen würde, daß das Objekt, auf dem die Methode angewendet wird, anschließend kein Binärbaum mehr wäre.

Aufgabe 15:

Schreiben Sie analog zur Methode flatten in der Klasse Tree eine Methode
List<a> postorder(), die die Knoten eines Baumes in Postordnung linearisiert.

Aufgabe 16:

Rechnen Sie auf dem Papier ein Beispiel für die Arbeitsweise der Methode military().

Aufgabe 17:

Zeichnen Sie schrittweise die Baumstruktur, die im Programm TestSearchTree aufgebaut wird.

Aufgabe 18:

Erzeugen Sie ein Objekt des typs SearchTree und fügen Sie nacheinander die folgenden Elemente ein:
"anna","berta","carla","dieter","erwin","florian","gustav"
Lassen Sie anschließend die maximale Tiefe des Baumes ausgeben.

Aufgabe 19:

a) Schreiben sie entsprechend die Methode:
static public SearchTree rotateLeft(SearchTree t)
b) Schreiben Sie in der Klasse BinTree die entsprechende modifizierende Methode rotateLeft()
c) Testen Sie die beiden Rotierungsmethoden. Testen Sie, ob die Tiefe der Kinder sich verändert und ob die Inordnung gleich bleibt. Testen Sie insbesondere auch einen Fall, in dem die NullPointerException abgefangen wird.

Aufgabe 20:

Erweitern Sie die obige Grammatik so, daß sie mit ihr auch geklammerte arithmetische Ausdrücke ableiten können. Hierfür gibt es zwei neue Terminalsymbolde: ( und ).

Schreiben Sie eine Ableitung für den Ausdruck: 1+(2*20)+1

Aufgabe 21:

Betrachten Sie die einfache Grammatik für arithmetische Ausdrücke aus dem letzen Abschnitt. Zeichnen Sie einen Syntaxbaum für den Audruck 1+1+2*20.

Aufgabe 22:

(2 Punkte) In dieser Aufgabe sollen Sie den Parser für arithmetische Ausdrücke um geklammerte Ausdrücke erweitern. Hierzu sei die Grammatik für die Regel multExpr wie folgt geändert:
multExpr ::= atomExprmultOpmultExpratomExpr
atomExpr ::= (addExpr)|zahl
Hierzu sei die entsprechende zusätzliche Tokenaufzählung für die zwei Klammersymbole gegeben:
package name.panitz.parser;
public enum Parentheses implements Token{lpar,rpar;}
Zusätzlich gegeben sei die die folgende Funktion:
package name.panitz.parser;

public class DoParentheses
  implements  
    Function<Pair<Parentheses,Pair<Integer,Parentheses>>,Integer>{
  public Integer 
             apply(Pair<Parentheses,Pair<Integer,Parentheses>> x){
    return x.getE2().getE1();
  }
}
a) Schreiben Sie eine Klasse AtomExprEval, die Parser<Integer> implementiert und der Regel für atomExpr entspricht.
b) Ändern Sie die Klasse MultExprEval, so daß sie der geänderten Grammatikregel entspricht.
c) Erweitern Sie die Klasse ArithTokenizer, so daß er auch die beiden Klammersymbole erkennt.

Aufgabe 23:

Fügen Sie der Datei sms.jjt folgende Zeilen am Anfang ein:
options {
   MULTI=true;
   STATIC=false;
}
Generieren Sie mit jjtree und javac den Parser neu. Was hat sich geändert?

Beispielaufgaben zur Klausur:

Aufgabe 1:

Betrachten Sie folgenden Baum.

a) Handelt es sich bei diesen Baum um einen binären Suchbaum (mit lexikographischer Ordnung auf den Stringmarkierungen)? Begründung?

Wenn nicht, dann zeichnen Sie einen binären Suchbaum, der die gleichen Elemente enthält.

b) Wie könnten Sie vorgehen, um aus einem Binärbaum einen beliebigen Knoten zu löschen? Malen sie hierzu Beispiele und beschreiben Sie ihr Vorgehen.

Aufgabe 2:

Betrachten Sie das folgende Javamethoden, die der Baumklasse Tree hinzugefügt wurden. Rechnen Sie die Methoden auf dem Papier für den Baum aus Aufgabe 1 durch und geben ihr Ergebnis an.

Was berechnen die Methoden?

a) 
int foo1(){
  int result = theChildren().size();
  for (Iterator it=theChildren().iterator();it.hasNext();){
    final int n = ((Tree)it.next()).foo1();
    if (n>result) result=n;
  }
  return result;
}

b) 
List foo2(List result){
  result.add(mark());
  final List xs= theChildren();
  if (!xs.isEmpty()){
    try {
      ((Tree)xs.get(1)).foo2(result);
    }catch (Exception _){}
  }
  return result;
}

Aufgabe 3:

Gegeben sei die folgende abstrakte Klasse für Bäume, gemäß unserer Spezifikation aus der Vorlesung:
import java.util.*;

abstract class AbTree{
  abstract public AbTree tree(Object mark, List/*AbTree*/ xs);
  abstract public Object mark();
  abstract public List/*AbTree*/ theChildren();
}
Schreiben Sie für die Klasse folgende Methoden, die ihr hinzugefügt werden können:
a) int howOftenContained(Object o): zählt, wieviel Knoten mit einem Objekt markiert sind, das gleich dem Argument o ist.
b) AbTree mapToUpperCase() ergibt einen neuen Baum, der die gleiche Struktur hat und dessen Knoten mit Strings markiert sind, die sich ergeben, indem man die Markierungen des Ausgangsbaums mit mark().toString().toUpperCase() umwandelt.

Aufgabe 4:

Gegeben seien folgende Gui-Komponenten:
a) Erweitern Sie die Komponente GoodbeyFrame so, daß beim Drücken des Knopfes, das Programm mit System.exit(0) beendet wird.
b) Erweitern Sie die Komponente SimpleFrame so, daß beim Schließen des Fensters ein Objekt des Typs GoodbyeFrame erzeugt wird.

Aufgabe 5:

Gegeben sei folgende Grammatik:
start ::= addExpr
addExpr ::= multExpr addOpaddExpr multExpr
multExpr ::= zahlmultOpmultExpr zahl
multOp ::= */
addOp ::= +-
Das Terminalsymbol zahl steht dabei für eine beliebige Zahl.
a) Leiten Sie den Ausdruck 1*4+42/5-6 mit der rekursiv absteigenden Parserstrategie ab.
b) Zeichnen Sie den Ableitungsbaum für Ihre obige Ableitung.
c) Die Grammatik erlaubt kein unäres Minussymbol zum Negieren einer Zahl. Ergänzen Sie die Grammatik, so daß dieses erlaubt ist. Zeigen Sie damit die Ableitung des Audrucks -12 * -1 -4 + 2.