Aufgabe 1: Strings in C

Ihre Aufgabe ist es verschiedene Funktionen zur Behandlung von Strings in C zu implementieren und diese auch hinreichend zu testen. Dazu steht ihnen ein Code Template zur Verfügung.

Es folgt eine Beschreibung der zu implementierenden Funktionen.

normalisiere

Implementiere

char* normalisiere(char* s)

Eingabe ist ein String welcher nur aus Klein-/Grossbuchstaben und Leerzeichen besteht.

Rückgabe ist ein (neuer) String in welchem

alle Leerzeichen eliminiert wurden
alle Grossbuchstaben in Kleinbuchstaben umgewandelt wurden.

Z.B.

normalisiere("Ha Ll o o") ==> "halloo"

Hinweise.

Speicher für den Rückgabe String muss dynamisch allokiert werden
Berechne zuerst die Größe des Strings
Allokiere entsprechend Speicher für den neuen String
Übertrage alle Zeichen (ausser Leerzeichen) in den neuen String, wobei Grossbuchstaben in Kleinbuchstaben umgewandelt werden

copyStr

Implementiere

char* copyStr(char* s)

Eingabe ist ein beliebiger String.

Rückgabe ist eine Kopie des Strings.

Hinweise:

Speicher für den Rückgabe String muss dynamisch allokiert werden
Verwende copy

putBack

Implementiere

char* putBack(char c, char* s)

Eingabe ist ein beliebiger String.

Rückgabe ist ein (neuer) String in welchem Zeichen c am Schluss angehängt ist

Z.B.

putBack('!', "abcd")  ==> "abcd!"

Hinweise.

Speicher für den Rückgabe String muss dynamisch allokiert werden
Verwende wenn möglich putFront und reverse unter Aussnutzung folgender Invariante

 reverse(putFront(c,reverse(s))) = putBack(c, s)

rev

Implementiere

char* rev(char* s)

Eingabe ist ein beliebiger String.

Rückgabe ist ein neuer String welcher die Umkehrung des Eingabestrings ist.

Z.B.

rev("abcd!") ==> "!dcba"

Hinweise.

Speicher für den Rückgabe String muss dynamisch allokiert werden
Die Implementierung soll rekursiv sein und die Hilfsroutine putBack verwenden

replace

Implementiere

char* replace(char* s, struct OldNew* m, int n)

wobei

struct OldNew {
  char old;
  char new;
};

Eingaben sind:

Ein beliebiger String s
Eine Referenz auf ein Array vom Typ OldNew
Die Größe des Arrays

Rückgabe ist ein (neuer) String in welchem alle Zeichen entsprechend dem “OldNew” Array ersetzt wurden.

Z.B. Falls

struct OldNew m[] = { {'B', 'b'}, {'s', '!'}};

dann

replace("Aa dss fBB", m, 2) ==> "Aa d!! fbb"

Hinweise.

Speicher für den Rückgabe String muss dynamisch allokiert werden
Wir gehen davon auss, die Domäne der “old” Zeichen verschieden ist von der Domäne der “new” Zeichen

D.h. Fälle wie

struct OldNew m2[] = { {'B', 'b'}, {'b', '!'}};

sind ausgeschlossen.

Allgemeine Hinweise

Achte auf die Speicherallokation und Speicherfreigabe.

Bestehende Funktionalitäten aus der C Standard Bibliothek dürfen NICHT verwendet werden.

Verwende und erweitere die zur Verfügung gestellten Testroutinen.

Code Template für Aufgabe 1

#include <stdio.h>
#include <stdlib.h>


enum Bool;
struct OldNew;

int length(char *s);
char* normalisiere(char* s);
void copy(char* s, int n, char* t);
char* copyStr(char* s);
char* putFront(char c, char* s);
char* reverse(char* s);
char* putBack(char c, char* s);
char* rev(char* s);
char* replace(char* s, struct OldNew* m, int n);
char* show(enum Bool b);
enum Bool strCmp(char* s1, char* s2);



// Anzahl aller Zeicher (ohne Null-terminator).
int length(char *s) {
  int n = 0;
  while(*s != '\0') {
    n++;
    s++;
  }

  return n;
}


// Normalisiere C String.
// 1. Eliminiere Leerzeichen.
// 2. Alle Grossbuchstaben werden in Kleinbuchstaben umgewandelt.
// 3. Kleinbuchstaben bleiben unveraendert.
// Annahme: C String besteht nur aus Klein-/Grossbuchstaben und Leerzeichen.
char* normalisiere(char* s) {
  // TODO
}


// Kopiere n Zeichen von s nach t.
// Annahme: n ist > 0
void copy(char* s, int n, char* t) {
  int i = 0;
  while(i < n) {
    t[i] = s[i];
    i++;
  }
}


// Baue neuen String welcher eine Kopie des Eingabestrings ist.
char* copyStr(char* s) {
  // TODO
}

// Baue neuen String welcher mit Zeichen c startet gefolgt von allen Zeichen in s.
char* putFront(char c, char* s) {
  const int n =  length(s);
  char* r = (char*)malloc(sizeof(char) * (n+2));
  copy(s, n+1, r+1);
  r[0] = c;
  return r;
}


// Umkehrung eines Strings.
char* reverse(char* s) {
  const int n = length(s);
  char* t = (char*)malloc(n + 1);
  int i;

  for(i = 0; i < n; i++) {
    t[i] = s[n-1-i];
  }
  t[n] = '\0';

  return t;
}

// Baue neuen String welcher aus allen Zeichen in s besteht gefolgt von Zeichen c.
char* putBack(char c, char* s) {
  // TODO
}

// Baue einen neuen String welcher die Umkehrung des Eingabestrings ist.
// Hinweis: Die Implementierung soll rekursiv sein und die Hilfsroutine putBack verwenden.
char* rev(char* s) {
  // TODO
}


struct OldNew {
  char old;
  char new;
};


// Ersetze in einem String jedes Zeichen 'old' mit dem Zeichen 'new'.
// Die Zeichen 'old' und 'new' sind definiert in einem Array vom Typ struct OldNew.
char* replace(char* s, struct OldNew* m, int n) {
  // TODO
}

enum Bool {
  True = 1,
  False = 0
};

char* show(enum Bool b) {
  if(b == True) {
    return copyStr("True");
  } else {
    return copyStr("False");
  }
}


// Teste ob zwei Strings identisch sind.
enum Bool strCmp(char* s1, char* s2) {
  while(*s1 == *s2) {
    if(*s1 == '\0' && *s2 == '\0') {
      return True;
    }
    if(*s1 == '\0') {
      return False;
    }
    if(*s2 == '\0') {
      return False;
    }
    s1++;
    s2++;
  }

  return False;
}


void userTests() {
  printf("\n\n *** User Tests *** \n\n");

  char s1[] = "Ha Ll o o ";

  printf("\n1. %s", s1);

  printf("\n2. %s", normalisiere(s1));

  char* s2 = (char*)malloc(length("Hello")+1);

  char* s3 = copyStr("Hello");

  printf("\n3. %s", s3);

  char s4[] = "abcd";

  char* s5 = putBack('!',s4);

  printf("\n4. %s", s5);

  char* s6 = rev(s5);

  printf("\n5. %s", s6);

  char s7[] = "Aa dss fBB";

  printf("\n6. %s", s7);

  struct OldNew m[] = { {'B', 'b'}, {'s', '!'}};

  char* s8 = replace(s7, m, 2);

  printf("\n7. %s", s8);

  char s9[] = "HiHi";

  char* s10 = copyStr(s9);

  enum Bool b1 = strCmp(s9,s10);

  char* s11 = show(b1);

  printf("\n8. %s", s11);

  char s12[] = "HiHo";

  enum Bool b2 = strCmp(s10, s12);

  char* s13 = show(b2);

  printf("\n8. %s", s13);

  free(s2);
  free(s3);
  free(s5);
  free(s6);
  free(s8);
  free(s10);
  free(s11);
  free(s13);
}

struct TestCase_ {
  char* input;
  char* expected;
};

typedef struct TestCase_ TC;

void runTests(TC* tc, int n, char* sut(char*)) {
  int i;

  for(i=0; i<n; i++) {
    char* result = sut(tc[i].input);
    if(True == strCmp(tc[i].expected, result)) {
      printf("\n Okay Test (%s,%s) => %s", tc[i].input,tc[i].expected, result);
    } else {
      printf("\n Fail Test (%s,%s) => %s", tc[i].input,tc[i].expected, result);
    }
    free(result);
  }

}


void unitTests() {
  printf("\n\n *** Unit Tests *** \n\n");

  TC normTests[] = {
    {"hElLo", "hello"},
    {"hEl Lo", "hello"},
    {"h  El Lo", "hello"},
  };


  runTests(normTests, 3, normalisiere);

}

char* rndString() {
  int i;
  int n = (rand() % 10) + 1;
  char* s = (char*)malloc(n+1);

  for(i=0; i<n; i++) {
    int lowHigh = (rand() % 2) ? 'a' : 'A';
    int c = rand() % 26;
    s[i] = (char)(c + lowHigh);
  }
  s[n] = '\0';

  return s;
}

void invariantenTests() {
  printf("\n\n *** Invarianten Tests *** \n\n");

  int i;
  for(i=0; i<20; i++) {
    char* s = rndString();
    char* r = reverse(s);
    char* n1 = normalisiere(s);
    char* n2 = normalisiere(r);
    char* n3 = reverse(n2);

    if(True == strCmp(n1,n3)) {
      printf("\nOkay %s", s);
    } else {
      printf("\nFail %s", s);
    }

    free(s);
    free(r);
    free(n1);
    free(n2);
    free(n3);
  }



}


int main() {
  userTests();

  unitTests();

  invariantenTests();
}

Aufgabe 2: Dynamische Arrays in C++11

Ihre Aufgabe ist die Implementierung einer Klasse zur Verwaltung von dynamischen Arrays. Die Elemente in dem dynamischen Array sind alle vom gleichen aber beliebigen Typ. Des verwenden wir eine templatifizierte Klasse.

Das Design der Klasse orientiert sich an dem Design der “String” Klasse bekannt aus der Vorlesung und soll dem “Rule of Five” Designmusster (copy/move Semantik) folgen.

Es folgt eine Beschreibung der zu implementierenden Konstruktoren/Methoden.

Konstruktoren/Zuweisungsmethode (copy/move)

  DynArr(const DynArr<T>& src) {
   // TODO
  }
   DynArr<T>& operator=(const DynArr<T>& src) {
   // TODO
  }
  DynArr(DynArr<T>&& src) {
   // TODO
  }
  DynArr<T>& operator=(DynArr<T>&& src) {
   // TODO
  }

Das zu implementierende Verhalten ist analog zur “String” Klasse.

add Methode

  void add(T x)

Füge Element x hinzu (an den Schluss).

Hinweise.

Lege neuen Speicher an (bisherige Größe + 1)
Kopiere bestehende Elemente, wobei x an den Schluss kommt
Lösche bestehenden Speicher

reverse Methode

  void reverse()

Bilde die Umkehrung. Letztes Element wird erstes Element usw.

Hinweise.

Codefragmente aus Aufgabe 1 dürfen übernommen werden

append Methode

  void append(const DynArr<T>& src)

Füge eine dynamisches Array src hinzu (an den Schluss).

Hinweise.

Lege neuen Speicher an (bisherige Größe + Größe von src)
Kopiere bestehende Elemente, wobei Elemente von src an den Schluss kommen
Lösche bestehenden Speicher

Mit Hilfe von append kann man add implementieren.

Anhang: Source Files

dynArr.hpp

#ifndef __DYNARR__
#define __DYNARR__

#include <iostream>
using namespace std;

template<typename T>
void copy_(T* s, int n, T* t) {
  int i = 0;
  while(i < n) {
    t[i] = s[i];
    i++;
  }
}


template<typename T>
class DynArr {
  int len;
  T* p;

public:

  DynArr() {
    this->len = 0;
    this->p = nullptr;
  }
  DynArr(T x, int size) {
    this->len = size;
    this->p = new T[size];

    for(int i=0; i<size; i++) {
      this->p[i] = x;
    }
  }
  DynArr(const DynArr<T>& src) {
   // TODO
  }
   DynArr<T>& operator=(const DynArr<T>& src) {
   // TODO
  }
  DynArr(DynArr<T>&& src) {
   // TODO
  }
  DynArr<T>& operator=(DynArr<T>&& src) {
   // TODO
  }


  ~DynArr() { delete[] p; }

  T& operator[](int index) {
    return p[index];
  }


  int size() const {
      return this->len;
  }

  string show() {
    string s;
    for(int i=0; i<this->len; i++) {
      s = s + to_string(p[i]);
    }
    return s;
  }


  void add(T x) {
   // TODO
  }

  void reverse() {
  // TODO
  }

  void append(const DynArr<T>& src) {
  // TODO
  }

};


#endif

testDynArr.cpp


#include <iostream>
using namespace std;

#include "dynArr.hpp"

void example1() {

  DynArr<int> d;

  d.add(1);

  cout << "\n1. " << d[0];

  d.add(2);

  cout << "\n2. " << d[0] << d[1];

  cout << "\n3. " << d.show();

  d.reverse();

  cout << "\n4. " << d.show();

  d.append(d);

  cout << "\n5. " << d.show();

  DynArr<int> d2;

  d2 = d;

  cout << "\n6. " << d2.show();

  d.reverse();

  d2.append(d);

  cout << "\n7. " << d2.show();

}


template<typename T>
void someFunc(int i, DynArr<T> d) {
  d.reverse();

  cout << "\n" << i << ". " << d.show();
}


void example2() {

  DynArr<bool> d = DynArr<bool>();

  d.add(true);

  cout << "\n1. " << d[0];

  d.add(false);

  cout << "\n2. " << d[0] << d[1];

  cout << "\n3. " << d.show();

  someFunc<bool>(3,d);

  cout << "\n4. " << d.show();

  someFunc<bool>(5,DynArr<bool>(true, 2));

  DynArr<bool> d2;

  d2 = move(d);

  d2.add(false);

  cout << "\n6. " << d2.show();



}


int main() {

  cout << "\n\n *** example1 *** \n";
  example1();

  cout << "\n\n *** example2 *** \n";
  example2();


}

Aufgabe 3: Stack-basierte VM in C++11

Wir betrachten die semantische Auswertung von Programmen. Dazu gibt es zwei prinzipielle Ansätze.

Interpreter/Interpretation.

Die Auswertung des Programms betrachtet die Struktur der einzelnen Programmteile. Z.B. im Fall von Addition, werden die Operanden ausgewertet, dann die Addition ausgeführt usw.

Compiler/Compilation.

Das Programm wird in eine Maschinen-verarbeitbare Form gebracht welche direkt vom Prozessor ausgewertet werden kann. Die Compilation ist ein komplexer Prozess und wird deshalb in eine Reihe von Zwischenschritten (unter Zuhilfenahme von Zwischensprachen) ausgeführt.

Das Ziel heutzutage ist, dass ein Compiler weitesgehend Plattform-unabhängig ist. Deshalb wird anstatt Assembler/Maschinencode, Code für eine virtuelle Maschine erzeugt (siehe Java/JVM und C#/.Net).

Aufgabe

Wir betrachten hier eine sehr einfache Programmiersprache (arithmetische Ausdrücke) welche in eine stack-basierte virtuelle Maschine (VM) übersetzt werden soll.

Eine Beschreibung der VM wie auch der zu verwendende Source Code findet sich weiter unten. Die von ihne zu vervollständigen Teile sind als TODO markiert.

Stack-basierte VM am Beispiel

Unsere stack-basierte VM verfügt über folgende Instruktionen (Befehle/Codes).

Push i

     schiebe (push) Konstante i auf den Stack

Plus

     hole Operanden von Stack
     fuehre Addition aus
     schiebe Ergebnis aud Stack

Mult

     hole Operanden von Stack
     fuehre Multiplikation aus
     schiebe Ergebnis aud Stack

Ein paar Beispiele, um zu zeigen, wie damit arithmetische Ausdrücke ausgewertet werden können.

Zuerst der Ausdruck und dann die VM Instruktionen.

1 + 2

Push 1; Push 2; Plus;

Wir betrachten den Stack während der Abarbeitung der VM Instruktionen. Den Stack schreiben wir von links nach rechts. Links = top.

Initial:

Push 1; Push 2, Plus

Stack = []


1. Schritt

Push 2, Plus

Stack = [1]

2. Schritt

Plus

Stack = [2, 1]

3. Schritt


Stack = [3]

Ein komplexeres Beispiel.

1 * (2 + 3)

Push 1; Push 2; Push 3; Plus; Mult;

Die einzelnen Auswertungsschritte.

Initial:

Push 1; Push 2; Push 3; Plus; Mult;

Stack = []

1. Schritt

Push 2; Push 3; Plus; Mult;

Stack = [1]

2. Schritt

Push 3; Plus; Mult;

Stack = [2, 1]

3. Schritt

Plus; Mult;

Stack = [3, 2, 1]

4. Schritt

Mult;

Stack = [5, 1]

5. Schritt

Stack = [5]

Source Files (Aufgabe 3)

Makefile utility.h vm.h, vm.cpp exp.h, exp.cpp testVM.cpp testExp.cpp

Makefile

CC=g++ --std=c++11

testExp : testExp.o vm.o exp.o
    $(CC) testExp.o vm.o exp.o -o testExp

testExp.o :testExp.cpp
    $(CC) -c testExp.cpp

testVM : testVM.o vm.o
    $(CC) testVM.o vm.o -o testVM
testVM.o: testVM.cpp
    $(CC) -c testVM.cpp

exp.o: exp.cpp exp.h vm.cpp vm.h
    $(CC) -c exp.cpp
vm.o: vm.cpp vm.h
    $(CC) -c vm.cpp

NB. If you copy and paste the above Makefile, some tabs might not be copied. There need to be some tabs in the third, fith line and so on. Depending on your system, you may also need to set CC to your specific C++ compiler.

utility

utility.h

// Utility stuff

#ifndef __UTILITY__
#define __UTILITY__

// Haskell's Maybe
template<typename T>
class Optional {
  bool b;
  T val;
public:
  Optional() : b(false) {}
  Optional(T v) : val(v), b(true) {}
  bool isJust() { return b; }
  bool isNothing() { return !b; }
  T fromJust() { return val; }
};

template<typename T>
Optional<T> nothing() {
  return Optional<T>();
}

template<typename T>
Optional<T> just(T v) {
  return Optional<T>(v);
}


#endif // __UTILITY__

vm

vm.h

// Stack-based VM

#ifndef __VM__
#define __VM__

#include <vector>
#include <stack>

using namespace std;

#include "utility.h"


/*

Stack-based VM, instructions supported are:

  Push i
  Plus
  Mult

 */



typedef enum {
  PUSH,
  PLUS,
  MULT

} OpCode_t;


class Code {
public:
  OpCode_t kind;
  int val;

  // Nullary VM code (PLUS, MULT)
  Code(OpCode_t o) : kind(o) {}
  // Unary VM code (Push i)
  Code(OpCode_t o, int i) : kind(o), val(i) {}
};

// Short-hands

Code newPush(int i);

Code newPlus();

Code newMult();

class VM {
    vector<Code> code;
    stack<int> s;
  public:
    VM(vector<Code> c) : code(c) {}

    Optional<int> run();

    void runAndPrint();

};




#endif // __VM__

vm.cpp

#include <iostream>
#include <string>
using namespace std;

#include "utility.h"
#include "vm.h"


Code newPush(int i) {
  return Code(PUSH, i);
}

Code newPlus() {
  return Code(PLUS);
}

Code newMult() {
  return Code(MULT);
}


Optional<int> VM::run() {

      // always start with an empty stack
      stack<int> d;
      s.swap(d);

      for(int i = 0; i < code.size(); i++) {
    switch(code[i].kind) {
    case PUSH:
      s.push(code[i].val);
        break;
    case MULT: {
      int right = s.top();
      s.pop();
      int left = s.top();
      s.pop();
      s.push(left * right);
      break;
    }
    case PLUS: {
      int right = s.top();
      s.pop();
      int left = s.top();
      s.pop();
      s.push(left + right);
      break;
    }
    }
      }

      if(s.empty())
    return nothing<int>();

      return just<int>(s.top());
} // run


void VM::runAndPrint() {

  auto r = this->run();

  if(r.isNothing()) {
    cout << "\nVM stack (top): empty";
  } else {
    cout << "\nVM stack (top):" << r.fromJust();
  }

}// runAndPrint

exp

exp.h

// AST for exp


#ifndef __AST__
#define __AST__

#include <iostream>
#include <string>
#include <vector>
#include <memory>

#include "vm.h"

using namespace std;

class Exp {
public:
  virtual int eval() = 0;
  virtual vector<Code> compile() = 0;
};

class IntExp : public Exp {
  int val;
  public:
  IntExp(int _val) { val = _val; }
  int eval();
  vector<Code> compile();
};

class PlusExp : public Exp {
  std::shared_ptr<Exp> e1;
  std::shared_ptr<Exp> e2;
  public:
  PlusExp(std::shared_ptr<Exp> _e1, std::shared_ptr<Exp> _e2) {
      e1 = _e1; e2 = _e2;
  }
  int eval();
  vector<Code> compile();
};


class MultExp : public Exp {
  std::shared_ptr<Exp> e1;
  std::shared_ptr<Exp> e2;
  public:
  MultExp(std::shared_ptr <Exp> _e1, std::shared_ptr<Exp> _e2) {
      e1 = _e1; e2 = _e2;
  }
  int eval();
  vector<Code> compile();
};

// Short-hands

typedef std::shared_ptr<Exp> EXP;

EXP newInt(int i);

EXP newPlus(EXP l, EXP r);

EXP newMult(EXP l, EXP r);


#endif // __AST__

exp.cpp

#include <iostream>
#include <string>
#include <vector>

using namespace std;

#include "vm.h"
#include "exp.h"

int IntExp::eval() { return val;}

int PlusExp::eval() { return e1->eval() + e2->eval(); }

int MultExp::eval() { return e1->eval() * e2->eval(); }


// TODO
vector<Code> IntExp::compile() {
  vector<Code> v;

  return v;
}


// TODO
vector<Code> PlusExp::compile() {
  vector<Code> v;

  return v;
}

// TODO
vector<Code> MultExp::compile() {
  vector<Code> v;

  return v;
}


EXP newInt(int i) {
  return std::make_shared<IntExp>(i);
}

EXP newPlus(EXP l, EXP r) {
  return std::make_shared<PlusExp>(l,r);
}

EXP newMult(EXP l, EXP r) {
  return std::make_shared<MultExp>(l,r);
}

testVM.cpp

#include "vm.h"


void testVM() {

  {
    vector<Code> vc{
          newPush(1),
      newPush(2),
      newPush(3),
      newMult(),
      newPlus() };

    VM(vc).runAndPrint();

  }

  {
    vector<Code> vc{
          newPush(2),
      newPush(3),
      newPush(5),
      newPlus(),
      newMult() };

    VM(vc).runAndPrint();
  }
}


int main() {

  testVM();

  return 1;
}

testExp .cpp

#include <iostream>
#include <string>

using namespace std;

#include "exp.h"


void testExp() {

  EXP e1 = newPlus(newInt(1),newInt(0));

  cout << "\n " << e1->eval();

  EXP e2 = newMult(e1,e1);

  cout << "\n " << e2->eval();


  // We expect that result are the same.
  auto vm1 = VM(e1->compile());

  vm1.runAndPrint();

  auto vm2 = VM(e2->compile());

  vm2.runAndPrint();
}


int main() {

  testExp();

  return 1;
}

Übung (Schein) ab Winter Semester 2024/25

Übersicht und allgemeine Hinweise

Aufgabe 1: Strings in C

normalisiere

copyStr

putBack

rev

replace

Allgemeine Hinweise

Code Template für Aufgabe 1

Aufgabe 2: Dynamische Arrays in C++11

Konstruktoren/Zuweisungsmethode (copy/move)

add Methode

reverse Methode

append Methode

Anhang: Source Files

dynArr.hpp

testDynArr.cpp

Aufgabe 3: Stack-basierte VM in C++11

Stack-basierte VM am Beispiel

Source Files (Aufgabe 3)

Makefile

utility

utility.h

vm

vm.h

vm.cpp

exp

exp.h

exp.cpp

testVM.cpp

testExp .cpp