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
<
<=
>
>=
==
!=
&&
||
=
+=

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

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

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

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

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

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

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

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

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

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

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

/* 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

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