Problem mit Stack

[stud]

Hallo,

ich habe folgendes Problem. Ich habe folgende Aufgabe zu lösen:

ergänze folgendes Programmfragment damit die Eingabe (154326) geordnet ausgegeben werden kann (123456).

INIT(S), i=0

Solange (i<Laenge(L)):

{

Solange ((nicht EMPTY(S)) und (.......)): { Ausgabe(TOP(S)), POP(S) }

PUSH(S,L)

i=i+1

}

Solange (nicht EMPTY(S)): { Ausgabe(TOP(S), POP(S)) }

Ende

Jetzt habe ich mir gedacht, dass ich statt ...... überprüfe ob L > TOP(S) ist, wenn dass der Fall ist soll die Spitzenzahl ausgegeben werden und anschließend gelöscht werden. Wenn nicht führt das Programm dann die Funktion PUSH aus und fügt das Element als oberstes ein.

Das dürfte für die Eingabe auch so weit funktionieren, allerdings bin auf das Problem gestoßen, dass PUSH den Wert den es oben einfügt ja unten nicht löscht und dieser Wert somit 2mal vorhanden ist, sodass eine Ausgabe wie gefordert gar nicht möglich ist, oder habe ich irgendeinen Denkfehler?

Ich bitte daher um eure Meinung zu dem Problem.

Vielen Dank.

[RipperFox]

mh..

Normalerweise sortiert man etwas mittels Rekursion, die von Dir gebrachte Aufgabe durchläuft aber nur einmal den String und ein einfacher Vergleich wird somit nur einmal durchgeführt.

Die Aufgabe ist mir suspekt. Tippfehler ausgeschlossen?

Grüße

Ripper

[stud]

du hast schon recht. Die Aufgabe geht ja auch noch weiter, dass man in nachfolgenden Aufgabenteilen genau das herausfindet, das die Sortiermethode nicht überall anwendbar ist. Es soll ja auch nur die Vorgegebene Eingabe richtig sortiert werden.

Nur wie ich schon oben erwähnt hatte, die PUSH methode löscht doch an sich das Objekt nicht, oder doch?

[RipperFox]

nein, PUSH legt nur etwas auf den Stack und löscht nix.

Die Ausgabe "{ Ausgabe(TOP(S)), POP(S) }" in "Solange ((nicht EMPTY(S)) und (.......)): { Ausgabe(TOP(S)), POP(S) }" scheint mir auch widersinnig.

Wo gibt's denn die komplette Aufgabe?

Grüße Ripper

[stud]

hier die komplette Aufgabe:

Beim Umzug eines Informatik-Instituts ist eines der Programme beschädigt worden. Glücklicherweise

ist nur an einer Stelle (.......) der Ausdruck für eine Bedingung verlorengangen. Das

Programm sieht nun so aus:

INIT(S), i=0

Solange (i<Laenge(L)):

{

Solange ((nicht EMPTY(S)) und (.......)): { Ausgabe(TOP(S)), POP(S) }

PUSH(S,L)

i=i+1

}

Solange (nicht EMPTY(S)): { Ausgabe(TOP(S), POP(S)) }

Ende

(a) Welche Bedingung steht sinnvollerweise statt ......., damit das Programm die Elemente

aus der Eingabe möglichst gut in aufsteigender Reihenfolge sortiert ausgibt? Insbesondere soll das reparierte Programm bei Eingabe von (5,4,3,2,1) als Ausgabe (1,2,3,4,5) liefern. Auf (1,5,4,3,2,6) soll mit (1,2,3,4,5,6) geantwortet werden. Zeigen Sie, wie das reparierte Programm auf diesen zwei Beispielen arbeitet, indem Sie den Stapel direkt vor und direkt nach jedem PUSH explizit angeben.

( Geben Sie eine möglichst kurze Liste an, die vom Programm nicht korrekt sortiert wird.

Sehe ich es dann richtig, dass die Aufgabe gar nicht lösbar ist, sobald PUSH einmal ausgeführt worden ist, da ja dann eine Zahl doppelt da ist?

Grüße

stud

[Klotzkopp]

Sehe ich es dann richtig, dass die Aufgabe gar nicht lösbar ist, sobald PUSH einmal ausgeführt worden ist, da ja dann eine Zahl doppelt da ist?

Nein, jedes Element der Eingabe L wird in den Stack gepackt, und jedes Element, das im Stack ist, wird genau einmal wieder ausgegeben. Entscheidend ist nur die Reihenfolge.

Die Frage an der Stelle ist doch, ob du die aktuell zu verarbeitende Eingabe einfach nur auf den Stack packst, oder ob du vorher zusätzlich einen Teil des Stacks abbaust und ausgibst.

[stud]

Da ich davon ausgehe dass der Programmcode vollständig ist, gibt es nur eine Möglichkeit ein Element vorher abzubauen, in der eingekapselten "Solange" Schleife, mit TOP(S).

Ich setze also statt den Punkten die Bedingung L > TOP(S) ein. Da laut der zweiten Eingabe die 1 ja ganz unten drunter steht, muss sie zu erst ausgegeben werden. Dies geschieht über den Befehl PUSH(S,L). Danach steht die 1 oben und kann beim nächsten Schleifendurchlauf ausgegeben werden. Dies funktioniert mit den übrigen Zahlen ähnlich, bis ich unten auf dem Stack angekommen bin, denn dort steht ja immer noch die 1, da ich sie ja nur nach oben kopiert habe. Demzufolge kann ich die erforderte Ausgabe ja gar nicht erreichen, da sie ungefär so lauten würde: (1,2,3,4,5,6,2,3,4,5,1), wenn ich Anweisung komplett ausführe, oder gibt es irgendeinen anderen Weg, wie ich die geforderte Ausgabe erreiche?

D.h. kann ich statt den Punkten auch eine andere Bedingung einsetzen, damit es funktioniert?

[Klotzkopp]

Da laut der zweiten Eingabe die 1 ja ganz unten drunter steht, muss sie zu erst ausgegeben werden. Dies geschieht über den Befehl PUSH(S,L).

PUSH bewirkt keine Ausgabe. PUSH packt nur eine Zahl auf den Stack.

Danach steht die 1 oben und kann beim nächsten Schleifendurchlauf ausgegeben werden. Dies funktioniert mit den übrigen Zahlen ähnlich, bis ich unten auf dem Stack angekommen bin, denn dort steht ja immer noch die 1, da ich sie ja nur nach oben kopiert habe.

Ich kann nicht ganz nachvollziehen, was du mit "unten" und "oben" meinst.

Bei der zweiten Beispieleingabe wird die 1, die im ersten Durchlauf auf den Stack gepackt wurde, schon bei der 5 wieder vom Stack runtergeholt und ausgegeben. Danach ist der Stack zunächst wieder leer.

Demzufolge kann ich die erforderte Ausgabe ja gar nicht erreichen, da sie ungefär so lauten würde: (1,2,3,4,5,6,2,3,4,5,1), wenn ich Anweisung komplett ausführe, oder gibt es irgendeinen anderen Weg, wie ich die geforderte Ausgabe erreiche?

Kann es sein, dass du das erste POP ignorierst? Wenn du die 6 ausgegeben hast, ist der Stack leer.

[stud]

ich stelle mir die Eingabe wie folgt vor: Die Zahlen werden eingegeben und so sieht der Stack dann aus:

6

2

3

4

5

1

wobei 1 die unterste Zahl ist, da zuerst eingegeben.

Jetzt gelangt man in die erste Solange schleife und danach gleich in die zweite. Jetzt prüft das Programm, ob 1 > 6 ist, wenn nein kopiert(PUSH) es die 1 nach "oben" sodass der Stack so aussieht:

1

6

2

3

4

5

1.

Jetzt läuft die Solangeschleife das zweite mal durch und prüft ob 5 > 1, da das Wahr ist, wird die obere 1 (TOP) ausgelesen und mit POP gelöscht, danach prüft es ob die 5>6, da das falsch ist kopiert es die 5 auf den Stack (PUSH) usw.

Das geht solange bis ich bei der 6 bin und diese ausgegeben habe, dann ist i einmal durchgelaufen und ich habe die Zahlen sortiert erhalten. (1,2,3,4,5,6)

Danach kommt allerdings noch die 3. Solange Anweisung und gibt mir den kompletten Restl. Stapel noch aus, was zu der Ausgabe 2,3,4,5,1 führen würde. Genau das müsste ich ja umgehen um nur die Ausgabe 1,2,3,4,5,6 zu erhalten.

Hier weis ich nicht wie das geht bzw. ob es geht, wenn ich nur die Bedingung ändern kann????

Ich nehme daher an das Programm kann man gar nicht richtig für die zweite Ausgabe ausführen, die erste funktioniert ja problemlos.

Kann es sein, dass du das erste POP ignorierst? Wenn du die 6 ausgegeben hast, ist der Stack leer.

Außerdem löscht POP ja nicht den ganzen Stapel sondern nur das oberste Element.

Grüße

stud

[Klotzkopp]

ich stelle mir die Eingabe wie folgt vor: Die Zahlen werden eingegeben und so sieht der Stack dann aus:

6

2

3

4

5

1

Du scheinst der Meinung zu sein, dass irgendwie die Eingabe vor der Ausführung des Programms auf den Stack gelegt wird. Das ist nicht der Fall. Die Eingabe liegt im Array L, der Stack ist leer.

[stud]

Das erklärt natürlich einiges, ich bin davon ausgegangen, dass die Eingabe direkt auf dem Stack liegt.

Ich habs doch geahnt, dass ich da irgendeinen Denkfehler habe.

Vielen Dank.

Damit ist die Aufgabe gar nicht so schwer.

Grüße

stud