Stacks



  • Hi @ all! 🙂

    Folgendes Problem sei gegeben: Man hat 3 Geleise, Geleis 1 mit den Zugwagen BABA, Gleis 2 mit AAB und Gleis 3, das leer ist.
    Ziel ist es, dass alle A-Wagen auf Gleis 1 und alle B-Wagen auf Gleis 2 zu stehen kommen. Dabei habe ich jeden Zug in einen Stack gesteckt (d.h. der Wagen ganz links ist "zuoberst").

    Ich habe das - wie gesagt - mit Stacks gelöst. Allerdings animiere ich den Benutzer zur Hirnbetätigung, denn ich hab es so implementiert, dass der Benutzer sagen kann, welchen Wagen er wohni verschieben will.
    Meine Frage ist nun: Wie sähe der Code aus, wenn der Computer diese Arbeit übernehmen solle?

    Hier mein Code, der im Wesentlichen hieraus besteht:

    #include <stack>
    #include <iostream>
    #include <cstdlib>
    #include "wagon.hpp"
    
    int main()
    {
        std::stack<wagon> rail_one;
        rail_one.push( wagon(A) );
        rail_one.push( wagon(B) );
        rail_one.push( wagon(A) );
        rail_one.push( wagon(B) );
    
        std::stack<wagon> rail_two;
        rail_two.push( wagon(B) );
        rail_two.push( wagon(A) );
        rail_two.push( wagon(A) );
    
        std::stack<wagon> rail_three;
    
        /* Hier habe ich meine Abfragen wie Element wegnehmen etc. implementiert.
         Da der Benutzer ins Geschehen eingreifen muss, frage ich mich, ob es nicht möglich ist, dass der Computer diese Arbeiten übernimmt? (wäre auf jeden Fall eine Produktivitätssteigerung :P */
    
        // Ueberpruefung des Resultats
        std::cout << "Checking wagons arrangement.." << std::endl;
    
        if( rail_one.size() <= 0 || rail_two.size() <= 0 )
        {
            std::cerr << "Error: rail 1 and 2 both need to contain some wagons." << std::endl;
            abort();
        }
    
        while( rail_one.size() > 0)
        {
            if(rail_one.top().appointed_train() != A)
            {
                std::cerr << "Error: wagon of train B on rail one." << std::endl;
                abort();
            }
    
            rail_one.pop();
        }
    
        while( rail_two.size() > 0)
        {
            if(rail_two.top().appointed_train() != B)
            {
                std::cerr << "Error: wagon of train A on rail two." << std::endl;
                abort();
            }
    
            rail_two.pop();
        }
    
        if( rail_three.size() > 0 )
        {
            std::cerr << "Error: rail three should be empty." << std::endl;
            abort();
        }
    
        std::cout << "Wagons correctly arranged." << std::endl;
    
        return 0;
    }
    

    Vorschläge jeglicher Art sind sehr willkommen.
    Liebe Grüsse, Sonja



  • Auf die schnelle:
    1. Schaue ob am Ende vom Zug auf Gleis 1 ein B-Waggon ist.
    Wenn ja, dann pack den Waggon auf Gleis 3.
    Wenn nein, dann pack den Waggon auf Gleis 2.
    Das wiederholt man solange bis das Gleis 1 Leer ist(oder der einzige Waggon darauf A ist.)

    2. Schaue ob am Ende vom Zug auf Gleis 2 ein A-Waggon ist.
    Wenn ja, dann pack den Waggon auf Gleis 1.
    Wenn nein, dann pack den Waggon auf Gleis 3.
    Das wiederholt man solange bis das Gleis 2 Leer ist(oder der einzige Waggon darauf B ist.)

    3. Packe alles von Gleis 3 auf Gleis 1.

    Das ganze funktioniert wenn Gleis 3 Garantiert am anfang leer ist! Ansonsten müsste man den Punkt 3. noch anpassen. Für dein Beispiel würde das dann so ablaufen:

    ####Erster Teil####
    1: ABAB
    2: BAA
    3: 
    
    1: ABA
    2: BAA
    3: B
    
    1: AB
    2: BAAA
    3: B
    
    1: A
    2: BAAA
    3: BB
    
    1: 
    2: BAAAA
    3: BB
    
    ####Zweiter Teil####
    
    1: A
    2: BAAA
    3: BB
    
    1: AA
    2: BAA
    3: BB
    
    1: AAA
    2: BA
    3: BB
    
    1: AAAA
    2: B
    3: BB
    
    1: AAAA
    2: 
    3: BBB
    
    ####Dritter Teil####
    1: AAAA
    2: B
    3: BB
    
    1: AAAA
    2: BB
    3: B
    
    1: AAAA
    2: BBB
    3:
    

    Ich hoffe ich hab kein Fehler gemacht, ist schon spät :p



  • Ich frage dies nun auch "auf die Schnelle", da ich momentan an einem PC bin, der kein Visual Basic hat.
    Mit "Ende vom Zug" - meinst du da die top()-Methode, oder?

    Also das heisst für den ersten Absatz (wie gesagt, ich habe die folgenden Zeilen ohne C++-Editor geschrieben 😉 )

    while(!rail_one.empty())
    {
    if(rail_one.top().appointed_train() = B)
    {
    rail_three.push(rail_one.top());
    rail_one.pop(rail_one.top());
    }
    
    else
    {
    rail_two.push(rail_one.top());
    rail_one.pop(rail_one.top());
    }
    }
    

    Kann das sein?



  • Ja. So sollte das dann gehen.
    Die Zeile

    rail_one.pop(rail_one.top());
    

    wird im if und im else Zweig aufgerufen, kann also "Ausgeklammert" werden, sprich dahinter geschrieben werden.



  • Hab ich übersehen, im if muss natürlich ein "==" rein und kein "=".



  • Ah genau. Du hast recht. Jetzt, wo ich wieder an einem C++-Editor bin, werden diese beiden Zeilen sogar unterwellt. Guter Editor 🙂

    ..eine Reklamation hat er noch: Bei

    rail_one.pop(rail_one.top());
    

    hat es ihm zu viele Argumente im Funktionsaufruf. Wie kann man dem entgegenwirken?



  • indem du dem parameter weg lässt 😉 AFAIK liefert pop das oberste element vom stack. Und das möchtest du doch oder?



  • Oki doki. You're right.

    Ich habe also den folgenden Code:

    while(!rail_one.empty())
    	{
    	if(rail_one.top().appointed_train() == B)
    	{
    		rail_three.push(rail_one.top());
    	}
    
    	else
    	{
    		rail_two.push(rail_one.top());
    
    	}
    
    	rail_one.pop();
    	}
    
    	while(!rail_two.empty())
    	{
    	if(rail_two.top().appointed_train() == A)
    	{
    		rail_one.push(rail_two.top());
    	}
    
    	else
    	{
    		rail_three.push(rail_two.top());
    	}
    
    	rail_two.pop();
    	}
    
    	for(int i = 0; i<rail_three.size() + 1; i++)
    	{
    		rail_one.push(rail_three.top());
    		rail_three.pop();
    		i++;
    	}
    

    Kann es sein, dass mir irgendwo 'nen Fehler eingeschlichen ist?
    Weil mein Überprüfungs-Code sagt gibt die erste "Fehlermeldung" an, also dass Rail 1 und Rail 2 Wagen benötigen.



  • Es gibt zwei Stellen die Fehlerhaft sind.
    1. Die Anleitung von mir in Punkt 3 ist fehlerhaft.
    Man sollte natürlich von Gleis 3 auf Gleis 2 Packen und nicht auf Gleis 1.

    2. Diese For-Schleife hier solltest du nochmal begutachten:

    for(int i = 0; i<rail_three.size() + 1; i++) //erstes hochzählen von i
        {
            rail_one.push(rail_three.top());
            rail_three.pop(); //Hier ändert sich .size() von dem Stack
            i++; //zweites hochzählen von i
        }
    

    Dort zählst du i 2 mal hoch.
    Zudem ändert sich rail_three.size() mit jedem Durchlauf der Schleife.
    D.h. du kannst entweder mit einer while-Schleife solange fortfahren bis rail_three leer ist oder du speicherst dir rail_three.size() in eine Variable vor einer For- Schleife.



  • Programmierst du mit Visual Studio?
    Weist du schon wie man den Debugger verwendet?

    Der Debugger ist unheimlich hilfreich bei solchen Problemchen. Denn dort kannst du live mitverfolgen was passiert. Dann sieht man auch schnell, dass Gleis 1 zugestellt wurde statt Gleis 2. Und bei der Fehlermeldung sieht man dann auch das Gleis 2 leer gewesen ist.



  • Ah, du hast Recht!
    Nun funktioniert alles einwandfrei.
    Klar, Gleis 2 war ja die längste Zeit (also nach der ersten while-Schlaufe) leer. Sorry, das hätte ich auch sehen müssen...

    Genau, ich programmiere mit Visual Studio. Meistens lass ich den Code kompilieren und schau dann, was der Compiler sagt (auch sehr nützlich, das meistens die Zeilennummer auch gerade angegeben wird).
    Mit dem Debugger hab ich auch schon hantiert, aber irgendwie fand ich die Compiler-Meldungen etwas effektiver...

    Besten Dank für die Hilfe beim Verstehen des Problems!


Anmelden zum Antworten