WS 2002/2003                   Übung  4                           H. Schweppe
        

        Ausgabe:  7.11.2002
        Abgabe:  19.11.2002 

Aufgabe 4.1 (   10 P)  
Geben Sie die Postfix-Darstellung der folgenden Ausdrücke an. Dabei bezeichnet ^ den Potenzierungsoperator, a ^ b  ist  also a^b . ^ hat eine höhere Präferenz als * und / und ist rechtsassoziativ. 
a) 1 + 2 -3 ^ 4 
b) 1 + 2 * 3 - 4 ^ 3 + 6
c) (1 + 2 ) * 3 - (4 ^ ( 5 - 3)  )
Geben Sie in jedem wesentlichen Schritt den Operator-Stack an. 
d) Werten Sie die Postfixausdrücke aus a) und c) aus. Dabei sollen die verschiedenen Stadien des Operanden-Stapels angegeben werden. 
e) Wir gehen von einem klammerfreien  Infix-Ausdruck aus. Der zugehörige Postfix-Ausdruck sei 
 4 5 7 + * . Ist er  korrekt? Wenn nein, warum nicht; wenn ja: wie sieht der zugehörige Infix-Ausdruck aus? 
(je 2 P) 

Aufgabe 4.2 (  14P)  
Verändern bzw. erweitern Sie das Programm zur Auswertung von arithmetischen Ausdrücken. 

a) (2) Ersetzen Sie die class StackFactory durch eine statische Methode in Stack. Dieses Interface muss dann zu einer abstrakten Klasse gemacht werden. 
b) (2) Ersetzen Sie die Implementierung des verwendeten Stapels mit Feldern durch eine, die eine verkettete Liste verwendet (Für class LListStack reicht das Anpassen der Klasse aus Alp2)
c) (3) Gefragt ist die Erweiterung um die Potenzierungsoperator, den wir (wie in Haskell) mit  ^  benennen. 
   Beachte: ^ ist rechtsassoziativ, also   a ^ b ^c  ==  a ^ ( b ^ c )  .
d) (5 ) Erweitern Sie das Programm  so, dass die arithmetischen Ausdrücke in Infix-Darstellung eingegeben werden können. 
e  (2 ) Trockenübung: Skizzieren Sie (max 15 Zeilen), wie man den Rechner um einstellige Operationen (wie einstelliges - ) erweitern könnte. 

Aufgabe 4.3 (  8 P)  
Zu vorgegebenem max aus N+ sollen natürliche Zahlen aus {0,1,2,..,max-1} auf einem Stapel gespeichert werden.  Die folgende Spezifikation ist vorgegeben:

interface NumberStack {
     // model: s :: [Int];  max, maxlength :: Int
     // inv:   max > 0 && all(\x-> x>=0 && x<max) 
     // && max <= MAX &&
     //        maxlength > 0 && length s <= maxlength &&
     //        maxlength == MAXLENGTH – i.e. maxlength is constant

void init(int m) throws InvalidRange;
 // pre:     0 < m <= MAX  -- else InvalidRange
  // post:  s == [] && max == m

void push(int x) throws OutOfRange, StackOverflow;
 // pre:   x >= 0 && x < max    -- else OutOfRange
  //        && length s < maxlength   -- else StackOverflow
 // post:  s == x:S -- S is value before push(..)

int pop() throws StackUnderflow;
  // pre:   S /= []             // else StackUnderflow
 // post:  if (S == x:xs) then  s==xs  && result = x    

int length(); 
    // pre:   True
  //  post:  result == length s && s == S
}

Der Stapel (Keller) soll durch eine Zahl repräsentiert werden. ( maxlength ist hier nicht durch die Spezifikation festgelegt, sondern ergibt sich aus der gewählten Repräsentation!)  Geben Sie eine entsprechende Java-Klasse an. 

Vergessen Sie nicht die Abstraktionsfunktion und die Repräsentationsinvariante. Testen Sie   die Implementierung (Unit-Test).

Aufgabe 4.4( 3  P)   
Gegeben eine n x n -Matrix mit 0 und 1, bei der in jeder Zeile erst die Einsen, dann die Nullen kommen. Entwerfen Sie einen Algorithmus, der selbst im schlechtesten Fall in linearer (nicht quadratischer) Zeit feststellt, in welcher Zeile die meisten Einsen zu finden sind. Falls es mehrere Zeilen gibt, reicht die erste. Begründen Sie kurz, warum der Algorithmus linear ist. (Trockenübung, Pseudocode reicht also).  

Gesamt: 35 Punkte