Gruppe und Namen der Mitglieder

Punkte:

Total

Übung Stapelspeicher (04)

In dieser Übung sollen zwei Ziele erreicht werden:

Den ADT Stack als Java Klasse implementieren;
Lösen eines komplexeren Problems mit einer einfachen VM.

Ausgabe : 28.11.2025

Abgabe : 8.12.2025

Grundlagen

Aufgabe 1. Welchen Eigenschaften besitzen lineare Tabellen (Arrays)?

Anpassbare Programmierung

Optimale Speichergröße für jedes Problem

Einfache Implementierung mit der Programmiersprache

Der Index ist ein Schlüssel zu einem Datensatz

Jede Schlüsselmenge kann mit linearen Tabellen effizient umgesetzt werden

Die Suche mit dem Index als Schlüssel dauert ca. O(N)

Die Suche mit dem Index als Schlüssel dauert ca. O(1)

Ein Stapelspeicher basiert auf einer lienaren Tabelle

Lösung.

Anpassbare Programmierung

Optimale Speichergröße für jedes Problem

Einfache Implementierung mit der Programmiersprache

Der Index ist ein Schlüssel zu einem Datensatz

Jede Schlüsselmenge kann mit linearen Tabellen effizient umgesetzt werden

Die Suche mit dem Index als Schlüssel dauert ca. O(N)

Die Suche mit dem Index als Schlüssel dauert ca. O(1)

Ein Stapelspeicher basiert auf einer lienaren Tabelle

Aufgabe 2. In einen Stack werden in der gegebenen Reihenfolge {1,2,3,4} Werte nacheinander gechrieben. In welcher Reihenfolge werden sie wieder ausgegeben?

First-in First-out {1,2,3,4}

First-in First-out {4,3,2,1}

Last-in Last-out {1,2,3,4}

Last-in First-out {4,3,2,1}

Last-in Last-out {1,4,3,2}

Lösung.

First-in First-out {1,2,3,4}

First-in First-out {4,3,2,1}

Last-in Last-out {1,2,3,4}

Last-in First-out {4,3,2,1}

Last-in Last-out {1,4,3,2}

Kommandoklasse

In dieser Übung soll die in der Vorlesung vorgestellte sehr einfache Stackmaschine nachgebaut werden. Dazu wird zuerst eine Kommandoklasse benötigt, die die einfachen Befehlsformate aus der Vorlesung nun durch Kommando Objekte ersetzt. Die VM solle aus zwei Stacks bestehen:

Daten Stack (D-Stack) für den Datentype int;
Code Stack (C-Stack) für den Datentype Command.

Wir haben wieder zwei Arten von Befehlen:

Befehle ohne Operanden mit dem Befehlscode als Zeichen new Command('+',0);
Literale als Befehl die Werte auf den D-Stack zu schieben new Command('L',1234).

Kommando Klasse (websh 0)

public class Command {
  char cmd;
  int op;
  public Command (char cmd,int op) {
    this.cmd=cmd;
    this.op=op;
  }
}

Stackspeicher

Implementiere die beiden Stack Speicherklassen DataStack für den Integer Datentyp (int) und den Codestack für den Objecttyp Command in Java Klassen.

Der D-Stack muss folgende Methoden haben:

pop
push
swap

Immer die Operation prüfen (also leerer oder voller Stack, ungültige Op usw.).

Dann der C-Stack muss folgende Methoden haben:

pop
push
run mit folgenden Befehlen: '+','-','%','.','L' (siehe Vorlesung).

Aufgabe 3. Implementiere die DataStack Klasse

DataStack Klasse

public class DataStack {
  public DataStack(int _N) {

  }
  public void push(int x) {

  }
  public int pop() {
    return 0;
  }
  public void swap() {

  }
}

Lösung.

cHVibGljIGNsYXNzIERhdGFTdGFjayB7CiAgaW50IE47CiAgaW50IGRhdGFbXTsKICBpbnQgc3A7CiAgcHVibGljIERhdGFTdGFjayhpbnQgX04pIHsKICAgIHRoaXMuTj1fTjsKICAgIHRoaXMuZGF0YT1uZXcgaW50W3RoaXMuTl07CiAgICB0aGlzLnNwPTA7CiAgfQogIHB1YmxpYyB2b2lkIHB1c2goaW50IHgpIHsKICAgIHRoaXMuZGF0YVt0aGlzLnNwXT14OwogICAgdGhpcy5zcCsrOwogIH0KICBwdWJsaWMgaW50IHBvcCgpIHsKICAgIGlmICh0aGlzLnNwPT10aGlzLk4pIHRocm93ICJFUE9QIjsKICAgIGlmICh0aGlzLnNwPT0wKSB0aHJvdyAiRVBPUCI7CiAgICBpbnQgeCA9IHRoaXMuZGF0YVt0aGlzLnNwLTFdOwogICAgdGhpcy5zcC0tOwogICAgcmV0dXJuIHg7CiAgfQogIHB1YmxpYyB2b2lkIHN3YXAoKSB7CiAgICBpZiAodGhpcy5zcDwyKSB0aHJvdyAiRVBPUCI7CiAgICBpbnQgdD10aGlzLmRhdGFbdGhpcy5zcC0xXTsKICAgIHRoaXMuZGF0YVt0aGlzLnNwLTFdPXRoaXMuZGF0YVt0aGlzLnNwLTJdOwogICAgdGhpcy5kYXRhW3RoaXMuc3AtMl09dDsKICB9Cn0=

Aufgabe 4. Implementiere die CodeStack Klasse

CodeStack Klasse

public class CodeStack {
  public CodeStack(int N) {

  }
  public void push(Command x) {

  }
  public Command pop() {
    return null;
  }
  public void run(CodeStack C,DataStack D) {
    Command next=C.pop();
  }
}

Lösung.

cHVibGljIGNsYXNzIENvZGVTdGFjayB7CiAgaW50IE47CiAgaW50IGRhdGFbXTsKICBpbnQgc3A7CiAgcHVibGljIENvZGVTdGFjayhpbnQgTikgewogICAgdGhpcy5OPU47CiAgICB0aGlzLmRhdGE9bmV3IGludFt0aGlzLk5dOwogICAgdGhpcy5zcD0wOwogIH0KICBwdWJsaWMgdm9pZCBwdXNoKENvbW1hbmQgeCkgewogICAgdGhpcy5kYXRhW3RoaXMuc3BdPXg7CiAgICB0aGlzLnNwKys7CiAgfQogIHB1YmxpYyBDb21tYW5kIHBvcCgpIHsKICAgIGlmICh0aGlzLnNwPT10aGlzLk4pIHRocm93ICJFUE9QIjsKICAgIGlmICh0aGlzLnNwPT0wKSB0aHJvdyAiRVBPUCI7CiAgICBDb21tYW5kIHggPSB0aGlzLmRhdGFbdGhpcy5zcC0xXTsKICAgIHRoaXMuc3AtLTsKICAgIHJldHVybiB4OwogIH0KICBwdWJsaWMgdm9pZCBydW4oQ29kZVN0YWNrIEMsRGF0YVN0YWNrIEQpIHsKICAgIENvbW1hbmQgbmV4dD1DLnBvcCgpOwogICAgd2hpbGUgKG5leHQuY21kIT0nLicpIHsKICAgICAgc3dpdGNoIChuZXh0LmNtZCkgewogICAgICAgIGNhc2UgJysnOgogICAgICAgICAgaW50IGE9RC5wb3AoKSwKICAgICAgICAgICAgICBiPUQucG9wKCk7CiAgICAgICAgICBELnB1c2goYStiKTsKICAgICAgICAgIGJyZWFrOwogICAgICAgIGNhc2UgJy0nOgogICAgICAgICAgaW50IGE9RC5wb3AoKSwKICAgICAgICAgICAgICBiPUQucG9wKCk7CiAgICAgICAgICBELnB1c2goYS1iKTsKICAgICAgICAgIGJyZWFrOwogICAgICAgIGNhc2UgJyUnOgogICAgICAgICAgaW50IGE9RC5wb3AoKSwKICAgICAgICAgICAgICBiPUQucG9wKCk7CiAgICAgICAgICBELnB1c2goYSk7IEQucHVzaChiKTsKICAgICAgICAgIC8vIG9kZXIgRC5zd2FwKCk7CiAgICAgICAgICBicmVhazsKICAgICAgICBjYXNlICdMJzoKICAgICAgICAgIEQucHVzaChuZXh0Lm9wKTsKICAgICAgICAgIGJyZWFrOwogICAgICAgIGRlZmF1bHQ6CiAgICAgICAgICB0aHJvdyAiRVJVTiI7CiAgICAgIH0KICAgICAgbmV4dD1DLnBvcCgpOwogICAgfQogIH0KfQ==

Die VM programmieren

Ab hier sollen Algorithmen in Java mit dem integrierten JS Transpiler implementiert werden.

Teste die VM mit folgenden Programmen (alle vier Aufgaben sollen unten zusammen getestet werden):

112 234 + .
112 234 - .
112 234 + 100 - .
112 234 % - .

Aufgabe 5. Implementiere die Tests in main und führe die Tests durch bis die Ergebnisse erwartungsgemäß sind.

VM Test

public class Test {
  public static void main() {
    Command cmd1 = new Command('L',2),
            cmd2 = new Command('L',3),
            cmd3 = new Command('+',0),
            cmd4 = new Command('.',0);
    CodeStack C = new CodeStack(10);
    DataStack D = new DataStack(10);
    C.push(cmd4);
    C.push(cmd3);
    C.push(cmd2);
    C.push(cmd1);
    C.run(C,D);
    System.out.println("Result="+D.pop()); 
  }
}

Lösung.

VEJB

Test der VM mit Command, CommandStack, DataStack Klassen . Ausführung von make (Linux, Mac) oder makew (Windows) und run. (websh 0)

Type help or hit TAB for a list of commands.

Aufgabe 6. Wie viele VM Operationen (verwende opCount vom Profiling) werden durchschnittlich für eine Stack VM Instruktion benötigt? Wie ist die Aufteilung in opALU (arithmetische), opBRANCH und opCALL (Kontrollanweisungen) und opDATA (Datenanweisungen)? Führe das Profiling mit dem Verfahren aus der vorherigen Übung durch.

Lösung.

Anhang Profiling

Nachfolgend ist ein Template für das Profiling eines Codeabschnitts (d.h.hier die relevanten algorithmischen Teile).


  public static void profileMe() {
    // Delta stop-start! 

    int [] ops = uj.lang.RT.profileOps();
    int [] mem = uj.lang.RT.profileMem();
    System.out.println(uj.lang.RT.profileTime()+" ms");
    System.out.println(uj.lang.RT.profileIcount()+" Instr.");
    System.out.println("SP="+uj.lang.RT.profileSp());
    System.out.println("[opALU="+ops[0]+" opBRANCH="+ops[1]+" opCALL="+ops[2]+" opNEW="+ops[3]+" opRET="+ops[4]+"]");
    System.out.println("[heapAlloc="+mem[0]+" nalloc="+mem[1]+" nfree="+mem[2]+" ngc="+mem[3]+" ncompact="+mem[4]+"]");  
  }
  ...
  uj.lang.RT.profileStart();
  // Hier der Code 1 für die Profilierung

  uj.lang.RT.profileStop();
  profileMe();
  uj.lang.RT.profileStart();
  // Hier der Code 2 für die Profilierung

  uj.lang.RT.profileStop();
  profileMe();
  ...

Hilfe

Created by the NoteBook Compiler Ver. 1.41.2 (c) Dr. Stefan Bosse (Sat Nov 29 2025 13:20:35 GMT+0100 (Central European Standard Time))