Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Aufgabenblatt 10
Servus,
kann mir jemand vielleicht nen kleinen Tipp geben, wie ich die in Aufgabe 3-2 geforderte queue mittels zweier stacks implementiere? Wahrscheinlich liegt die Lösung auf der Hand, aber meine kleinen grauen Zellen sind trotzdem noch nicht drauf gekommen…
is gar net so schwer:
du schiebst einfach immer das oberste element des ersten stacks auf den zweiten. damit drehst du den stack quasi um. dann kannst du das oberste (vorher wars ja das unterste) element entfernen, und verschiebst die restlichen elemente wieder in den ersten stack, damit die ursprüngliche reihenfolge wiederhergestellt ist.
das wars dann auch schon.
also ich habs so gemacht.
du erstellst 2 stacks einen für die queue (stack 1) und den andern als temporären auslagerungsstack (stack 2). wenn beide stacks leer sind is ja alles easy. packst das neue element einfach in stack 1. sobald sich aber schon elemente in stack 1 befinden lagerst du diese einfach in den stack 2 aus, eins nach dem andern bis stack 1 leer ist. somit hast du in stack 2 alle ehemaligen elemente von stack 1 in umgekehrter reihenfolge. nun packst du das neue element in den stack 1 und schaufelst wieder alle objekte von stack 2 zurück in stack 1 und fertig bist du (zumindest was die push funktion betrifft, der rest is aber ganz einfach). das is zumindest meine lösung, vielleicht gibts ja noch was besseres, aber das funktioniert!
ich seh auch nur diese beiden lösungen:
entweder man hält sich in seinem “main” stack immer das erste element (was als nächstes an der reihe ist) ganz unten, dann kostet enq() konstanten aufwand / nix, man schmeissts einfach oben aufn stack, jedoch front() oder deq() jeweils 2n umschaufelungen (hin und zurück)
oder man hält sich das erste element ganz oben, dann is front() u. deq() umsonst, einfach runterpopen, jedoch für enq() muss man dann au 2n mal rumschaufeln…
gibt’s noch ne andere (bessere?) lösung?
grad vorhin noch ne mind. doppelt so gute lösung eingefallen, wenn man beide stacks gleichzeitig benutzt und versetzt immer einsortiert, wobei die elemente die als nächstes an der reihe sind jeweils oben auf den beiden stacks liegen… so mit hat man für front/deq au kosten 0, enq kostet dann nur noch floor(n/2) * 2 verschiebungen
dürfen wir bei der aufgabe jetzt eigtl mal die klassen selber frei benennen? (oder hat er des nur wieder vergessen hinzuschreiben)
kann mir vielleicht jemand einen tipp geben wie ich die aufgabe mit dem parser angehen könnte? irgendwie hab ich so garkeine vorstellung, wie ich das machen soll.
ich hab die methoden für die terminale geschrieben und einfach mal nach muster der gegebenen methode aufgebaut… aber wie fange ich eigentlich an, den string, der mir im konstrukor übergeben wird, zu parsen?
mensch stephan, du checkst aber auch garnix g
Mach dir für jedes Nichtterminalsymbol eine Methode. (Plus die angegebenen Methoden auf dem Übungsblatt)
Jede Methode bekommt als int Parameter den Punkt im String wo diese Methode das parsen beginnen soll und liefert wieder den Wert zurück wo sie aufgehört hat zu parsen.
Diese Position brauchst du um mit der Methode String.charAt(aktuelleposition) auf den String der geparst werden soll zuzugreifen. Die Methode verhält sich so als wäre der String ein Array mit den einzelnen Zeichen als ein Element pro Zelle. Auf den String “Hallo” Kannste mit String.charAt(0) auf das ‘H’ zugreifen usw.
Im Grunde sind alle Methoden ziemlich gleich aufgebaut … wirst dann schon merken fang einfach mal an
@Mercury
danke! 
irgendwie konnt ich’s mir einfach nicht vorstellen wie das funktionieren soll. ich denk, die vorherige aufgabe mit dem keller hat mich verwirrt… 
@Janoschka
mal schauen ob du’s sonntag abend um 23 Uhr checkst
AHHHHHH!!! ich muss hier mal eben meine unglaubliche blödheit kundtun:
ich hab jetzt bestimmt eine halbe stunde lang meinen MiniParser mit irgendwelchen debug-Statements zugemüllt weil er bei
44+33
immer “false” zurück gegen hat! und als ich dann endlich wirklich in jeder methode irgendein “System.out … bla bla” hatte hab ich bemerkt das ich bei ValueFloat den case ‘4’: vergessen habe :wand: :wand: :wand: :wand: :wand: :wand: ARGL! murphys law sag ich da nur!!!
Achtung!
Schaut mal auf die Algo Seite, dort gibt es eine neue Version von value_float, weil bei der alten nicht berücksichtigt wird ob ein weiterer Punkt eingelesen wird.
Meiner Meinung nach ist des Teil aber immernoch fehlerhaft!
Also ich habs bei mir etwas abgeändert und des funktioniert jetzt … des vom Bernd Ludwig hab ich entweder net verstanden oder es ist wirklich ein Fehler drinen: Alle denen es hilft können ja das hier verwenden:
private int value_float( int pos ) throws Exception{
String floatVal;
int startpos;
boolean dotRead;
printIndent( pos, "value_float" );
dotRead = false;
startpos = pos;
floatVal = "";
while( startpos < input.length() ) {
switch( input.charAt( startpos ) ) {
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
floatVal += input.charAt( startpos );
startpos++;
continue;
case '.':
if (dotRead) {
throw new Exception("Illegal Number Format!");
} else {
dotRead = true;
floatVal += input.charAt( startpos );
startpos++;
} continue;
default:
break;
}
break;
}
return startpos;
}
In der Methode vom Bernd ist immer noch ein Fehler drin würde ich sagen. Er nimmt beim jetzigen Stand bei jeder Ziffer an, dass ein ‘.’ gelesen wurde… Irgendwie ja nicht ganz Sinn der Sache.
Du kannst dir das Leben auch noch einfacher machen:
private int value_float(int pos) {
String floatVal;
int startpos;
boolean dotRead;
printIndent(pos, "value_float");
dotRead = false;
startpos = pos;
floatVal = "";
while (startpos < input.length()) {
switch (input.charAt(startpos)) {
case '.':
if (dotRead) return startpos; // error if more than one dot.
dotRead = true;
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
floatVal += input.charAt(startpos);
startpos++;
continue;
default:
return startpos; // error: char illegal for float
}
} // while
return startpos;
} // sym_floatBtw, hat sich irgend jemand die Mühe gemacht, Whitespace weg zu parsen? Hab’s mir überlegt ob ich’s machen soll, hab aber keine Lust gerade. :-p
Whitespace wegparsen? Bist du des wahnsinns? Das wär dann doch zuviel des Guten! 
Mir ist nochwas aufgefallen:
- wenn ich 0. als Zahl eingebe bringt er keinen Fehler
- wenn ich .0 eingebe auch net. wär aber sinnvoll denk ich.
- Ach ja wenn gar keine Nummer eingelesen wird wird auch kein Fehler gemeldet! … Also noch ändern …
Hat jemand den Aufwandsvergleich für die Queues schon gemacht?
Hm… stimmt. Ich hab noch keine ungültigen Eingaben ausprobiert.
Das schaut aber gar nicht so trivial aus, alle möglichen ungültigen Eingaben für Floats abzufangen… zumindest wenn man’s sauber machen will.
.0 abzufangen ist ja kein Problem.
0. abzufangen ist auch kein Problem wenn man im default-Teil einfach das letzte Zeichen von floatVal überprüft.
Aber die Fälle mit ungültigen Zahlen (sprich Buchstaben) gefallen mir nicht.
Probier z.B. mal
1a3+24
1.a3+24
Ich hab das jetzt so gelöst dass ich beim Verlassen der Methode einfach mit Float.parseFloat überprüfe, ob floatVal überhaupt eine Zahl ist. Aber das ist ja mehr als ein dirty hack…
Hmmm also bei mir kommen da Fehlermeldungen:
(2d3.9+45.322.0)54.89+3.065.5
expression
term
factor
expression
term
factor
value_float
Fehler!
java.lang.Exception: (in term) Missing Token! Exspected ‘*’ found: d
ERROR - stopped parsing due to errrors
Meine value_float sieht etz so aus:
private int value_float( int pos ) throws Exception{
String floatVal;
int startpos;
int point = 0;
int nonumber = 0;
boolean dotRead;
printIndent( pos, "value_float" );
dotRead = false;
startpos = pos;
floatVal = "";
while( startpos < input.length() ) {
switch( input.charAt( startpos ) ) {
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
if ( point == 1) point++;
floatVal += input.charAt( startpos );
startpos++;
nonumber++;
continue;
case '.':
//ueberpruefe ob bereits ein Punkt eingelesen wurde
if ( dotRead || nonumber==0 ) {
throw new Exception("Illegal Number Format!");
} else {
dotRead = true;
point = 1;
floatVal += input.charAt( startpos );
startpos++;
} continue;
default:
//Wirft Exception wenn nach einem Punkt keine Zahl mehr kommt
if (point ==1) throw new Exception("Illegal Number Format!");
//Wirft Exception wenn gar keine Zahl kam
else if (nonumber == 0) throw new Exception("Missing Number!");
break;
}
break;
}
return startpos;
}
Hm… ich hab gerade fest gestellt, dass das überflüssiger Code war. Ich hatte vorher ein anderes Problem in der .parse(), weswegen ungültige Eingaben akzeptiert wurden. Das hab ich zwischendrin behoben und jetzt funktioniert die Überprüfung auf korrekte Zahlenwerte automatisch quasi geschenkt. 
Interessantes Phänomen… Ich hab gerade mal versucht, das zu implementieren. Gar nicht so einfach, die Schlange korrekt zu implementieren, wenn du ungeradzahlige n oder nicht volle Schlangen hast. Aber jetzt probier mal folgendes:
Queue1 schlange = new Queue1(7);
schlange.enq(1);
schlange.enq(2);
schlange.enq(3);
schlange.enq(4);
schlange.enq(5);
schlange.enq(6);
schlange.enq(7);
schlange.deq(); schlange.deq(); schlange.deq();
schlange.enq(8); schlange.enq(9); schlange.enq(10);
while (!schlange.empty()) {
System.out.println(schlange.front());
schlange.deq();
}Was passiert? Wenn’s funktioniert, würde mich interessieren wie du das gelöst hast. 