import java.util.HashSet;
import java.util.Arrays;
/**
 * Abstract class Kellerautomat - Geruest fuer konkrete Kellerautomaten
 * Alle Kellerautomaten starten im Zustand 1.
 *
 * @author MB
 * @version NOV 2021
 */
public abstract class Kellerautomat
{
    protected Keller keller;
    protected Integer zustand;
    protected HashSet<Integer> endzustaende;
   
    public Kellerautomat(Integer[] endzustaende){
         zustand = 1;
         keller = new Keller();
         this.endzustaende = new HashSet<Integer>(Arrays.asList(endzustaende));
    }
    
    /**
     * Zentrale Methode der Verarbeitung.
     * @param eingabe - die Eingabe, die zeichenweise verarbeitet wird
     * @return - ob die Eingabe zur Sprache des Automaten gehoert
     */
    public boolean eingabeUntersuchen(String eingabe){
        boolean akzeptiert = false;
        for (int i = 0; i < eingabe.length(); i++){
            System.out.print("In Zustand: " + zustand);
            zustandWechseln(eingabe.charAt(i));
            System.out.println(" wird untersucht " + eingabe.charAt(i) + 
                " mit neuem Zustand: " + zustand + ".");
            keller.ausgeben();    
            try{
                 Thread.sleep(2000);   
            }
            catch(Exception e){
                 e.printStackTrace();   
            }
        }
        // der Automat muss nicht nur in einem Akzeptanzzustand sein, auch der Keller muss leer sein
        if (endzustaende.contains(zustand) && keller.istLeer()){
            akzeptiert = true;
            System.out.println("Die Eingabe ist ein Wort der Sprache des Automaten.");
        }
        // Zuruecksetzen des Automaten
        zustand = 1; 
        keller.leeren();
        return akzeptiert;
    }
    
    protected abstract void zustandWechseln(char eingabe);
    
    
    
}
class Keller
{
    protected int anzahl;
    protected Knoten erster;

    /**
     * Constructor
     */
    public Keller()
    {
       anzahl = 0;
       erster = null;
    }

    public void ausgeben(){
        Knoten k = erster;
        System.out.print("Keller: ");
        for(int i = 0; i < anzahl; i++){ // wenn [anzahl == 0], passiert nichts
            System.out.print(k.gibInhalt() + " ");
            k = k.gibNaechsten();
        }
        System.out.println();
    }
    
    public boolean istLeer(){
         return (anzahl == 0);   
    }
    
     public void leeren(){
        erster = null;
        anzahl = 0;
    }
    
    public Character pop(){
        if(anzahl == 0){
            System.err.println("Der Stapel ist leer");
            return null;
        }
        else if (anzahl == 1){
            Knoten output = erster;
            erster = null;
            anzahl = 0;
            return output.gibInhalt();
        }
        else{
            Knoten output = erster;
            erster = erster.gibNaechsten();
            anzahl--;
            return output.gibInhalt();
        }
    }
    
    public void push(Character neu){
        if(anzahl == 0){
            erster = new Knoten(neu);
            erster.setzeNaechsten(null); // fuer den Fall, dass der Knoten noch einen Verweis hatte; sonst werden zwei eingefuegt
        }
        else{
            Knoten k = new Knoten(neu);
            k.setzeNaechsten(erster);
            erster = k;
        }
        anzahl++;
    }
    
    public Character top(){
        if(anzahl > 0){
            return erster.gibInhalt();
        }
        return null;
    }  
}
class Knoten
{
    protected final Character inhalt;  // der Inhalt eines Knoten wird nicht geaendert, eher der Knoten ausgeschnitten
    protected Knoten naechster;

    /**
     * Constructor 
     */
    public Knoten(Character inhalt)
    {
        this.inhalt = inhalt;
        naechster = null;
    }

    public Knoten(Character inhalt, Knoten naechster){
        this(inhalt); // zuerst wird der Basiskonstruktor ausgefuehrt
        this.naechster = naechster;
    }
    
    public Character gibInhalt(){
        return inhalt;
    }
    
    public Knoten gibNaechsten(){
        return naechster;
    }
    
    public void setzeNaechsten(Knoten naechster){
        this.naechster = naechster;
    }
    
    
}