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!


Log in to reply