Algorithmen und Programmierung II

 SS 2004
Zusatzblatt 2
 Abgabe: 14.7.2004


Aufgabe 1 (4 Punkte)

In der Vorlesung wurde das 8-Damen-Problem vorgestellt. In dem Algorithmus wird eine Methode boolean bedroht(int zeile, int spalte) verwendet, die eine Aussage darüber trifft, ob ein gegebenes Feld des Schachbretts, unter Berücksichtigung aller bisher platzierten Damen, bedroht ist.

Ergänzen Sie die folgende Spezifikation von bedroht um die Beschreibung des Ergebnisses. Die Spezifikation soll formalsprachlich mittels Haskell erfolgen.
 
    /**
     * Voraussetzung: -- (keine)
     * Effekt:        --
     * Ergebnis:      ...
     */
    boolean bedroht(int zeile, int spalte)
Hinweise: Bei der Repräsentation des Schachbretts als boolean-Feld werden Elemente mit Index 0 ignoriert.


Aufgabe 2 (8 Punkte)

Für einfache Ausdrücke lässt sich ein Parser relativ einfach in Anlehnung an die Struktur der zugrunde liegenden Grammatik entwickeln. Vorgegeben sei beispielsweise die folgende Grammatik:
    expression = term { addOp term }
    addOp = + | -
    term = factor { mulOp factor }
    mulOp = * | /
    factor = number | (expression)
Die Auswertung eines Ausdrucks (expression) wird durch die Methode expression im vorgegebenen Programmfragment geleistet. Die Eingabe darf keine Leerzeichen enthalten und muss einen Punkt als Endmarkierung enthalten, z.B. "(31+219)/25.".

Der Parser soll erweitert werden, um auch den Exponentiationsoperator ^ zu unterstützen. Beispiel:

    Eingabe: (100-98)^10*2.
    Ausgabe: 2048

a)  Modifizieren Sie die oben stehenden Grammatik entsprechend und ergänzen Sie die fehlende Regel für number. Beschränken Sie sich auf positive ganze Zahlen.

b)  Vervollständigen bzw. modifizieren Sie das gegebene Programmfragment, so dass ein Ausdruck gemäß der neuen Grammatik von der Kommandozeile eingelesen und das Ergebnis (bzw. eine Fehlermeldung) ausgegeben wird.

Hinweis: Der Exponentiationsoperator soll, entsprechend der üblichen Konvention, rechtsassoziativ sein (2^3^2 = 2^(3^2) = 512).