Informatik I PVK

Pascal Schärli

pascscha@student.ethz.ch

Pascal Schärli - PVK Informatik 1 2019

Typen und Werte

int a = 5;
b = a + a;
c = b + 3;
  • Variablen können sich im Laufe des Programms ändern.
  • Jede Variable hat ihren eigenen Typ (z.B. int, float, char)
  • Jede Variable muss vor dem Gebrauch deklariert werden.
int a = 5;
int b = a + a;
int a = b + 3;
error: ‘b’ was not declared in this scope
int a = 5;
int b = a + a;
int c = b + 3;
error: error: redeclaration of ‘int a’

Variablen

Pascal Schärli - PVK Informatik 1 2019

Typen und Werte

Pascal Schärli - PVK Informatik 1 2019

Primitive Datentypen - Boolean

Typen und Werte

Beschreibung

Booleans werden verwendet um Wahrheitswerte (wahr/falsch) darzustellen.

Abkürzung

bool

Beispiel

bool a = true;
bool b = false;
Bits 1
Von 0
Bis 1

Eigenschaften

Pascal Schärli - PVK Informatik 1 2019

Primitive Datentypen - Character

Typen und Werte

Beschreibung

Characters werden verwendet um Zeichen darzustellen

Abkürzung

char

Beispiel

char a = 'f';
char b = '\n';
Bits 8
Von 0
Bis 255

Eigenschaften

Pascal Schärli - PVK Informatik 1 2019

Primitive Datentypen - Integer

Typen und Werte

Beschreibung

Integers werden verwendet um ganze Zahlen darzustellen

Abkürzung

int

Beispiel

int a = 1;
int b = -10;
Bits 32
Von
Bis

Eigenschaften

\(-2^{31}\)

\(2^{31}-1\)

Pascal Schärli - PVK Informatik 1 2019

Primitive Datentypen - Unsigned Integer

Typen und Werte

Beschreibung

Unsigned Integers werden verwendet um natürliche Zahlen darzustellen

Abkürzung

unsigned int

Beispiel

unsigned int a = 1;
unsigned int b = 5;
Bits 32
Von
Bis

Eigenschaften

\(0\)

\(2^{32}\) - 1

Pascal Schärli - PVK Informatik 1 2019

Typen und Werte

Beschreibung

Floats werden verwendet um Fliesskommazahlen darzustellen.

Abkürzung

float

Beispiel

float a = 1.5;
float b = -1.9;
Bits 32
Von
Bis

Eigenschaften

\(-(2^{23})^{2^8}\)

\((2^{23})^{2^8}\)

Primitive Datentypen - Float

Pascal Schärli - PVK Informatik 1 2019

Typen und Werte

Beschreibung

Doubles sind wie Floats, doch sie haben doppelt so hohe Präzision.

Abkürzung

double

Beispiel

double a = 1.5;
double b = -1.9;
Bits 64
Von
Bis

Eigenschaften

\(-(2^{52})^{2^{11}}\)

\((2^{52})^{2^{11}}\)

Primitive Datentypen - Double

Pascal Schärli - PVK Informatik 1 2019

Casting

Typen und Werte

  • Das umwandeln von einem Datentyp zu einem anderen Datentyp nennt man casten
  • Beim Casten kann es passieren, dass sich der Wert der Zahl verändern kann.

Pascal Schärli - PVK Informatik 1 2019

Casting - Boolean

Typen und Werte

  • Irgendein Typ \(\rightarrow\) Boolean
    • 0 \(\rightarrow\) false
    • sonst \(\rightarrow\) true
  • Boolean \(\rightarrow\) Irgendein Typ
    • false \(\rightarrow\) 0
    • true \(\rightarrow\) 1

Beispiele

5.8

\(\rightarrow\)

true
0

\(\rightarrow\)

false

Irgendein Typ \(\rightarrow\) Boolean

false

\(\rightarrow\)

0

true

\(\rightarrow\)

1

Boolean \(\rightarrow\) Irgendein Typ

Pascal Schärli - PVK Informatik 1 2019

Casting - Character

Typen und Werte

Die letzen 8 Bits werden zum entsprechenden Zeichen umgewandelt:

Pascal Schärli - PVK Informatik 1 2019

Casting - Integer \(\leftrightarrow\) Float, Double

Typen und Werte

  • Float, Double \(\rightarrow\) Integer
    • Die Zahl wird abgerundet
  • Integer \(\rightarrow\) Float, Double
    • Die Zahl bleibt (meistens*) unverändert
0.4

\(\rightarrow\)

0

9.99

\(\rightarrow\)

9

Beispiele

Float,Double \(\rightarrow\) Integer

*bei grossen Zahlen kann es sein, dass sie nicht exakt als float darstellbar sind

5

\(\rightarrow\)

5

7

\(\rightarrow\)

7

Integer \(\rightarrow\) Float,Double

Pascal Schärli - PVK Informatik 1 2019

Casting - Integer \(\leftrightarrow\) Unsigned Integer

Typen und Werte

Bei der Umwandlung von int zu unsigned int bleibt die Binäre darstellung gleich, die Zahl wird einfach anders interpretiert.

Binär int unsigned int
0000 0 0
0001 1 1
0010 2 2
0011 3 3
0100 4 4
0101 5 5
0110 6 6
0111 7 7
Binär int unsigned int
1000 -8 8
1001 -7 9
1010 -6 10
1011 -5 11
1100 -4 12
1101 -3 13
1110 -2 14
1111 -1 15

Beispiel: 4 Bit Zahlensystem

Pascal Schärli - PVK Informatik 1 2019

Typen und Werte

Beim Rechnen mit verschiedenen Datentypen werden die Werte immer in den "Allgemeineren" Datentyp umgewandelt.

bool
char
int
unsigned int
float
double

Rechnen mit verschiedenen Typen

Pascal Schärli - PVK Informatik 1 2019

Rechnen mit verschiedenen Typen

Typen und Werte

0.5f * (true + 'a' - 2) + 4u - 6.
bool
char

int

unsigned int

float

double

0.5f * (    'b'    - 2) + 4u - 6.
0.5f * (      96      ) + 4u - 6.
          48.0f         + 4u - 6.
            52.0f            - 6.
              46.0
Typ Wert
double 46

Pascal Schärli - PVK Informatik 1 2019

Rechnen mit verschiedenen Typen

Typen und Werte

2 / 4.0f + 7 / 2.0
1 / 2 * 2.0
12 - 7 % 5
3 / 2.0f + 10 / 2.0

Typ

Wert

double

4

double

0

int

10

double

6.5

Pascal Schärli - PVK Informatik 1 2019

Increment

Typen und Werte

  • Der Pre- Post Increment Operator erhöht eine Variable um 1.
  • Man kann das Increment vor oder nach der Variabel schreiben.

Pre Increment

Post Increment

Die Variabel wird erhöht und der neue Wert wird zurückgegeben

Die Variabel wird erhöht und der alte Wert wird zurückgegeben

int a = 5;
std::cout << ++a;
int a = 5;
std::cout << a++;

Output

6

Wert von a

6

Output

5

Wert von a

6

Pascal Schärli - PVK Informatik 1 2019

Increment

Typen und Werte

Pre Increment

Post Increment

Die Variabel wird erhöht und der neue Wert wird zurückgegeben.

Das Pre-increment für Integer ist äquivalent zu dieser Funktion:

Die Variabel wird erhöht und der alte Wert wird zurückgegeben.

Das Post-increment für Integer ist äquivalent zu dieser Funktion:

int& pre(int& i){
    i = i + 1;
    return i;
}
int post(int& i){
    i = i + 1;
    return i - 1;
}
++a
pre(a)
a++
post(a)

Pascal Schärli - PVK Informatik 1 2019

Vergleiche

Typen und Werte

=
==
<
<
>
>
!=
\le
<=

≠

\ge
>=

In C++ können Variablen wie in der Mathematik miteinander verglichen werden.

Pascal Schärli - PVK Informatik 1 2019

Boolean Expressions

Typen und Werte

a b a && b
false false false
false true false
true false false
true true true

AND

a b a || b
false false false
false true true
true false true
true true true

OR

a b a != b
false false false
false true true
true false true
true true false

XOR

a !a
false true
true false

NOT

&&
||
!=
!

Pascal Schärli - PVK Informatik 1 2019

Kurzschluss Evaluation

Typen und Werte

false && (1u-5<=++x%y)
false
true || (1u-5<=++x%y)
true

C++ wertet die rechte Seite von einem boolschen nicht mehr aus, falls das Resultat bereits bekannt ist.

Pascal Schärli - PVK Informatik 1 2019

Präzedenz

Typen und Werte

Präzedenz Operator Assoziativität
2
3
5
6
9
10
14
15
16 
a++
a--
++a
--a
!
a*b
a/b
a%b
a+b
a-b
<
<=
>
>=
==
!=
&&
||
=
+=

Komplette Tabelle: https://en.cppreference.com/w/cpp/language/operator_precedence

Pascal Schärli - PVK Informatik 1 2019

Präzedenz

Typen und Werte

 x == 1  ||   1 / (x - 1)  < 1
 x == 1  ||  (1 / (x - 1)) < 1
 x == 1  || ((1 / (x - 1)) < 1)
(x == 1) || ((1 / (x - 1)) < 1)
(1 == 1) || ((1 / (x - 1)) < 1)
    true || ((1 / (x - 1)) < 1)
    true
int x = 1;
P Op Assoz.
2
3
5
6
9
10
14
15
16 
a++
a--
++a
--a
!
a*b
a/b
a%b
a+b
a-b
<
<=
>
>=
==
!=
&&
||
=
+=

Pascal Schärli - PVK Informatik 1 2019

Präzedenz

Typen und Werte

P Op Assoz.
2
3
5
6
9
10
14
15
16 
a++
a--
++a
--a
!
a*b
a/b
a%b
a+b
a-b
<
<=
>
>=
==
!=
&&
||
=
+=
 !(1 && x)  + 1
(!(1 && x)) + 1
(!(1 && 1)) + 1
(!( true )) + 1
(  false  ) + 1
     0      + 1
              1
int x = 1;

Pascal Schärli - PVK Informatik 1 2019

Präzedenz

Typen und Werte

P Op Assoz.
2
3
5
6
9
10
14
15
16 
a++
a--
++a
--a
!
a*b
a/b
a%b
a+b
a-b
<
<=
>
>=
==
!=
&&
||
=
+=
  8 > 4  > 2  > 1
((8 > 4) > 2) > 1
( true   > 2) > 1
(   1    > 2) > 1
       false  > 1
         0    > 1
            false

Pascal Schärli - PVK Informatik 1 2019

Typen und Werte

true && ! true == false || false
++a / b--
1. + (2u - 5 < 6)
1 / 10 * 1. == 1. * 1 / 10

Typ

Wert

bool

true

int

2

double

1

bool

false

int a = 1;
int b = 1;

Präzedenz

Pascal Schärli - PVK Informatik 1 2019

R/L - Values

Typen und Werte

  • Operanden in Expressions können in R und L values unterteilt werden.
  • L-Values dürfen links von einem Assignment Operator (=) stehen, R-Values nicht.

L-Value

R-Value

Darf links oder rechts von = stehen.

Hat eine Adresse an welcher Werte gespeichert werden können.

Darf nur rechts vom = stehen.

Kann keine Werte speichern.

Pascal Schärli - PVK Informatik 1 2019

R/L - Values

Typen und Werte

L-Value

R-Value

a
a += 3
a = b
3
a + 3
a == b
++a
a++
int a = 1;
int b = 2;

Pascal Schärli - PVK Informatik 1 2019

Prüfungsaufgabe

Typen und Werte

Sommer 2017, 0.59 Notenpunkte

Pascal Schärli - PVK Informatik 1 2019

Typen und Werte (Basistypen)

Prüfungsaufgabe

Basisprüfung Sommer 2017, 0.59 Notenpunkte

Geben Sie für jeden der Ausdrücke auf der nächsten Seite jeweils C++Typ und Wert an. Wenn der Wert nicht bestimmt werden kann, schreiben Sie “undefiniert”.

int i = 10;
double d = 2;
int m = 7;
int pre = 1;
int post = 1;
unsigned int u = 0;

Pascal Schärli - PVK Informatik 1 2019

Typen und Werte (Basistypen)

Prüfungsaufgabe

Basisprüfung Sommer 2017, 0.59 Notenpunkte

1 / 4 * d
m % m
i = 10
i += i

Typ

Wert

double

0

++pre / post--
u-5 < 6
int

0

int

10

int

20

int

2

bool

false

Zahlendarstellung

Pascal Schärli - PVK Informatik 1 2019

Fliesskomma \(\rightarrow\) Binär

Pascal Schärli - PVK Informatik 1 2019

Zahlendarstellung

\(ab.cd \rightarrow a*2 + b*1 + c/2 + d/4\)

10.00 \(\rightarrow\) 2
10.01 \(\rightarrow\) 2 + 1/4
10.10 \(\rightarrow\) 2 + 1/2
10.11 \(\rightarrow\) 2 + 3/4
11.00 \(\rightarrow\) 3
11.01 \(\rightarrow\) 3 + 1/4
11.10 \(\rightarrow\) 3 + 1/2
11.11 \(\rightarrow\) 3 + 3/4

00.00 \(\rightarrow\) 0
00.01 \(\rightarrow\) 0 + 1/4
00.10 \(\rightarrow\) 0 + 1/2
00.11 \(\rightarrow\) 0 + 3/4
01.00 \(\rightarrow\) 1
01.01 \(\rightarrow\) 1 + 1/4
01.10 \(\rightarrow\) 1 + 1/2
01.11 \(\rightarrow\) 1 + 3/4

Fliesskomma \(\rightarrow\) Binär

Pascal Schärli - PVK Informatik 1 2019

Zahlendarstellung

x_i
b_i
x - b_i
x_{i+1} = 2*(x-b_i)
1.9
1.2
0.4
0.8
1.6
1.8
1.6
1
1
0
0
1
1
1
1.2
1.2
0.4
0.8
1.6
1.8
1.6
0.9
0.2
0.4
0.8
0.6
0.8
0.6
1
.
1
1
1
1
0
0
1
1
1
1.9 \rightarrow
\sout{1}

Pascal Schärli - PVK Informatik 1 2019

Zahlendarstellung

Fliesskomma \(\rightarrow\) Binär

FP-Systeme

Pascal Schärli - PVK Informatik 1 2019

Zahlendarstellung

F^* (b, p, e_{min} , e_{max} )
\pm b_0.b_1 b_2 \cdots b_{p-1} * b^e
b_i \in \{0, \ldots b-1\}\\
b_0 != 0
e \in \{e_{min}, e_{min} + 1, \ldots, e_{max}\}\\

\(p \rightarrow\) Anzah Ziffern

(Basis des Zahlensystems)

(Bereich für Exponent)

(Normalisiert)

FP-Systeme

Pascal Schärli - PVK Informatik 1 2019

Zahlendarstellung

Sind diese Zahlen sind im folgenden Zahlensystem enthalten: \(F^* (2, 4, -2 , 2 )\)?

1.000 * 2^1
1.001 * 2^-1
1.111 * 2^2
0.000 * 2^1
1.0001 * 2^-1
1.111 * 2^5

normalisiert \(\rightarrow \) Zahl startet nicht mit 0

zu viele Nachkommastellen

Exponent ist nicht zwischen \(-2\) und \(2\).

\pm b_0.b_1 b_2 \cdots b_{p-1} * b^e

FP-Systeme

Pascal Schärli - PVK Informatik 1 2019

Zahlendarstellung

Was sind die folgenden Zahlen in \(F^* (2, 4, -2 , 2 )\)?

die kleinste nicht-negative.
die grösste
die kleinste
 1.111 * 2^2 ->  7.5
-1.111 * 2^2 -> -7.5
1.000 * 2^-2 -> 0.25
\pm b_0.b_1 b_2 \cdots b_{p-1} * b^e

FP-Systeme

Pascal Schärli - PVK Informatik 1 2019

Zahlendarstellung

\(F^* (b, p, e_{min} , e_{max} )\)?

Was Formel
Anzahl Positiver Werte
Anzahl Werte
grösste Zahl
kleinste positive Zahl

\((b-1)*b^{p-1} * (e_{max} - e_{min} + 1)\)

\((b^p -1) * b^{e_{max}-p+1}\)

\(b^{e_{min}} \)

\((b-1)*b^{p-1} * (e_{max} - e_{min} + 1)*2\)

FP-Systeme

Pascal Schärli - PVK Informatik 1 2019

Zahlendarstellung

Rechnen mit FP-Systemen

Pascal Schärli - PVK Informatik 1 2019

Zahlendarstellung

Wie kann man Zahlen in einem FP-System addieren?

 

  • Beide Zahlen auf den selben Exponenten bringen

 

  • Binärzahlen addieren (wie schriftliche Addition)

 

  • Summe re-Normalisieren (\(1.\ldots\))

 

  • Runden falls nötig

Rechnen mit FP-Systemen

Pascal Schärli - PVK Informatik 1 2019

Zahlendarstellung

1.001 * 2^-1 + 1.111 * 2^-2
    1.001  * 2^-1
 +  0.1111 * 2^-1
    1.001  * 2^-1
 +  0.1111 * 2^-1
 -----------------
 = 10.0001 * 2^-1

    1.001  * 2^-1
 +  0.1111 * 2^-1
 -----------------
 = 10.0001 * 2^-1
 
 = 1.00001 * 2^0

    1.001  * 2^-1
 +  0.1111 * 2^-1
 -----------------
 = 10.0001 * 2^-1
 
 = 1.00001 * 2^0
 
=> 1.000   * 2^0

\(\rightarrow\) Resultat: \(1\) (Exakt: \(1.03125\))

\(F^* (2, 4, -2 , 2 )\)

Beide Zahlen auf den selben Exponenten bringen
Binärzahlen addieren (wie schriftliche Addition)
Summe re-Normalisieren (1. ...)
Runden falls nötig

Pascal Schärli - PVK Informatik 1 2019

Prüfungsaufgabe

Zahlendarstellungen

Winter 2016, 0.44 Notenpunkte

Pascal Schärli - PVK Informatik 1 2019

Normalisiertes Fliesskommasystem

Prüfungsaufgabe

Basisprüfung Winter 2016, 0.44 Notenpunkte

F^* (b, p, e_{min} , e_{max} )
e_{min} = -2
b = 2
p = 5
e_{max} = 2

Pascal Schärli - PVK Informatik 1 2019

Normalisiertes Fliesskommasystem

Prüfungsaufgabe

Wie viele unterschiedliche positive Werte beinhaltet das normalisierte Fliesskommasystem \(F^*\)?

F^* (2, 5, -2, 2)

\((b-1)b^{p-1} * (e_{max} - e_{min} + 1)\)

\(= (2-1)*2^{5-1} * (2 - (-2) + 1)\)

\(= 80\)

\(= 2^{4} * (5)\)

Pascal Schärli - PVK Informatik 1 2019

Normalisiertes Fliesskommasystem

Prüfungsaufgabe

Welches ist die grösste Zahl in \(F^*\)?

F^* (2, 5, -2, 2)

\((b^p -1) * b^{e_{max}-p+1}\)

\(=(2^5 -1) * 2^{2-5+1}\)

\(=7.75\)

\(=32 / 4 - 1/4\)

\(=(32 - 1) * 2^{-2}\)

Pascal Schärli - PVK Informatik 1 2019

Normalisiertes Fliesskommasystem

Prüfungsaufgabe

Welches ist die maximale Präzision in \(F^*\)?

F^* (2, 5, -2, 2)

\(b^{e_{min}}\)

\(=2^{-2}\)

\(=\frac{1}{4}\)

Pascal Schärli - PVK Informatik 1 2019

Normalisiertes Fliesskommasystem

Prüfungsaufgabe

Welche Zahl \(\hat{x}\) aus \(F^*\) ist am nächsten an \(x = 2.5625\)?

(Arithmetisch Runden)

F^* (2, 5, -2, 2)

\(2 \rightarrow 10_{(2)}\)

\(0.5625 \rightarrow 0.1001_{(2)}\)

\(2.5625 \rightarrow 10.1001_{(2)}\)

\(10.1001_{(2)}\)

\(1.01001_{(2)} * 2^1\)

\(\hat{x} = 1.0101_{(2)} * 2^1\)

Normalisieren

Arithmetisch Runden

Pascal Schärli - PVK Informatik 1 2019

Normalisiertes Fliesskommasystem

Prüfungsaufgabe

Was ist der Fehler \(|\hat{x}-x|\)?

F^* (2, 5, -2, 2)

\(\hat{x} = 1.0101_{(2)} * 2^1\)

\(= (1 + \frac{1}{4} + \frac{1}{16}) * 2^1\)

\(=2.625\)

\(\Rightarrow |\hat{x} - x|=|2.625 - 2.5625|\)

\(=0.0625\)

Pascal Schärli - PVK Informatik 1 2019

Programmfluss

If - Statement

Pascal Schärli - PVK Informatik 1 2019

Programmfluss

int n = 50;

if(n > 128){
    std::cout << "n is larger than 128";
}
else if(n > 64){
    std::cout << "n is larger than 64";
}
else if(n > 32){
    std::cout << "n is larger than 32";
}
else if(n > 16){
    std::cout << "n is larger than 16";
}
else {
    std::cout << "n is smaller than 17";
}
  • Falls die Condition in den Runden () Klammern erfüllt ist, wird der Code in den geschweiften {} Klammern ausgeführt.

 

  • Jedes If-Statement besteht aus:
    1. Genau einem if
    2. Beliebig vielen else if
    3. Höchstens einem else 
n is larger than 32

Scopes

Pascal Schärli - PVK Informatik 1 2019

Programmfluss

int a = 0;

if(a == 0){
    int b = 3;
}
else{
    int b = 4;
}

std::cout << b << std::endl;
  • Variablen sind immer nur in einem bestimmten Bereich (=scope) gültig
  • Wenn dieser Bereich verlassen wird, wird die Variable wieder gelöscht

error: ‘b’ was not declared in this scope

Scopes

Pascal Schärli - PVK Informatik 1 2019

Programmfluss

int a = 2;

if (x < 7) {
    int a = 8;
    std::cout << a;
}

std::cout << a;

82
int a = 2;

if (x < 7) {
    a = 8;
    std::cout << a;
}

std::cout << a;

88

While-Loop

Pascal Schärli - PVK Informatik 1 2019

Programmfluss

int i = 0;
while(i < 10){
    std::cout << i << " ";

    i++;
}
0 1 2 3 4 5 6 7 8 9

Solange die Condition in den Runden () Klammern erfüllt ist, wird der Code in den geschweiften {} Klammern wiederholt.

For-Loop

Pascal Schärli - PVK Informatik 1 2019

Programmfluss

int i = 0;
while(i < 10){
    std::cout << i << " ";

    i++;
}
  • While-Loops verfolgen häufig die selbe Struktur:
  1. Initialization
  2. Condition
  3. Increment
0 1 2 3 4 5 6 7 8 9 
int i = 0;
i < 10
i++
  • Diese Struktur kann man daher auch schöner mit einem For-Loop schreiben.
  • Der einzige unterschied ist, dass i nun im inneren Scope ist.
for(int i = 0; i < 10; i++){
    std::cout << i << " ";
}

Do-While-Loop

Pascal Schärli - PVK Informatik 1 2019

Programmfluss

  • Alternative zum while-Loop
     
  • Kondition wird erst am Ende geprüft
     
  • Schleifenkörper wird mindestens ein Mal ausgeführt
int i = 1;
do{
    std::cout << i << " ";
    i*=2;
} while(i < 10);
1 2 4 8

Abkürzung

Pascal Schärli - PVK Informatik 1 2019

Programmfluss

Falls ein Statement nur eine Zeile lang ist, kann man die geschweiften {} Klammern weglassen

for (int i = 1; i <= n; ++i){
    std::cout << i << "\n";
}
while (i < n){
    std::cout << ++i << "\n";
}
do{
    std::cout << i++ << "\n";
}while (i <= n);
if(i > 10){
    std::cout << "yes" << std::endl;
}
for (int i = 1; i <= n; ++i)
    std::cout << i << "\n";

while (i < n)
    std::cout << ++i << "\n";

do
    std::cout << i++ << "\n";
while (i <= n);
if(i > 10)
    std::cout << "yes" << std::endl;

Aufgabe

Pascal Schärli - PVK Informatik 1 2019

Programmfluss

// loop 1
for (int i = 1; i <= n; ++i){
    std::cout << i << "\n";
}
  • Welche drei Unterschiede gibt es zwischen diesen drei Loops?

Lösung:

  • Der letzte Loop hat den Output 1 falls \(n \le 0 \)
  • Loops 1 und 3 terminieren nie wenn n der grösstmögliche Integer ist
  • Bei Loop 1 ist i nach dem Ausführen out of scope
// loop 2
int i = 0;
while (i < n){
    std::cout << ++i << "\n";
}
// loop 3
int i = 1;
do{
    std::cout << i++ << "\n";
}while (i <= n);

Pascal Schärli - PVK Informatik 1 2019

Funktionen

Motivation

Pascal Schärli - PVK Informatik 1 2019

Funktionen

Schreibe ein Programm, welches für drei Zahlen a, b und c die Summe a! + b! + c! zurück gibt.

 

  • Wir müssen drei mal denselben Code kopieren um die Fakultät zu berechnen
unsigned int a,b,c;
std::cin >> a >> b >> c;

unsigned int a_fact = 1;
for(int i = 1; i <= a; i++){
	a_fact *= i;
}

unsigned int b_fact = 1;
for(int i = 1; i <= b; i++){
	b_fact *= i;
}

unsigned int c_fact = 1;
for(int i = 1; i <= c; i++){
	c_fact *= i;
}

std::cout << a_fact + b_fact + c_fact << std::endl;

Motivation

Pascal Schärli - PVK Informatik 1 2019

Funktionen

Wie können wir verhindern, immer wieder den selben Code zu kopieren?

 

  • Wir können die Fakultät in eine "Funktion" packen, so dass wir den Algorithmus nur einmal schreiben müssen.
#include <iostream>

unsigned int fact(unsigned int n){
  unsigned int out = 1;
  for(int i = 1; i <= n; i++){
    out *= i;
  }
  return out;
}


int main(){
  unsigned int a,b,c;
  std::cin >> a >> b >> c;
    
  std::cout << fact(a)+fact(b)+fact(c)<<std::endl;
  return 0;
}

Syntax

Pascal Schärli - PVK Informatik 1 2019

Funktionen

int foo(int a, float b, bool c){
    if(c){
        a += b;
    }
    else{
        a-=b;
    }
    return a;
}

Datentyp vom Rückgabewert

Name der Funktion

Beliebig viele Übergabewerte

Funktions-Körper (Berechnung)

Rückgabe des Resultats

Aufgabe

Pascal Schärli - PVK Informatik 1 2019

Funktionen

isPrime(n);{
    for(unsigned int i == 2; i < n/2, i+1){
        if(n % i = 0){
    	    return false
    	}
    }

}
bool isPrime(unsigned int n){
    for(unsigned int i = 2; i <= n/2; i++){
    	if(n % i == 0){
    		return false;
    	}
    }
    return true;
}

Findet die 10 Fehler!

Pre- / Postcondition

Pascal Schärli - PVK Informatik 1 2019

Funktionen



bool inInterval(double x, double left, double right){
	return x >= left && x <= right;
}

Precondition:

  • Was muss bei Funktionsaufruf gelten?
  • Spezifiziert Definitionsbereich der Funktion.

 

//PRE:  left <= right
//POST: returns true iff x is in the Interval [left, right]
bool inInterval(double x, double left, double right){
	return x >= left && x <= right;
}

Postcondition:

  • Was gilt nach Funktionsaufruf?
  • Spezifiziert Wert und Effekt des Funktionsaufrufes.

Forward Declaration

Pascal Schärli - PVK Informatik 1 2019

Funktionen

Was machen wir, wenn wir zwei Funktionen haben, welche sich im Kreis aufrufen?

error: ‘g’ was not declared in this scope



int f(int i){
    if(i < 0) return 1;
    return g(i-1);
}

int g(int i){
    return 2*f(i-1);
}

Forward Declaration

Pascal Schärli - PVK Informatik 1 2019

Funktionen

int g(int i);

int f(int i){
    if(i < 0) return 1;
    return g(i-1);
}

int g(int i){
    return 2*f(i-1);
}

Wir müssen eine Funktion bereits vorher deklarieren, aber noch nicht implementieren. Dies nennt man forward declaration.

Pascal Schärli - PVK Informatik 1 2019

Referenzen

Pascal Schärli - PVK Informatik 1 2019

Referenzen

Namensalias

In C++ können wir existierende Variablen "Verlinken"

int a = 3;
int& b = a;
b = 2;
std::cout << a;
2

Pascal Schärli - PVK Informatik 1 2019

Referenzen

Call by Reference

#include <iostream>

void swap(int a, int b){
    int temp = a;
    a = b;
    b = temp;
}

int main(){
    int a = 2;
    int b = 4;
    swap(a, b);
    std::cout << a << b;
    return 0;   
}
#include <iostream>

void swap(int& a, int& b){
    int temp = a;
    a = b;
    b = temp;
}

int main(){
    int a = 2;
    int b = 4;
    swap(a, b);
    std::cout << a << b;
    return 0;   
}
24
42

Es ist möglich Funktionsargumente als Referenzen zu definieren.

Pascal Schärli - PVK Informatik 1 2019

Referenzen

Motivation

Warum braucht es Referenzen überhaupt?

  • Referenzen erlauben uns mehrere Werte zurückzugeben in einer Funktion.

     
  • Die Übergebenen Parameter müssen nicht kopiert werden.

     
  • Manche Objekte können nicht kopiert werden.
void scale(double& x, double& y, double amount){
    x *= amount;
    y *= amount;
}
void read_i (Vector& v, unsigned int i);
std::ostream o = std::cout;
o << "It works!\n";
std::ostream& o = std::cout;
o << "It works!\n";
It works!
error: use of deleted function

Pascal Schärli - PVK Informatik 1 2019

Rekursion

Pascal Schärli - PVK Informatik 1 2019

Fibonacci

Rekursion

\begin{cases}0 & n = 0\\ 1 & n = 1\\ f(n-1) + f(n-2) & \text{sonst} \end{cases}

\(f(n)=\)

unsigned int f(unsigned int n){
    if(n == 0) return 0;
    if(n == 1) return 1;
    return f(n-1) + f(n-2);
}

In C++ können sich Funktionen selbst "rekursiv" aufrufen. Dies vereinfacht manchmal die Implementation einer Funktion.

int main(){
    for(unsigned int i = 0; i < 10; i++){
        std::cout << f(i) << " ";
    }
    return 0;
}
0 1 1 2 3 5 8 13 21 34

Pascal Schärli - PVK Informatik 1 2019

Beispiel 1

Rekursion

Was ist der Output von diesem Programm?

Welche Mathematische Operation ist es?

int foo(double b, unsigned int e){
    if(e == 0){
        return 1;
    }
    else{
        return b * foo(b, e-1);
    }
}
int main(){
    std::cout << foo(2,2) << std::endl;
    std::cout << foo(2,3) << std::endl;
    std::cout << foo(5,2) << std::endl;
    std::cout << foo(10,9) << std::endl;
    return 0;
}

Pascal Schärli - PVK Informatik 1 2019

Beispiel 1 - Erklärung

Rekursion

int foo(double b, unsigned int e){
    if(e == 0){
        return 1;
    }
    else{
        return b * foo(b, e-1);
    }
}

\( b = 2, e = 2\)

\( 2 * foo(2, 1)\)

\(foo(2, 2)\)

\( b = 2, e = 1\)

\( 2 * foo(2, 0)\)

\(foo(2, 1)\)

\( b = 2, e = 0\)

1

\(foo(2, 0)\)

\( = 2 * 1 = 2\)

\( = 2 * 2 = 4\)

\( b = 2, e = 3\)

\( 2 * foo(2, 2)\)

\(foo(2, 3)\)

\( = 2 * 4 = 8\)

Pascal Schärli - PVK Informatik 1 2019

Beispiel 1 - Lösung

Rekursion

4
8
25
1000000000
#include <iostream>

int foo(double b, unsigned int e){
    if(e == 0){
        return 1;
    }
    else{
        return b * foo(b, e-1);
    }
}

int main(){
    std::cout << foo(2,2) << std::endl;
    std::cout << foo(2,3) << std::endl;
    std::cout << foo(5,2) << std::endl;
    std::cout << foo(10,9) << std::endl;
    return 0;
}

Die Funktion Implementiert das Potenzieren der Basis \(b\) mit dem Exponent \(e\).

 

\(foo(b, e) = b^e\)

Pascal Schärli - PVK Informatik 1 2019

Beispiel 2

Rekursion

Was ist der Output von diesem Programm?

Welche Mathematische Operation ist es?

int foo2(unsigned int l, unsigned int b){
    if(l < b){
        return 0;
    }
    else{
        return 1 + foo2(l / b, b);
    }
}
int main(){
    std::cout << foo2(2,2) << std::endl;
    std::cout << foo2(16,4) << std::endl;
    std::cout << foo2(30,3) << std::endl;
    std::cout << foo2(10000,10) << std::endl;
    return 0;
}

Pascal Schärli - PVK Informatik 1 2019

Rekursion

Beispiel 2 - Erklärung

int foo2(unsigned int l, unsigned int b){
    if(l < b){
        return 0;
    }
    else{
        return 1 + foo(l / b, b);
    }
}

\( l = 10, b = 3\)

\( 1 + foo2(3, 3)\)

\(foo2(10, 3)\)

\( l = 3, b = 3\)

\( 1 + foo2(1, 3)\)

\(foo2(3, 3)\)

\( l = 1, b = 3\)

0

\(foo2(1, 3)\)

\( = 1 + 0 = 1\)

\( = 1 + 1 = 2\)

\( l = 30, b = 3\)

\( 1 + foo2(10, 3)\)

\(foo2(30, 3)\)

\( = 1 + 2 = 3\)

Pascal Schärli - PVK Informatik 1 2019

Beispiel 2 - Lösung

Rekursion

1
2
3
4
#include <iostream>

int foo2(unsigned int l, unsigned int b){
    if(l < b){
        return 0;
    }
    else{
        return 1 + foo2(l / b, b);
    }
}

int main(){
    std::cout << foo2(2,2) << std::endl;
    std::cout << foo2(16,4) << std::endl;
    std::cout << foo2(30,3) << std::endl;
    std::cout << foo2(10000,10) << std::endl;
    return 0;
}

Die Funktion Implementiert das der abgerundete Logarithmus von l zur Basis b.

 

\(foo2(l, b) = \lfloor log_b(l) \rfloor\)

Pascal Schärli - PVK Informatik 1 2019

Rekursive Funktionen Schreiben

Rekursion

  • Rekursive Funktionen haben grundsätzlich immer die selbe Struktur:
    • Abbruchsbedingungen
    • Rekursiver Funktionsaufrufe
unsigned int f(unsigned int n){
    if(n == 0) return 0;
    if(n == 1) return 1;
    return f(n-1) + f(n-2);
}
int foo(double b, unsigned int e){
    if(e == 0) return 1;

    return b * foo(b, e-1);
}
int foo2(unsigned int l, unsigned int b){
    if(l == 1) return 0;

    return 1 + foo(l / b, b);
}

Pascal Schärli - PVK Informatik 1 2019

Rekursive Funktionen Schreiben

Rekursion

  • Die Funktion ruft sich selbst mit einer einfacheren Variante des Problems auf
  • Der Trick zum Schreiben von rekursiven Funktionen ist, dass man davon ausgehen muss, dass die Funktion welche man schreibt bereits Funktioniert.

Pascal Schärli - PVK Informatik 1 2019

Beispiel - Print reverse

Rekursion

Wir wollen eine Funktion schreiben, welche einen String in umgekehrter Reihenfolge printen kann:

//POST: Prints the interval [start, end) of a string
//      in reverse.
void print_reverse(std::string s, int start, int end){



}

int main(){
    std::string s = "KVP olleH";
    print_reverse(s, 0, s.size());
    return 0;
}

Pascal Schärli - PVK Informatik 1 2019

Beispiel - Print reverse

Rekursion

//POST: Prints the interval [start, end) of a string
//      in reverse.
void print_reverse(std::string s, int start, int end){



}

int main(){
    std::string s = "KVP olleH";
    print_reverse(s, 0, s.size());
    return 0;
}

Wir wollen eine Funktion schreiben, welche einen String in umgekehrter Reihenfolge printen kann:

Abbruchsbedingung:

Falls unser Intervall leer ist, müssen wir nichts printen.

//POST: Prints the interval [start, end) of a string
//      in reverse.
void print_reverse(std::string s, int start, int end){
    if(start >= end) return;


}

int main(){
    std::string s = "KVP olleH";
    print_reverse(s, 0, s.size());
    return 0;
}

Pascal Schärli - PVK Informatik 1 2019

Beispiel - Print reverse

Rekursion

//POST: Prints the interval [start, end) of a string
//      in reverse.
void print_reverse(std::string s, int start, int end){
    if(start >= end) return;


}

int main(){
    std::string s = "KVP olleH";
    print_reverse(s, 0, s.size());
    return 0;
}

Wir wollen eine Funktion schreiben, welche einen String in umgekehrter Reihenfolge printen kann:

Rekursiver Funktionsaufruf:

Falls das Intervall nicht leer ist, können wir zuerst unseren String ohne das erste Zeichen rückwärts ausgeben

//POST: Prints the interval [start, end) of a string
//      in reverse.
void print_reverse(std::string s, int start, int end){
    if(start >= end) return;
    print_reverse(s, start+1, end);

}

int main(){
    std::string s = "KVP olleH";
    print_reverse(s, 0, s.size());
    return 0;
}

Pascal Schärli - PVK Informatik 1 2019

Beispiel - Print reverse

Rekursion

//POST: Prints the interval [start, end) of a string
//      in reverse.
void print_reverse(std::string s, int start, int end){
    if(start >= end) return;
    print_reverse(s, start+1, end);

}

int main(){
    std::string s = "KVP olleH";
    print_reverse(s, 0, s.size());
    return 0;
}

Wir wollen eine Funktion schreiben, welche einen String in umgekehrter Reihenfolge printen kann:

Nachdem wir den rest vom String rückwärts ausgegeben haben, müssen wir nur noch das erste Zeichen von unserem Intervall ausgeben.

//POST: Prints the interval [start, end) of a string
//      in reverse.
void print_reverse(std::string s, int start, int end){
    if(start >= end) return;
    print_reverse(s, start+1, end);
    std::cout << s[start];
}

int main(){
    std::string s = "KVP olleH";
    print_reverse(s, 0, s.size());
    return 0;
}

Pascal Schärli - PVK Informatik 1 2019

Beispiel - Print reverse

Rekursion

#include <iostream>

//POST: Prints a string in reverse from start to end
void print_reverse(std::string s, int start, int end){
    if(start >= end) return;
    print_reverse(s, start+1, end);
    std::cout << s[start];
}

int main(){
    std::string s = "KVP olleH";
    print_reverse(s, 0, s.size());
    return 0;
}

Output:

Hello PVK

Pascal Schärli - PVK Informatik 1 2019

Beispiel - Print reverse

Rekursion

print_reverse("KVP",0,3)
    print_reverse("KVP",1,3)
        print_reverse("KVP",2,3)
            print_reverse("KVP",3,3)
            start == end -> return
        std::cout << 'P'
    std::cout << 'V'
std::cout << 'K'
//POST: Prints a string in reverse from start to end
void print_reverse(std::string s, int start, int end){
    if(start >= end) return;
    print_reverse(s, start+1, end);
    std::cout << s[start];
}

P

V

K

Pascal Schärli - PVK Informatik 1 2019

Prüfungsaufgabe

Rekursion

Sommer 2018, 0.72 Notenpunkte

Pascal Schärli - PVK Informatik 1 2019

Prüfungsaufgabe

Basisprüfung Sommer 2018, 0.72 Notenpunkte

Rekursion: Pascalsches Dreieck

row = 1
row = 2
row = 3
row = 4
row = 5

Vervollständigt das gegebene Programm, welches die Zahl für eine gegebene Position berechnet.

pos = 1
pos = 2
pos = 3
pos = 4
pos = 5

Pascal Schärli - PVK Informatik 1 2019

Prüfungsaufgabe

Basisprüfung Sommer 2018, 0.72 Notenpunkte

Rekursion: Pascalsches Dreieck

int main(){
    //Input
    std:: cout<< "Please input a row and a position along the row: ";
    // TODO


    //Check whether the input integers correspond to a valid entry
    assert (check_input_validity(row, pos));

    //Display the result
    std::cout << "The value at row " << row << " and position " << pos
              << " is "<< compute_pascal(row, pos);

    return 0;
}
int main(){
    //Input
    std:: cout<< "Please input a row and a position along the row: ";
    int row, pos;
    std::cin >> row >> pos;

    //Check whether the input integers correspond to a valid entry
    assert (check_input_validity(row, pos));

    //Display the result
    std::cout << "The value at row " << row << " and position " << pos
              << " is "<< compute_pascal(row, pos);

    return 0;
}

Pascal Schärli - PVK Informatik 1 2019

Prüfungsaufgabe

Basisprüfung Sommer 2018, 0.72 Notenpunkte

Rekursion: Pascalsches Dreieck

/* TODO */ check_input_validity(/* TODO */){
    if (/* TODO */){
        std::cout << "Invalid: no element at the given row-position pair.";
        /* TODO */
    }
    /* TODO */    


}
bool check_input_validity(/* TODO */){
    if (/* TODO */){
        std::cout << "Invalid: no element at the given row-position pair.";
        /* TODO */
    }
    /* TODO */    


}
bool check_input_validity(int row, int pos){
    if (/* TODO */){
        std::cout << "Invalid: no element at the given row-position pair.";
        /* TODO */
    }
    /* TODO */    


}
bool check_input_validity(int row, int pos){
    if (row < pos || pos < 1){
        std::cout << "Invalid: no element at the given row-position pair.";
        /* TODO */
    }
    /* TODO */    


}
bool check_input_validity(int row, int pos){
    if (row < pos || pos < 1){
        std::cout << "Invalid: no element at the given row-position pair.";
        return false;
    }
    /* TODO */    


}
bool check_input_validity(int row, int pos){
    if (row < pos || pos < 1){
        std::cout << "Invalid: no element at the given row-position pair.";
        return false;
    }
    else {
        return true;
    } 
}

Pascal Schärli - PVK Informatik 1 2019

Prüfungsaufgabe

Basisprüfung Sommer 2018, 0.72 Notenpunkte

Rekursion: Pascalsches Dreieck

int compute_pascal(int row, int pos){
    if (pos == 1){
        return 1;
    }
    // TODO





}
int compute_pascal(int row, int pos){
    if (pos == 1){
        return 1;
    }
    else if (pos == row){
        return 1;
    }
    // TODO


}
int compute_pascal(int row, int pos){
    if (pos == 1){
        return 1;
    }
    else if (pos == row){
        return 1;
    }
    else {
        return compute_pascal(row-1, pos) + compute_pascal(row-1, pos-1);
    }
}

Pascal Schärli - PVK Informatik 1 2019

BNF/EBNF

BNF

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

  • Die Backus-Naur-Form (BNF) ist ein Rekursiver Weg um Elemente aus einem "Alphabet" mit gegebenen Regeln zusammenzusetzen.

 

  • Sie ist eine Sammlung von Substitutionsregeln, mit welchen alle erlaubten Sätze erstellt werden können.

BNF - Prefix Expression Parser

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer | Integer ’.’ Integer
Integer   = Digit | Integer Digit
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer | Integer ’.’ Integer
Integer   = Digit | Integer Digit
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Digit

Irgend eine beliebige Ziffer von '0' bis '9'

Beispiele

0, 5, 9

BNF - Prefix Expression Parser

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer | Integer ’.’ Integer
Integer   = Digit | Integer Digit
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Integer

Zwischen 1 und ∞ viele Ziffern aneinander gehängt

Beispiele

1, 0034, 089457029348720398712304190857

BNF - Prefix Expression Parser

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer | Integer ’.’ Integer
Integer   = Digit | Integer Digit
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Number

Entweder 1 Integer oder 2 Integer mit '.' getrennt

Beispiele

0, 1.1, 01.1200, 3.14159

BNF - Prefix Expression Parser

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer | Integer ’.’ Integer
Integer   = Digit | Integer Digit
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Operand

Entweder eine Number oder eine Expression

Beispiele

0, 1, 2.2, [+ 1 2, + 1 * 2 3]

BNF - Prefix Expression Parser

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer | Integer ’.’ Integer
Integer   = Digit | Integer Digit
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Operator

Irgend ein beliebiger Operator '+', '-', '/', '*'

Beispiele

+, -, /, *

BNF - Prefix Expression Parser

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer | Integer ’.’ Integer
Integer   = Digit | Integer Digit
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

Ausrücke in der Prefix-Schreibweise. In der Prefix-Schreibweise wird jeweils der Operator zuerst geschrieben.
(\(1 + 2 \rightarrow + 1 2\))

Beispiele

+ 2 3.12 ,  * 1 - 2.5 0, - 1 * 2 3 / 2 3

BNF - Prefix Expression Parser

EBNF

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

  • Die Extended-Backus-Naur-Form hat zusätzliche Syntax
    -> kompaktere Notationen
  • {...} -> Inhalt kann beliebig viel (inkl. 0) Mal wiederholt werden.
  • [...] -> Inhalt wird entweder 0 oder 1 Mal wiederholt
Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer | Integer ’.’ Integer
Integer   = Digit | Integer Digit
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

BNF

EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Entspricht der folgende String einer gültigen Expression?

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

+

*

3

2

9

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

+

*

3

2

9

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

Operator

Operand

Operand

+

*

3

2

9

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

Operator

Operand

Operand

+

+

*

3

2

9

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

Operator

Operand

Operand

+

Number

Expression

+

*

3

2

9

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

Operator

Operand

Operand

+

Number

Expression

+

*

3

2

9

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

Operator

Operand

Operand

+

Number

Expression

+

*

3

2

9

Operator

Operand

Operand

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

Operator

Operand

Operand

+

Number

Expression

+

*

3

2

9

Operator

Operand

Operand

*

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

Operator

Operand

Operand

+

Number

Expression

+

*

3

2

9

Operator

Operand

Operand

*

Number

Expression

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

Operator

Operand

Operand

+

Number

Expression

+

*

3

2

9

Operator

Operand

Operand

*

Number

Expression

3

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

Operator

Operand

Operand

+

Number

Expression

+

*

3

2

9

Operator

Operand

Operand

*

Number

Expression

3

Number

Expression

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

Operator

Operand

Operand

+

Number

Expression

+

*

3

2

9

Operator

Operand

Operand

*

Number

Expression

3

Number

Expression

2

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

Operator

Operand

Operand

+

Number

Expression

+

*

3

2

9

Operator

Operand

Operand

*

Number

Expression

3

Number

Expression

2

Number

Expression

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

Operator

Operand

Operand

+

Number

Expression

+

*

3

2

9

Operator

Operand

Operand

*

Number

Expression

3

Number

Expression

2

Number

Expression

9

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

Operator

Operand

Operand

+

Number

Expression

+

*

3

2

9

Operator

Operand

Operand

*

Number

Expression

3

Number

Expression

2

Number

Expression

9

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Entspricht der folgende String einer gültigen Expression?

/

7

5

-

0

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

/

7

5

-

0

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

/

7

5

-

0

Operator

Operand

Operand

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

/

7

5

-

0

Operand

Operand

Operator

/

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

/

7

5

-

0

Operand

Operand

Operator

/

Number

Expression

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

/

7

5

-

0

Operand

Operand

Operator

/

Number

Expression

7

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

/

5

-

0

Operand

Operator

/

Number

Expression

7

Operand

Number

Expression

7

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

/

5

-

0

Operand

Operator

/

Number

Expression

7

Operand

7

Number

Expression

5

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Expression

/

5

-

0

Operand

Operator

/

Number

Expression

7

Operand

7

Number

Expression

5

Die BNF Konnte nicht den ganzen String Parsen.

\(\rightarrow\) invalid

BNF - Beispiel

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

EBNF in C++

  • Für jede Regel erstellen wir eine Funktion mit Rückgabetyp bool und einem instream als Übergabetyp.
  • Wir returnen true, falls unsere Expression am Anfang vom String steht
  • Ansonsten returnen wir false 
Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

EBNF in C++

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’ 
// POST: returns true if a digit could
//  be consumed from in
// digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | 
//          ’5’ | ’6’ | ’7’ | ’8’ | ’9’
bool digit(std::istream& is){
    char next = lookahead(is);
    if(next >= '0' && next <= '9'){
        is >> next;
        return true;
    }
    return false;
}

112.3 + 2

112.3 + 2

+ 5 - 1 2.2

true
false

+ 5 - 1 2.2

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

EBNF in C++

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’ 
// POST: returns true if an unsigned integer
//        could be consumed from in
// integer = digit { digit }
bool integer(std::istream& is){
    if(!digit(is)){
        return false;
    }
    while(digit(is));
    return true;
}

112.3 + 2

112.3 + 2

true
false

+ 5 - 1 2.2

+ 5 - 1 2.2

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

EBNF in C++

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’ 
// POST: returns true if an unsigned
//       floating point number could
//       be consumed from in
// number = integer [’.’ integer]
bool number(std::istream& is){
    if(!integer(is)){
        return false;
    }
    if(lookahead(is) == '.'){
        char dot;
        is >> dot;
        return integer(is);
    }
    else{
        return true;
    }
}

112.3 + 2

112.3 + 2

true
false

+ 5 - 1 2.2

+ 5 - 1 2.2

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

EBNF in C++

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’ 
// POST: returns true if an operator
//       could be consumed from in
// operator  = ’+’ | ’-’ | ’/’ | ’*’
bool operator_(std::istream& is){
    std::vector<char> o = {'+','-','*','/'};
    char next = lookahead(is);
    for(unsigned int i = 0; i < 4; i++){
        if(next==o[i]){
            consume(is, next);
            return true;
        }
    }
    return false;
}

112.3 + 2

112.3 + 2

false

true

+ 5 - 1 2.2

+ 5 - 1 2.2

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

EBNF in C++

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’ 
// POST: returns true if an operand could
//       be consumed from in
// operand   = number | expression
bool operand(std::istream& is){
    char next = lookahead(is);
    if(next == '+' || next == '-' ||
       next == '*' || next == '/'){
        return expression(is);
    }
    else{
        return number(is);
    }
}

112.3 + 2

+ 5  +  1

+ 5  +  1

112.3 + 2

true
false

Das Programm versuchte eine Expression  zu parsen, aber es fehlt das Ende

Pascal Schärli - PVK Informatik 1 2019

BNF / EBNF

EBNF in C++

Expression = Operator ’ ’ Operand ’ ’ Operand
Operator  = ’+’ | ’-’ | ’/’ | ’*’
Operand   = Number | Expression
Number    = Integer [’.’ Integer]
Integer   = Digit { Digit }
Digit= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’ 
// POST: returns true if an expression
//       could be consumed from in
// expression = operator_ operand operand
bool expression(std::istream& is){
    if(!operator_(is)) return false;
    if(!consume(is,' ')) return false;
    if(!operand(is)) return false;
    if(!consume(is,' ')) return false;
    if(!operand(is)) return false;
    return true;
}

112.3 + 2

+ 5 - 1 2.2

+ 5 - 1 2.2

112.3 + 2

false

true

Pascal Schärli - PVK Informatik 1 2019

Prüfungsaufgabe

EBNF

Sommer 2017, 1.37 Notenpunkte

Pascal Schärli - PVK Informatik 1 2019

EBNF I

Prüfungsaufgabe

Basisprüfung Sommer 2017, 0.59 Notenpunkte

Statement = Expression ';'.
Expression = Simple [':' Simple].
Simple = Designator | Integer.
Designator = Identifier {'.' Identifier | '(' [ExpressionList] ')'}
ExpressionList = Expression { ',' Expression }.

Integer = Digit {Digit}
Digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' .

Identifier = Letter { Letter }
Letter = 'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' | 'h' | 'i' | 'j' .
a(2:5);
a(b).c:d;
a(3).3;
a(3):3;

Welche der folgenden Zeichenketten sind gültige Statements gemäss der EBNF?

Pascal Schärli - PVK Informatik 1 2019

EBNF I

Prüfungsaufgabe

Basisprüfung Sommer 2017, 0.59 Notenpunkte

Statement = Expression ';'.
Expression = Simple [':' Simple].
Simple = Designator | Integer.
Designator = Identifier {'.' Identifier | '(' [ExpressionList] ')'}
ExpressionList = Expression { ',' Expression }.

Integer = Digit {Digit}
Digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' .

Identifier = Letter { Letter }
Letter = 'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' | 'h' | 'i' | 'j' .

Ändern Sie genau eine Produktionsregel der EBNF ab, so dass folgende Anweisung (Statement) gültig wird:

a3(c3):a4(c4);
Statement = Expression ';'.
Expression = Simple [':' Simple].
Simple = Designator | Integer.
Designator = Identifier {'.' Identifier | '(' [ExpressionList] ')'}
ExpressionList = Expression { ',' Expression }.

Integer = Digit {Digit}
Digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' .

Identifier = Letter { Letter | Digit }
Letter = 'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' | 'h' | 'i' | 'j' .

Pascal Schärli - PVK Informatik 1 2019

EBNF II

Prüfungsaufgabe

Basisprüfung Sommer 2017, 0.78 Notenpunkte

Wir haben diesen Code, mit welchem identifiziert werden soll, ob eine Zeichenkette im Sinne der vorherigen EBNF ein gültiges Statement darstellt.

bool Expression (std::istream& is);

// ExpressionList = Expression { ’,’ Expression }.
bool ExpressionList(std::istream& is){
    if (!Expression(is)) return false;
    
    // TODO

    return true;
}

// Designator = Identifier {’.’ Identifier 
//             | ’(’ [ExpressionList] ’)’}.
bool Designator(std::istream& is){
    if (!Identifier(is)) return false;
    while(true){
        if (has(is, ’.’)){
            // TODO
        }
        else if (has(is, ’(’)){
            bool ignore = ExpressionList(is);
            // TODO
        } else
            return true;
    }
}
// Simple = Designator | Integer.
bool Simple(std::istream& is){
    return Integer(is) || Designator(is);
}

// Expression = Simple [’:’ Simple].
bool Expression(std::istream& is){
    if (!Simple(is)) return false;
    return // TODO ;
}

// Statement = Expression ’;’.
bool Statement(std::istream& is){
    return Expression(is) && has(is, ’;’);
}

Pascal Schärli - PVK Informatik 1 2019

EBNF II

Prüfungsaufgabe

Basisprüfung Sommer 2017, 0.78 Notenpunkte

Folgender Code, welcher nur als Funktionsdeklaration vorliegt, soll als korrekt implementiert vorausgesetzt werden:

// POST: when the next available non-whitespace character equals c,
//it is consumed and the function returns true,
//otherwise the function returns false.
bool has(std::istream& is, char c);

// Integer = Digit {Digit}.
bool Integer (std::istream& is);

// Identifier = Letter {Letter}.
bool Identifier (std::istream& is);

Pascal Schärli - PVK Informatik 1 2019

EBNF II

Prüfungsaufgabe

Basisprüfung Sommer 2017, 0.78 Notenpunkte

Warum wird die Funktion Expression anscheinend zweimal deklariert?

Es gibt eine zirkuläre Abhängigkeit zwischen den Funktionen. Daher muss mindestens eine Funktion vor ihrer Definition deklariert werden (forward declaration).

Sonst wäre sie in mindestens einer anderen Funktion nicht sichtbar.

Pascal Schärli - PVK Informatik 1 2019

EBNF II

Prüfungsaufgabe

Basisprüfung Sommer 2017, 0.78 Notenpunkte

bool Expression (std::istream& is);

// ExpressionList = Expression { ’,’ Expression }.
bool ExpressionList(std::istream& is){
    if (!Expression(is)) return false;
    
    // TODO

    return true;
}

// Designator = Identifier {’.’ Identifier 
               | ’(’ [ExpressionList] ’)’}.
bool Designator(std::istream& is){
    if (!Identifier(is)) return false;
    while(true){
        if (has(is, ’.’)){
            // TODO
        }
        else if (has(is, ’(’)){
            bool ignore = ExpressionList(is);
            // TODO
        } else
            return true;
    }
}
// Simple = Designator | Integer.
bool Simple(std::istream& is){
    return Integer(is) || Designator(is);
}

// Expression = Simple [’:’ Simple].
bool Expression(std::istream& is){
    if (!Simple(is)) return false;
    return // TODO ;
}

// Statement = Expression ’;’.
bool Statement(std::istream& is){
    return Expression(is) && has(is, ’;’);
}
bool Expression (std::istream& is);

// ExpressionList = Expression { ’,’ Expression }.
bool ExpressionList(std::istream& is){
    if (!Expression(is)) return false;
    while (has(is, ’,’)){
        if (!Expression(is)) return false;
    }
    return true;
}

// Designator = Identifier {’.’ Identifier 
               | ’(’ [ExpressionList] ’)’}.
bool Designator(std::istream& is){
    if (!Identifier(is)) return false;
    while(true){
        if (has(is, ’.’)){
            // TODO
        }
        else if (has(is, ’(’)){
            bool ignore = ExpressionList(is);
            // TODO
        } else
            return true;
    }
}
bool Expression (std::istream& is);

// ExpressionList = Expression { ’,’ Expression }.
bool ExpressionList(std::istream& is){
    if (!Expression(is)) return false;
    while (has(is, ’,’)){
        if (!Expression(is)) return false;
    }
    return true;
}

// Designator = Identifier {’.’ Identifier 
               | ’(’ [ExpressionList] ’)’}.
bool Designator(std::istream& is){
    if (!Identifier(is)) return false;
    while(true){
        if (has(is, ’.’)){
            if (!Identifier(is)) return false;
        }
        else if (has(is, ’(’)){
            bool ignore = ExpressionList(is);
            // TODO
        } else
            return true;
    }
}
bool Expression (std::istream& is);

// ExpressionList = Expression { ’,’ Expression }.
bool ExpressionList(std::istream& is){
    if (!Expression(is)) return false;
    while (has(is, ’,’)){
        if (!Expression(is)) return false;
    }
    return true;
}

// Designator = Identifier {’.’ Identifier 
//             | ’(’ [ExpressionList] ’)’}.
bool Designator(std::istream& is){
    if (!Identifier(is)) return false;
    while(true){
        if (has(is, ’.’)){
            if (!Identifier(is)) return false;
        }
        else if (has(is, ’(’)){
            bool ignore = ExpressionList(is);
            if (!has(is,’)’)) return false;
        } else
            return true;
    }
}
// Simple = Designator | Integer.
bool Simple(std::istream& is){
    return Integer(is) || Designator(is);
}

// Expression = Simple [’:’ Simple].
bool Expression(std::istream& is){
    if (!Simple(is)) return false;
    return !has(is,’:’) || Simple(is) ;
}

// Statement = Expression ’;’.
bool Statement(std::istream& is){
    return Expression(is) && has(is, ’;’);
}

Pascal Schärli - PVK Informatik 1 2019

Structs & Klassen

Pascal Schärli - PVK Informatik 1 2019

Objekte

Structs & Klassen

  • Abgesehen von den Primitiven Datentypen gibt es auch komplexere Datentypen.
  • Diese können mehr Funktionalität beinhalten.
  • Diese Typen sind dem Compiler nicht standardmässig bekannt
    -> Sie müssen entweder selbst geschrieben oder importiert werden

Pascal Schärli - PVK Informatik 1 2019

Vektor

  • Ein Beispiel für ein solches Objekt ist der Vektor
  • Vor der Verwendung muss dieser mit #include<vector> importiert werden.
  • Beim erstellen von einem neuen Vektor muss immer noch der zu speichernde Datentyp angegeben werden.
  • Bei Bedarf kann auch die Anzahl Elemente, der Initialisierungswert oder eine Liste gegeben werden.
#include <vector>

std::vector<int> a;          // empty vector of ints
std::vector<float> b(5);     // five floats with value 0
std::vector<double> c(5,3);  // five doubles with value 3
std::vector <int> d = {1, 2};// two integers with values 1, 2

Beispiele:

Structs & Klassen

Pascal Schärli - PVK Informatik 1 2019

Vektor

  • Mit der Funktion at oder dem [] operator kann man auf Elemente im Vektor zugreifen.
  • Wir haben Indizierung bei 0, das heisst das vorderste Element hat den Index 0.
#include <vector>
#include <iostream>

int main(){
    std::vector<char> v = {'<', '1', '3', 'n', 'i', ' ', 'f'};
    std::cout << v[4] << v[3] << v.at(6) << v[1] << v.at(5) << v[0] << v[2];
    return 0;
}

Output

inf1 <3

Structs & Klassen

Pascal Schärli - PVK Informatik 1 2019

Vektor

Vektoren sind keine Primitive Datentypen. Sie haben noch weitere Funktionalitäten:

Name Returns

Grösse (Länge) vom Vektor

true falls Vektor leer ist, sonst false

Fügt Element am ende dazu

Löscht  letztes Element

Iterator auf Start vom Vektor

Eine komplette Liste findet ihr hier unter "Member Functions"

size
empty
push_back
pop
begin
end

Iterator auf Ende vom Vektor

Structs & Klassen

Structs

  • Structs erlauben uns eigene "Datentypen" zu erstellen.
  • Sie sind eine Kollektion von Variablen und Funktionen
  • Nach der Deklaration braucht es ein Semicolon ;

Pascal Schärli - PVK Informatik 1 2019

struct my_struct_t{
    int n;
    bool b = true;
};

Unser eigener Datentyp mit dem Namen my_struct_t

Der Struct beinhaltet eine Variable n

Semicolon nach der Deklaration

Die Variable b hat standardmässig den Wert true

Structs & Klassen

Initialisierung

Pascal Schärli - PVK Informatik 1 2019

  • Einen Struct kann man initialisieren in dem man alle Initialisierungswerte in geschwungenen {} Klammern schreibt.
  • Diese Werte werden dann in der entsprechenden Reihenfolge in die Variablen geschrieben
  • Elemente können mit "." ausgelesen werden
struct my_struct_t{
    int n;
    bool b = true;
};
int main(){
    my_struct_t s = {2, true};
    if(s.b){
        s.n = 3;
    }
}

Initialisierung mit {} Klammern

Auf b kann mit s.b zugegriffen werden

Man kann die Variablen schreiben und lesen

Structs & Klassen

Initialisierung

Pascal Schärli - PVK Informatik 1 2019

  • Man kann auch eine Funktion schreiben, welche zum erstellen von einem Struct dient.
  • Diese Funktion nennt man Konstruktor.
  • Sie hat denselben Namen wie der Struct und sie hat keinen Rückgabetyp.
struct my_struct_t{
    int n;
    bool b = true;
    my_struct_t(int a){
        n = a;
    }
};
int main(){
    my_struct_t s(2);
    std::cout << s.n << " " << s.b;
}

Konstruktor hat keinen Rückgabetyp und denselben Namen wie der Struct

Bei der Initialisierung wird der Konstruktor aufgerufen

Output

2 1

Structs & Klassen

Initialisierung

Pascal Schärli - PVK Informatik 1 2019

  • Die Initialisierung von Variablen kann abgekürzt werden
  • Man Initialisiert alle Variablen auf der selben Linie wie der Konstruktor.
struct my_struct_t{
    int n;
    bool b;
    my_struct_t(int a): n(a), b(true){}
};
int main(){
    my_struct_t s(2);
    std::cout << s.n << " " << s.b;
}

Die Variable n wird mit a initialisert und die Variable b wird mit true initialisiert.

Der Konstruktor kann immer noch gleich aufgerufen werden.

Output

2 1

Structs & Klassen

Funktionen

Pascal Schärli - PVK Informatik 1 2019

  • Structs können auch Funktionen beinhalten
  • Diese können genau gleich wie die Variabeln mit einem "." benutzt werden
struct my_struct_t{
    int n;
    bool b;
    my_struct_t(int a): n(a), b(true){}
    void print_conditional(){
        if(b){
            std::cout << this->n;
        }
    }
};
int main(){
    my_struct_t s(2);
    s.print_conditional();
}

Wir definieren eine Funktion innerhalb von unserem Struct

Output

2

Structs & Klassen

Diese Funktion können wir dann auf ein bestimmtes Objekt angewendet aufrufen.

Mit dem Keyword this bekommen wir einen Pointer auf uns selbst

Kapselung

Pascal Schärli - PVK Informatik 1 2019

Structs & Klassen

  • Mit Kapselung ist es möglich zu steuern, wer alles Zugriff auf ein Member (Variable / Funktion) hat.
  • Das Keyword private macht, dass alle folgenden Funktionen / Variablen nur von innerhalb vom Objekt benutzt werden können.
  • Das Keyword public macht, dass alle folgenden Funktionen / Variablen auch von ausserhalb vom Objekt benutzt werden können.

Kapselung

Pascal Schärli - PVK Informatik 1 2019

Structs & Klassen

struct my_struct_t{
private:
    int n;
    bool b;
public:
    my_struct_t(int a): n(a), b(true){}
    void print_conditional(){
        if(b){
            std::cout << n;
        }
    }
};
int main(){
    my_struct_t s(2);
    s.print_conditional();
}
int main(){
    my_struct_t s(2);
    std::cout << s.n << " " << s.b;
}

Output

2

Klassen

Pascal Schärli - PVK Informatik 1 2019

Structs & Klassen

  • Klassen können in C++ genau gleich wie Structs verwendet werden.
  • Der Unterschied ist, dass Members von Klassen standardmässig private sind, während Members von Structs standardmässig public sind.

Pascal Schärli - PVK Informatik 1 2019

Überladung

Function Overloading

Pascal Schärli - PVK Informatik 1 2019

Überladung

In C++ ist es möglich, dass mehrere Funktionen den gleichen Namen haben, solange sich die Übergabewerte unterscheiden.

int foo1(int a){ ... }
int foo1(int a, int b){ ... }
int foo2(int a){ ... }
int foo2(float a){ ... }
int foo3(int a){ ... }
int foo3(int b){ ... }
int foo4(int a){ ... }
float foo4(int a){ ... }

richtig

falsch

Es reicht nicht, wenn sich nur die Variabelnamen unterscheiden.

Es reicht nicht, wenn sich nur der Rückgabetyp unterscheidet.

Function Overloading

Pascal Schärli - PVK Informatik 1 2019

Überladung

#include <iostream>

void out (const int i) {
    std::cout << i << " (int)\n";
}

void out (const double i) {
    std::cout << i << " (double)\n";
}

int main () {
    out(3.5);
    out(2);
    out(2.0);
    out(0);
    out(0.0);
    return 0;
}
3.5 (double)
2 (int)
2 (double)
0 (int)
0 (double)

Operator Overloading

Pascal Schärli - PVK Informatik 1 2019

Überladung

Genau wie Funktionen können auch Operatoren wie +-*/ überschrieben werden.

struct vec_t {
    double x;
    double y;
    double z;
};

Als Beispiel überladen wir Operatoren für diesen Struct, welcher Punkte im dreidimensionalen Koordinatensystem darstellt:

Addition

Pascal Schärli - PVK Informatik 1 2019

Überladung

vec_t operator+(const vec_t& lhs, const vec_t& rhs) {
  vec_t out;
  out.x = lhs.x + rhs.x;
  out.y = lhs.y + rhs.y;
  out.z = lhs.z + rhs.z;
  return out;
}
struct vec_t {
    double x;
    double y;
    double z;
};

Die Summe von zwei Vektoren ist immernoch ein Vektor

Wir überladen den + Operator

linker Summand

rechter Summand

call by reference damit nicht das ganze Objekt kopiert werden muss

constant damit die Summanden trotz call by Reference nicht verändert weren.

Output

Pascal Schärli - PVK Informatik 1 2019

Überladung

std::ostream& operator<< (std::ostream &out, const vec_t& vec) {
    out << "(" << vec.x << "," << vec.y << "," << vec.z << ")";
    return out;
}
struct vec_t {
    double x;
    double y;
    double z;
};

Der outstream wird returned, damit mehrere Werte auf der selben Zeile gelesen werden können

Wir überladen den << Operator

Unser outstream
(zB. std::cout)

Vektor den wir ausgeben wollen

call by reference weil streams nicht kopiert werden können

constant und call by reference wie bei der Addition

Gibt den Vektor als String aus: zB (1,2.5,3.5)

Output

Pascal Schärli - PVK Informatik 1 2019

Überladung

struct vec_t {
    double x;
    double y;
    double z;
};

Warum müssen wir wieder einen Outstream als Return-Wert haben?

std::cout << vec1 << vec2;

Dies ist nötig, damit wir mehrere Objekte auf derselben Zeile ausgeben können.

Output

Pascal Schärli - PVK Informatik 1 2019

Überladung

struct vec_t {
    double x;
    double y;
    double z;
};

Warum müssen wir wieder einen Outstream als Return-Wert haben?

std::cout << vec1 << vec2;

Weil der << Operator von links nach rechts ausgewertet wird, wird zuerst vec1 eingelesen.

std::ostream& operator<< (std::ostream &out, const vec_t& vec) {
    out << "(" << vec.x << "," << vec.y << "," << vec.z << ")";
    return out;
}

Output

Pascal Schärli - PVK Informatik 1 2019

Überladung

struct vec_t {
    double x;
    double y;
    double z;
};

Warum müssen wir wieder einen Outstream als Return-Wert haben?

std::cout << vec1 << vec2;

Weil der << Operator von links nach rechts ausgewertet wird, wird zuerst vec1 eingelesen.

std::ostream& operator<< (std::ostream &out, const vec_t& vec) {
    out << "(" << vec.x << "," << vec.y << "," << vec.z << ")";
    return out;
}
std::cout
vec1

Output

Pascal Schärli - PVK Informatik 1 2019

Überladung

struct vec_t {
    double x;
    double y;
    double z;
};

Warum müssen wir wieder einen Outstream als Return-Wert haben?

       std::cout  << vec2;

Nach dem vec1 ausgegeben wurde wird unser Outstream, in diesem Beispiel std::cout zurückgegeben.

std::ostream& operator<< (std::ostream &out, const vec_t& vec) {
    out << "(" << vec.x << "," << vec.y << "," << vec.z << ")";
    return out;
}

Output

Pascal Schärli - PVK Informatik 1 2019

Überladung

struct vec_t {
    double x;
    double y;
    double z;
};

Warum müssen wir wieder einen Outstream als Return-Wert haben?

       std::cout  << vec2;

So haben wir wieder einen Outstream, mit welchem wir vec2 ausgeben können.

std::ostream& operator<< (std::ostream &out, const vec_t& vec) {
    out << "(" << vec.x << "," << vec.y << "," << vec.z << ")";
    return out;
}
std::cout
vec2

Input

Pascal Schärli - PVK Informatik 1 2019

Überladung

std::istream& operator>> (std::istream &in, vec_t& vec) {
    char c;
    in >> c >> vec.x >> c >> vec.y >> c >> vec.z >> c;
    return in;
}
struct vec_t {
    double x;
    double y;
    double z;
};

Der instream wird auch hier zurückgegeben damit mehrere Werte auf der selben Zeile gelesen werden können

Wir überladen den >> Operator

Unser instream
(zB. std::cin)

Vektor den wir einlesen wollen

call by reference weil streams nicht kopiert werden können

kein constant aber trotzdem eine Referenz, da wir beim Einlesen das Objekt verändern wollen

Liest einen Vektor ein zB (1,2.5,3.5)

Input

Pascal Schärli - PVK Informatik 1 2019

Überladung

std::istream& operator>> (std::istream &in, vec_t& vec) {
    char c;
    in >> c >> vec.x >> c >> vec.y >> c >> vec.z >> c;
    return in;
}
struct vec_t {
    double x;
    double y;
    double z;
};

Wir definieren einen wegwerf Charakter c, welcher alle Klammern und Kommas "schluckt"

Input

Pascal Schärli - PVK Informatik 1 2019

Überladung

std::istream& operator>> (std::istream &in, vec_t& vec) {
    char c;
    in >> c >> vec.x >> c >> vec.y >> c >> vec.z >> c;
    return in;
}
struct vec_t {
    double x;
    double y;
    double z;
};
vec_t vec
x = ?
y = ?
z = ?
char c
?
std::instream & in
(1,2.5,3.5)

Input

Pascal Schärli - PVK Informatik 1 2019

Überladung

std::istream& operator>> (std::istream &in, vec_t& vec) {
    char c;
    in >> c >> vec.x >> c >> vec.y >> c >> vec.z >> c;
    return in;
}
struct vec_t {
    double x;
    double y;
    double z;
};
vec_t vec
x = ?
y = ?
z = ?
char c
'('

std::instream & in
(1,2.5,3.5)

Input

Pascal Schärli - PVK Informatik 1 2019

Überladung

std::istream& operator>> (std::istream &in, vec_t& vec) {
    char c;
    in >> c >> vec.x >> c >> vec.y >> c >> vec.z >> c;
    return in;
}
struct vec_t {
    double x;
    double y;
    double z;
};
vec_t vec
x = 1
y = ?
z = ?
char c
'('

std::instream & in
(1,2.5,3.5)

Input

Pascal Schärli - PVK Informatik 1 2019

Überladung

std::istream& operator>> (std::istream &in, vec_t& vec) {
    char c;
    in >> c >> vec.x >> c >> vec.y >> c >> vec.z >> c;
    return in;
}
struct vec_t {
    double x;
    double y;
    double z;
};
vec_t vec
x = 1
y = ?
z = ?
char c
','

std::instream & in
(1,2.5,3.5)

Input

Pascal Schärli - PVK Informatik 1 2019

Überladung

std::istream& operator>> (std::istream &in, vec_t& vec) {
    char c;
    in >> c >> vec.x >> c >> vec.y >> c >> vec.z >> c;
    return in;
}
struct vec_t {
    double x;
    double y;
    double z;
};
vec_t vec
x = 1
y = 2.5
z = ?
char c
','

std::instream & in
(1,2.5,3.5)

Input

Pascal Schärli - PVK Informatik 1 2019

Überladung

std::istream& operator>> (std::istream &in, vec_t& vec) {
    char c;
    in >> c >> vec.x >> c >> vec.y >> c >> vec.z >> c;
    return in;
}
struct vec_t {
    double x;
    double y;
    double z;
};
vec_t vec
x = 1
y = 2.5
z = ?
char c
','

std::instream & in
(1,2.5,3.5)

Input

Pascal Schärli - PVK Informatik 1 2019

Überladung

std::istream& operator>> (std::istream &in, vec_t& vec) {
    char c;
    in >> c >> vec.x >> c >> vec.y >> c >> vec.z >> c;
    return in;
}
struct vec_t {
    double x;
    double y;
    double z;
};
vec_t vec
x = 1
y = 2.5
z = 3.5
char c
','

std::instream & in
(1,2.5,3.5)

Input

Pascal Schärli - PVK Informatik 1 2019

Überladung

std::istream& operator>> (std::istream &in, vec_t& vec) {
    char c;
    in >> c >> vec.x >> c >> vec.y >> c >> vec.z >> c;
    return in;
}
struct vec_t {
    double x;
    double y;
    double z;
};
vec_t vec
x = 1
y = 2.5
z = 3.5
char c
')'

std::instream & in
(1,2.5,3.5)

Operator Overloading

Pascal Schärli - PVK Informatik 1 2019

Überladung

Das Überladen dieser Operatoren erlaubt es uns unsere eigenen Objekte mit den normalen Operatoren zu manipulieren:

#include <iostream>

struct vec_t {
  double x;
  double y;
  double z;
};

vec_t operator+(const vec_t& lhs, const vec_t& rhs) {
  vec_t out;
  out.x = lhs.x + rhs.x;
  out.y = lhs.y + rhs.y;
  out.z = lhs.z + rhs.z;
  return out;
}

std::ostream& operator<< (std::ostream &out, vec_t vec) {
    out << "(" << vec.x << "," << vec.y << "," << vec.z << ")";
    return out;
}

std::istream& operator>> (std::istream &in, vec_t& vec) {
    char c;
    in >> c >> vec.x >> c >> vec.y >> c >> vec.z >> c;
    return in;
}
int main () {
  vec_t a, b;
  std::cin >> a >> b;
  std::cout << a + b << std::endl;
}

Input:

(1,2.5,3.5)
(1,2,3)

Output:

(2,4.5,6.5)

In-Class Overloading

Pascal Schärli - PVK Informatik 1 2019

Überladung

  • Operatoren können auch in-class Überladen werden.
  • Diese wird für das Objekt auf der linken Seite des Operators aufgerufen
struct vec_t {
  double x;
  double y;
  double z;

  vec_t& operator-=(const vec_t& v){
    x -= v.x;
    y -= v.y;
    z -= v.z;
    return *this;
  }
};

Es wird ein L-Wert zurückgegeben

Wir überladen den -= Operator

Wir können unsere eigenen Variabeln ohne prefix verändern

Der Rückgabewert ist das Objekt selbst

Pascal Schärli - PVK Informatik 1 2019

Prüfungsaufgabe

Klassen/Datenstrukturen

Winter 2017, 0.83 Notenpunkte

Pascal Schärli - PVK Informatik 1 2019

Klassen und Operator Overloading

Prüfungsaufgabe

Basisprüfung Winter 2017, 0.83 Notenpunkte

class Time{
    int sec; // total number of seconds
    public:
    // construct time from hours, minutes and seconds
    Time (int h, int m, int s): sec(s+m*60+h*3600){}

    // write time to stream out
    void write (std::ostream& out) const {
        out << sec / 3600 % 24 << ":" 
            << sec / 60 % 60 << ":" << sec % 60;
    }
};
int main(){
    Time second (0,0,1);
    Time examStart (14,04,58);
    Time examDuration (01,02,05);
    Time examEnd = examStart + examDuration;
    for (Time t=examStart; t != examEnd; t += second){
        std::cout << t << std::endl;
    }
    
    return 0;
}

Output:

14:4:58
14:4:59

14:5:0
14:5:1
...
14:7:2

Überladet die nötigen Operatoren, damit die Mainfunktion so funktioniert.

Pascal Schärli - PVK Informatik 1 2019

Klassen und Operator Overloading

Prüfungsaufgabe

Basisprüfung Winter 2017, 0.83 Notenpunkte

class Time{
    int sec; // total number of seconds
    public:
    // construct time from hours, minutes and seconds
    Time (int h, int m, int s): sec(s+m*60+h*3600){}

    // add t to this time
    /* TODO */ operator+= (const Time& t){
        // TODO

    }

    // two times match when they represent the same time during a day
    // Example: 0:0:5 must match 24:0:5
    bool operator==(/* TODO */){
        // TODO
    }

    // write time to stream out
    void write (std::ostream& out) const {
        out << sec / 3600 % 24 << ":" 
            << sec / 60 % 60 << ":" << sec % 60;
    }
};
class Time{
    int sec; // total number of seconds
    public:
    // construct time from hours, minutes and seconds
    Time (int h, int m, int s): sec(s+m*60+h*3600){}

    // add t to this time
    Time& operator+= (const Time& t){
        sec += t.sec;
        return *this;
    }

    // two times match when they represent the same time during a day
    // Example: 0:0:5 must match 24:0:5
    bool operator==(/* TODO */){
        // TODO
    }

    // write time to stream out
    void write (std::ostream& out) const {
        out << sec / 3600 % 24 << ":" 
            << sec / 60 % 60 << ":" << sec % 60;
    }
};
class Time{
    int sec; // total number of seconds
    public:
    // construct time from hours, minutes and seconds
    Time (int h, int m, int s): sec(s+m*60+h*3600){}

    // add t to this time
    Time& operator+= (const Time& t){
        sec += t.sec;
        return *this;
    }

    // two times match when they represent the same time during a day
    // Example: 0:0:5 must match 24:0:5
    bool operator==(const Time& t){
        return sec % (3600*24) == t.sec % (3600*24);
    }

    // write time to stream out
    void write (std::ostream& out) const {
        out << sec / 3600 % 24 << ":" 
            << sec / 60 % 60 << ":" << sec % 60;
    }
};

Pascal Schärli - PVK Informatik 1 2019

Klassen und Operator Overloading

Prüfungsaufgabe

Basisprüfung Winter 2017, 0.83 Notenpunkte

// output time on stream o
/* TODO */ operator<< (std::ostream& o, const Time t){
    // TODO

}

// return if times are not equal
bool operator!=(const Time& t1, const Time& t2){
    // TODO
}

// add time t1 and time t2
Time operator+(Time t1, const Time & t2){
    return t1 += t2;
}

// output time on stream o
std::ostream& operator<< (std::ostream& o, const Time t){
    t.write(o);
    return o;
}

// return if times are not equal
bool operator!=(const Time& t1, const Time& t2){
    // TODO
}

// add time t1 and time t2
Time operator+(Time t1, const Time & t2){
    return t1 += t2;
}

// output time on stream o
std::ostream& operator<< (std::ostream& o, const Time t){
    t.write(o);
    return o;
}

// return if times are not equal
bool operator!=(const Time& t1, const Time& t2){
    return !(t1 == t2);
}

// add time t1 and time t2
Time operator+(Time t1, const Time & t2){
    return t1 += t2;
}

Pascal Schärli - PVK Informatik 1 2019

Pointer / Iteratoren

Pointers

Pointer / Iteratoren

Pascal Schärli - PVK Informatik 1 2019

  • Der Speicher in Computern ist in Bytes (8 Bit) aufgeteilt.
  • Jedes Byte hat eine Adresse
  • Ein Pointer speichert nicht einen Wert sondern die Adresse von einem Wert.
int a = 5;
int* x = &a;
    
char c = 'd';
char* z = &c;

Pointers

Pascal Schärli - PVK Informatik 1 2019

840

841

842

843

844

845

846

847

848

849

850

851

852

853

854

855

856

857

858

859

860

861

862

863

int a = 5;
int* x = &a;

char c = 'd';
char* z = &c;

Pointer / Iteratoren

Pointers

Pascal Schärli - PVK Informatik 1 2019

840

841

842

843

844

845

846

847

848

int a = 5;
int* x = &a;

char c = 'd';
char* z = &c;

5

int a

849

850

851

852

853

854

855

856

857

858

859

860

861

862

863

Pointer / Iteratoren

Pointers

Pascal Schärli - PVK Informatik 1 2019

840

841

842

843

844

845

846

847

int a = 5;
int* x = &a;

char c = 'd';
char* z = &c;

5

int a

840

int* x

x

848

849

850

851

852

853

854

855

856

857

858

859

860

861

862

863

Pointer / Iteratoren

Pointers

Pascal Schärli - PVK Informatik 1 2019

840

841

842

843

844

845

846

847

int a = 5;
int* x = &a;

char c = 'd';
char* z = &c;

int a

840

int* x

x

char c

d

848

849

850

851

852

853

854

855

856

857

858

859

860

861

862

863

5

Pointer / Iteratoren

Pointers

Pascal Schärli - PVK Informatik 1 2019

840

841

842

843

844

845

846

847

int a = 5;
int* x = &a;

char c = 'd';
char* z = &c;

int a

int* x

x

char c

d

char* z

850

z

848

849

850

851

852

853

854

855

856

857

858

859

860

861

862

863

5

840

Pointer / Iteratoren

Pointers

Pascal Schärli - PVK Informatik 1 2019

840

841

842

843

844

845

846

847

848

int a = 5;
int* x = &a;

char c = 'd';
char* z = &c;

int a

int* x

x

char c

d

char* z

850

z

849

850

851

852

853

854

855

856

857

858

859

860

861

862

863

5

840

Pointer / Iteratoren

Operatoren

Pascal Schärli - PVK Informatik 1 2019

&

  1. Bitwise AND
     
  2. Variabel als Referenz deklarieren
     
  3. Adresse einer Variabel herausfinden

*

  1. Multiplikation
     
  2. Variabel als Pointer deklarieren
     
  3. Inhalt von einem Pointer herausfinden
z = x & y;
int& y = x;
int* ptr_a = &a;
z = x * y;
int* ptr_a = &a;
int a = *ptr_a;

Pointer / Iteratoren

New & Delete

Pascal Schärli - PVK Informatik 1 2019

  • Mit dem Keyword new kann man Pointer erstellen, welche auf Daten zeigen die niemals out of scope gehen.
  • Im Gegenzug muss man selber die Daten mit dem Keyword delete löschen falls man diese nicht mehr braucht.

Pointer / Iteratoren

New & Delete

Pascal Schärli - PVK Informatik 1 2019

Pointer / Iteratoren

#include <iostream>

int* create_value(){
    int x = 5;
    return &x;
}

int main(){
    int* ptr = create_value();

    std::cout << *ptr << "\n";
    return 0;
}
warning: address of local variable ‘x’ returned

Segmentation fault (core dumped)
#include <iostream>

int* create_value(){
    int* x = new int(5);
    return x;
}

int main(){
    int* ptr = create_value();

    std::cout << *ptr << "\n";

    delete ptr;

    return 0;
}

5

New & Delete (Arrays)

Pascal Schärli - PVK Informatik 1 2019

Pointer / Iteratoren

#include <iostream>

int* create_array(){
    int* a = new int[5];

    for(unsigned int i = 0; i < 5; i++){
        *(a + i) = i;
    }

    return a;
}

int main(){
    int* a = create_array();

    std::cout << *a << " ";
    std::cout << *(a + 1) << " ";
    std::cout << *(a + 2) << " ";
    std::cout << *(a + 3) << " ";
    std::cout << *(a + 4) << " ";

    delete[] a;

    return 0;
}

Stellt speicher für 5 Integer bereit

Pointer dereferenzieren um den dort gespiecherten Wert zu ändern

Pointer dereferenzieren um den dort gespiecherten Wert zu lesen

0 1 2 3 4

Output:

Arrays - Syntaktischer Zucker

Pascal Schärli - PVK Informatik 1 2019

Pointer / Iteratoren

*(a + 1)
a[1]
#include <iostream>

int* create_array(){
    int* a = new int[5];

    for(unsigned int i = 0; i < 5; i++){
        *(a + i) = i;
    }

    return a;
}

int main(){
    int* a = create_array();

    std::cout << *a << " ";
    std::cout << *(a + 1) << " ";
    std::cout << *(a + 2) << " ";
    std::cout << *(a + 3) << " ";
    std::cout << *(a + 4) << " ";

    delete[] a;

    return 0;
}

#include <iostream>

int* create_array(){
    int* a = new int[5];

    for(unsigned int i = 0; i < 5; i++){
        a[i] = i;
    }

    return a;
}

int main(){
    int* a = create_array();

    std::cout << a[0] << " ";
    std::cout << a[1] << " ";
    std::cout << a[2] << " ";
    std::cout << a[3] << " ";
    std::cout << a[4] << " ";

    delete[] a;

    return 0;
}

Beispiel

Pascal Schärli - PVK Informatik 1 2019

Pointer / Iteratoren

int* a = new int[5]{0, 8, 7, 2, -1};
int* ptr = a;         // pointer assignment
++ptr;                // Shift pointer to right
int my_int = *ptr;    // read target
ptr += 2;             // shift by 2 elements
*ptr = 18;            // overwrite target
int* past = a+5;
std::cout << my_int << " " << (ptr < past) << "\n";
delete[] a;

0

8

7

2

-1

int a[0]

int a[1]

int a[2]

int a[3]

int a[4]

Beispiel

Pascal Schärli - PVK Informatik 1 2019

Pointer / Iteratoren

int* a = new int[5]{0, 8, 7, 2, -1};
int* ptr = a;         // pointer assignment
++ptr;                // Shift pointer to right
int my_int = *ptr;    // read target
ptr += 2;             // shift by 2 elements
*ptr = 18;            // overwrite target
int* past = a+5;
std::cout << my_int << " " << (ptr < past) << "\n";
delete[] a;

0

8

7

2

-1

int a[0]

int a[1]

int a[2]

int a[3]

int a[4]

ptr

Beispiel

Pascal Schärli - PVK Informatik 1 2019

Pointer / Iteratoren

int* a = new int[5]{0, 8, 7, 2, -1};
int* ptr = a;         // pointer assignment
++ptr;                // Shift pointer to right
int my_int = *ptr;    // read target
ptr += 2;             // shift by 2 elements
*ptr = 18;            // overwrite target
int* past = a+5;
std::cout << my_int << " " << (ptr < past) << "\n";
delete[] a;

0

8

7

2

-1

int a[0]

int a[1]

int a[2]

int a[3]

int a[4]

ptr

Beispiel

Pascal Schärli - PVK Informatik 1 2019

Pointer / Iteratoren

int* a = new int[5]{0, 8, 7, 2, -1};
int* ptr = a;         // pointer assignment
++ptr;                // Shift pointer to right
int my_int = *ptr;    // read target
ptr += 2;             // shift by 2 elements
*ptr = 18;            // overwrite target
int* past = a+5;
std::cout << my_int << " " << (ptr < past) << "\n";
delete[] a;

0

8

7

2

-1

int a[0]

int a[1]

int a[2]

int a[3]

int a[4]

ptr

my_int = 8

Beispiel

Pascal Schärli - PVK Informatik 1 2019

Pointer / Iteratoren

int* a = new int[5]{0, 8, 7, 2, -1};
int* ptr = a;         // pointer assignment
++ptr;                // Shift pointer to right
int my_int = *ptr;    // read target
ptr += 2;             // shift by 2 elements
*ptr = 18;            // overwrite target
int* past = a+5;
std::cout << my_int << " " << (ptr < past) << "\n";
delete[] a;

0

8

7

2

-1

int a[0]

int a[1]

int a[2]

int a[3]

int a[4]

my_int = 8

ptr

Beispiel

Pascal Schärli - PVK Informatik 1 2019

Pointer / Iteratoren

int* a = new int[5]{0, 8, 7, 2, -1};
int* ptr = a;         // pointer assignment
++ptr;                // Shift pointer to right
int my_int = *ptr;    // read target
ptr += 2;             // shift by 2 elements
*ptr = 18;            // overwrite target
int* past = a+5;
std::cout << my_int << " " << (ptr < past) << "\n";
delete[] a;

0

8

7

2

-1

int a[0]

int a[1]

int a[2]

int a[3]

int a[4]

my_int = 8

ptr

18

Beispiel

Pascal Schärli - PVK Informatik 1 2019

Pointer / Iteratoren

int* a = new int[5]{0, 8, 7, 2, -1};
int* ptr = a;         // pointer assignment
++ptr;                // Shift pointer to right
int my_int = *ptr;    // read target
ptr += 2;             // shift by 2 elements
*ptr = 18;            // overwrite target
int* past = a+5;
std::cout << my_int << " " << (ptr < past) << "\n";
delete[] a;

0

8

7

2

-1

int a[0]

int a[1]

int a[2]

int a[3]

int a[4]

my_int = 8

ptr

18

past

Beispiel

Pascal Schärli - PVK Informatik 1 2019

Pointer / Iteratoren

int* a = new int[5]{0, 8, 7, 2, -1};
int* ptr = a;         // pointer assignment
++ptr;                // Shift pointer to right
int my_int = *ptr;    // read target
ptr += 2;             // shift by 2 elements
*ptr = 18;            // overwrite target
int* past = a+5;
std::cout << my_int << " " << (ptr < past) << "\n";
delete[] a;

0

8

7

2

-1

int a[0]

int a[1]

int a[2]

int a[3]

int a[4]

my_int = 8

ptr

18

past

8 1

Output:

Beispiel

Pascal Schärli - PVK Informatik 1 2019

Pointer / Iteratoren

int* a = new int[5]{0, 8, 7, 2, -1};
int* ptr = a;         // pointer assignment
++ptr;                // Shift pointer to right
int my_int = *ptr;    // read target
ptr += 2;             // shift by 2 elements
*ptr = 18;            // overwrite target
int* past = a+5;
std::cout << my_int << " " << (ptr < past) << "\n";
delete[] a;

0

8

7

18

-1

my_int = 8

ptr

past

delete Löscht die Werte noch nicht, aber es gibt sie zum Überschreiben frei.

Nullpointer

Pascal Schärli - PVK Informatik 1 2019

Pointer / Iteratoren

  • Wie kann man es schaffen, dass ein Pointer auf nichts zeigt?
  • Es gibt in C++ den sogenannten null Pointer, welcher verwendet werden kann um eine Variable effektiv auf nichts zeigen zu lassen.
#include <iostream>

int main() {

    int* p = new int(10);
    std::cout << p << std::endl;

    delete p;
    std::cout << p << std::endl;

    p = nullptr;
    std::cout << p << std::endl;

    return 0;
}



0x55beafb36e70

0x55beafb36e70
0x55beafb36e70

0x55beafb36e70
0x55beafb36e70
0

Pointer auf Objekte

Pascal Schärli - PVK Informatik 1 2019

Pointer / Iteratoren

#include <iostream>
#include <vector>

int main() {

    std::vector<int>* v = new std::vector<int>;

    (*v).push_back(3);

    std::cout << (*v).size() << std::endl;

    return 0;
}

#include <iostream>
#include <vector>

int main() {

    std::vector<int>* v = new std::vector<int>;

    v->push_back(3);

    std::cout << v->size() << std::endl;

    return 0;
}

Beide Schreibweisen sind äquivalent, aber das Rechte (->) wirkt eleganter

Container

Pascal Schärli - PVK Informatik 1 2019

Pointer / Iteratoren

  • In C++ gibt es verschiedene Arten eine Sammlung von Daten zu speichern.
  • Alle diese Arten nennt man Container
  • Ihr kennt bereits ein paar Container: Arrays, Strings, Vektoren
  • Es gibt aber noch andere Container:

Iteratoren

Pascal Schärli - PVK Informatik 1 2019

Pointer / Iteratoren

  • Pointers erlauben es uns zusammenhängende Speicherbereiche zu traversieren
  • Andere Container speichern aber je nach dem nicht alle Daten in einem zusammenhängendem Speicherbereich (zB. Linked List) und somit nicht mit normalen Pointern  traversiert werden
  • Aus diesem Grund stellen uns Containers Iteratoren zur Verfügung, welche uns diese Funktionalität ermöglichen.

Iteratoren

Pascal Schärli - PVK Informatik 1 2019

Pointer / Iteratoren

Der Datentyp von einem Iterator erhält man mit dem Format

container::iterator

Beispiele

std::vector<int>::iterator

Vektor mit Integer gefüllt

std::vector<float>::iterator

Vektor mit Floats gefüllt

std::string::iterator

String

std::set<bool>::iterator

Set mit Booleans gefüllt

Iteratoren - Beispiel

Pascal Schärli - PVK Informatik 1 2019

Pointer / Iteratoren

#include <vector>
#include <iostream>

int main(){
    std::vector<int> cont = {8,3,1,4,6,9};

    for (std::vector<int>::iterator it = cont.begin(); it != cont.end(); ++it) {
        std::cout << *it << " ";
    }
    return 0;
}

8 3 1 4 6 9

Iteratoren - Beispiel

Pascal Schärli - PVK Informatik 1 2019

Pointer / Iteratoren

#include <set>
#include <iostream>

int main(){
    std::set<int> cont = {8,3,1,4,6,9};

    for (std::set<int>::iterator it = cont.begin(); it != cont.end(); ++it) {
        std::cout << *it << " ";
    }
    return 0;
}

1 3 4 6 8 9

Der selbe Code funktioniert genau gleich bei anderen Containertypen, wie z.B. bei einem set:

Pascal Schärli - PVK Informatik 1 2019

Prüfungsaufgabe

Typen und Werte (Konstrukte)

Sommer 2018, 0.89 Notenpunkte

Pascal Schärli - PVK Informatik 1 2019

Konstrukte

Prüfungsaufgabe

Basisprüfung Sommer 2018, 0.89 Notenpunkte

int a[6] = {1, 3, 5, 7, 9, 11};
int* x = a;
int& k = *x;
x++;
std::cout << *(x+k);
5

Pascal Schärli - PVK Informatik 1 2019

Konstrukte

Prüfungsaufgabe

Basisprüfung Sommer 2018, 0.89 Notenpunkte

float p[6] = {0.5, 1.0, 1.5, 2.0, 0.5, 0.0};
float* s = &p[4];
float* r = &p[2];
std::cout << (r[2] + *(s+1));
0.5

Pascal Schärli - PVK Informatik 1 2019

Konstrukte

Prüfungsaufgabe

Basisprüfung Sommer 2018, 0.89 Notenpunkte

void my_function(int* m) {
    *m = 2;
}

int values[] = {1, 3, 5};
int* v = values;
my_function(v++);
std::cout << v[0];
3

Pascal Schärli - PVK Informatik 1 2019

Konstrukte

Prüfungsaufgabe

Basisprüfung Sommer 2018, 0.89 Notenpunkte

struct Node {
    Node* next;
    int value;
    Node (int v, Node* n) : next(n), value(v) {};
};

Node s = Node(10, nullptr);
Node t = Node(20, &s);
s.next = &t;
std::cout << (s.next->next->value);
10

Pascal Schärli - PVK Informatik 1 2019

Prüfungstipps

Generell

Prüfungstipps

Pascal Schärli - PVK Informatik 1 2019

  • Macht euch einen Lernplan für die ganze Lernphase.
  • Löst nochmals viele Serien
  • Zu wenig lernen ist schlecht, zu viel aber genau so
    -> Gönnt euch Freizeit
  • Wenn Ihr an einer Prüfung stecken bleibt, geht weiter und löst die Schwierigen aufgaben am Schluss Iterativ Stück für Stück

Informatik I (♥)

Prüfungstipps

Pascal Schärli - PVK Informatik 1 2019

  • Es gibt viele Alte Prüfungen, löst so viele wie möglich.
  • Der Prüfungsstil war bis jetzt gleich wie bei Prof. Friedrich
  • Viele Aufgaben sind jedes Jahr gleich
  • Programmiert in eurer Freizeit
  • Wenn Ihr bei einem bestimmten Thema mühe habt, schaut euch das PVK Skript von Luzian Bieri an

Viel Spass!

Pascal Schärli - PVK Informatik 1 2019