ADT 3

2.3 Implementierung und Anwendung von ADT
2.3.1 Anwendung von ADT
.... am Beispiel "Stapel"
Ziel
Implementierung einer Anwendung ohne
Annahmen über die Implementierung der Typen
Austauschen der Implementierung eines ADT
ohne Veränderung des Klientenprogramms.
Auswertung Arithmetischer Ausdrücke:
Wichtige Anwendung von Stapeln
Auswerten von arithmetischem Ausdruck
Definition
arithmetischer Ausdrücke
( infix-Notation von zweistelligen Operationen)
eine reelle Zahl ist ein AA
von a und b AA, dann auch a+b, a-b, a*b, a/b,
und (b)
das sind alle AA
Auswertung nach Operatorpräferenz
(hier: " Punkt vor Strich")
Auswertungsmethode:
- Ausdruck in umgekehrter polnischer Notation
- Einkellern von Operanden und
Zwischenergebnissen
hs / fub – alp3 –ADT-3 2
1
Polnische Notation
Klammerfreie
Schreibweise von arithmetischen
Ausdrücken
Operatoren stehen vor den Operanden
(Jan Lukasiewicz, polnischer Logiker, 1848-1956,
http://www.philosophenlexikon.de/lukasiew.htm )
Beispiel:
(2+3) * 5 -> * + 2 3 5
Auswertung: Operatoranwendung wenn
genügend Operanden vorhanden.
Alternative:
Umgekehrte polnische Notation
("reverse polish notation", "postfix")
23+5*
hs / fub – alp3 –ADT-3 3
Auswertung klammerfreier Ausdrücke
Beispiel:
(5+3) *(9 - 4) / 5 + 4
5
3
5
8
-> 5 3 + 9 4 - * 5 / 4 +
9
8
5+3
40
8*5
5
40
8
40 / 5
4
8
4
9
8
5
8
9-4
12
12
8+4
hs / fub – alp3 –ADT-3 4
2
Auswertung klammerfreier Ausdrücke
Algorithmus (Pseudocode, no Syntax check) :
double eval (String a) {
Stack s = new Stack();
while (not a.stringEmpty()) {
token a = readNext(); // reads number or token
if (isNumber(a)) s.push();
else {right = s.top(); s.pop(); // a is operator
left = s.top(); s.pop();
s.push(execOp( left,a,right))
}
}
return s.top();
}
hs / fub – alp3 –ADT-3 5
"Infix to postfix"
postfix"
Infix
Darstellung von arithmetischen Ausdrücken
binäre Operatoren
ggf. Klammerung
zwischen Operanden
5 + 3 * 5 / 10
((2+3)*5 +1) / 2
Postfix
Darstellung
Operatoren stehen "geeignet" hinter den Operanden
keine Klammern nötig
5 3 5 10 / * +
23+5*1+2/
Achtung: wird 5 + (3*(10/5)) ausgewertet! entspricht nicht der
Konvention "Linksklammerung".
siehe separate Anmerkungen
hs / fub – alp3 –ADT-3 6
3
"Infix to postfix"
postfix" mit Hilfe eines OperatorOperator-Stapel
Input:
2*3–4/2
*3–4/2
3–4/2
-4/2
4/2
/2
2
Output _
2
2
23
23*
2 3* 4
2 3 *4 2
23*42/–
Stack
_
*
*
- /
-/
Wichtig: Operatorpräferenz
hs / fub – alp3 –ADT-3 7
Operatorpräferenzen
stack
2+3 * 5
-> 2 3
+
235
+*
Ergebnis:
235*+
2*3 + 5 ->
Ergebnis:
(2+3) * 5 ->
*5
Ergebnis:
23
*
23*
+
23*5+ _
23
(+
23+
_
23+5*
// Lesen von * : pref * > pref (top)
// push *
// Lesen von + : pref + < pref (top)
// Pop bis Operator kleiner Präfer.
//
"top-of-stack"
// Öffnende Klammer auf Stapel
// Schließende Klammer: pop bis "("
hs / fub – alp3 –ADT-3 8
4
Assoziativität von Operatoren
Was ist
30 / 5 / 2 ?
Konvention: 30 / 5 / 2 = ( (30 / 5) / 2)
Taucht das zweite "/" auf, ist das erste
abgearbeitet => pop
=> 30 5 / 2 /
ausgewertet: 3
op linksassoziativ a op b op c = (a op b) op c
op rechtsassoziativ a op b op c = a op (b op c)
Beispiel: Potenz a^b ^c = (a ^(b ^ c) )
hs / fub – alp3 –ADT-3 9
"Infix -> Präfix" - Algorithmus
String infix2Postfix (String a) {
Stack s = new Stack();
StringBuffer result = new StringBuffer();
while (not a.stringEmpty()) {
token a = readNext(); // reads number or token
if (isNumber(a)) result.append(a);
else {if (a="(" ) s.push(a);
if (pref (a) > pref(s.top()) s.push(a);
if (pref (a < pref(s.top()) popAndAppend(s,result);
if (pref (a) = pref(s.top() & isRightAss(a) ) s.push(a);
.... isLeftAss() ) .....
}
}
return result.toString( );
}
hs / fub – alp3 –ADT-3 10
5
Repräsentation von Präferenzen
Zwei Präferenzen für jeden Operator:
Zeichen
EingabePräf.
Stapelpräferenz
(
100
0
)
0
99
*
3
4
/
3
4
+
1
2
1
2
Höhere Stapel- als Eingabepräferenz : Linksassoziativität
sonst rechtsassoziativ.
Beipiel: 3 * 4 / 6 -> 3 4 * 6 /
hs / fub – alp3 –ADT-3 11
Programmentwurf
Naiv:
Main
eval
PostFixEval
push, pop,..
DoubleStack
Nachteile:
- DoubleStack als Reimplementierung des
(Object) Stack !
- EINE Implementierung, Änderung erzwingt Änderung
des Klienten (PostFixEval).
hs / fub – alp3 –ADT-3 12
6
class PostFixEval {
...
DoubleStack ds = new DoubleStack();
...
}
class DoubleStack {
// hier werden alle Stackoperationen
nacherfunden!
...
}
Programmentwurf
Lösung
des ersten Teilproblems: Adapterpattern
Main
eval
PostFixEval pushD(), .. topAndPop()«interface»
DoubleStack
MyStackImp
push(), pop(),..
DoubleStack
Besser: Keine Reimplementierung sondern Nutzung
von Stack-Operationen
hs / fub – alp3 –ADT-3 14
7
class DoubleStack implements DoubleStackIF{
...
MyStackImpl s = new MyStackImpl();
}
class MyStackImpl {
// Implementierung ...
// aber Datenabstraktion mit ADT??
}
hs / fub – alp3 –ADT-3 15
Programmentwurf
Main
eval
Entkoppelung von
Schnittstelle und
Implementierung:
Klient von class Stack
kennt nur Schnittstelle.
PostFixEval pushD(), .. topAndPop()
«interface»
DoubleStack
«interface»
Stack
DoubleStack
push(), pop(),..
ArrayStack
hs / fub – alp3 –ADT-3 16
8
class DoubleStack implements DoubleStackIF{
...
protected Stack s = new ArrayStack ();
......
}
Was wenn mehr
als eine
Stackimplementierung?
Stackimplementierung?
interface Stack {
public void push(){..
...
}
class ArrayStack implements Stack {
// Implementierung ...
// aber Datenabstraktion mit ADT??
}
Mehrere Implementierungen
Main
eval
Entkoppelung von
Schnittstelle und
Implementierung:
Klient von class Stack
kennt nur Schnittstelle.
ArrayStack
PostFixEval pushD(), .. topAndPop() «interface»
DoubleStack
«interface»
Stack
push(), pop(),..
DoubleStack
LListStack
hs / fub – alp3 –ADT-3 18
9
Programmentwurf: Objektfabrik
class DoubleStack implements DoubleStackIF{
...
protected Stack s = new ArrayStack();
......}
LListStack()
Idee:
Keine direkte Verwendung von Konstruktoren der
implementierenden Klassen.
Stattdessen Klasse zur Objekterzeugung
(Objektfabrik) mit einheitlicher Schnittstelle, z.B.
public Stack getStack()
hs / fub – alp3 –ADT-3 19
Programmentwurf: Objektfabrik
Main
eval
PostFixEval pushD(), .. topAndPop() «interface»
DoubleStack
StackFactory
«interface»
Stack
getStack()
new
DoubleStack
push(), .. pop()
ArrayStack
LListStack
StackFactory ist zu
ändern, wenn andere
StackStack-Implementierung
verwendet werden soll
hs / fub – alp3 –ADT-3 20
10
Nutzung der Objektfabrik
class DoubleStack implements DoubleStackIF{
...
protected Stack s
= (new StackFactory().getStack());
......
}
public class StackFactory {
protected final int ARRAYSTACK = 1; // zum Beispiel
protected final int LLISTSTACK = 2;
int whichOne = ARRAYSTACK;
public StackFactory(int which) {whichOne = which;}
public Stack getStack() {
if (whichOne = ARRAYSTACK) return (new StackArray());
if (whichOne = LLISTSTACK) return (new LListArray());
}
}
hs / fub – alp3 –ADT-3 21
Vereinfachung: statische Fabrikmethode
Main
abstract
Stack
eval
PostFixEval pushD(), .. topAndPop() «interface»
DoubleStack
new getStack() push(), .. pop()
DoubleStack
static
getStack()
ArrayStack
LListStack
statische Factory
Methode ist zu ändern,
wenn andere StackStackImplementierung
verwendet
werden soll
hs / fub – alp3 –ADT-3 22
11
Vereinfachung: statische Fabrikmethode
class DoubleStack implements DoubleStackIF{
...
protected Stack s
= Stack.getStack());
......
}
abstract class Stack {
.....
public abstract void pop() throws Underflow;;
....
public static Stack getStack(){
return (new StackArray());
}
// or which kind of stack implementation
// you want
}
hs / fub – alp3 –ADT-3 23
12