Informatik I - Übung 8

Pascal Schärli

pascscha@student.ethz.ch

12.04.2019

Was gibts heute?

Best-Of Vorlesung:
- Prefix / Infix
- EBNF
Vorbesprechung
Problem of the Week

Pascal Schärli 12.04.2019

Vorlesung

Pascal Schärli 12.04.2019

Prefix Notation

Expression1

Operator

Expression2

Expression1

Operator

Expression2

Infix (normal)

Prefix

Infix

a + b

+ a b

a * b - c

- * a b c

Pascal Schärli 12.04.2019

Prefix Notation

(a + b) * (c - d / e)

* +

* + a

* + a b

* + a b -

* + a b - c

* + a b - c /

* + a b - c / d

* + a b - c / d e

Gegen Uhrzeigersinn um den Baum Gehen und wenn man links von einer Node ist aufschreiben.

Pascal Schärli 12.04.2019

Infix vs Prefix Notation

Prefix

Infix

+ * a b * c d

a * b + c * d

+ + a * b c d

a + b * c + d

* + a b - c / d e

(a + b) * (c - d / e)

a * b

* a b

e / f

/ e f

(a * b) / (c * d)

/ * a b * c d

Pascal Schärli 12.04.2019

BNF

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

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

Pascal Schärli 12.04.2019

BNF - Beispiel

Alphabet: {A, a, _}

Regeln:

"A" kann nur als das Erste Symbol oder direkt nach "_" kommen.
"_" kann nicht als das Erste oder Letzte Symbol Kommen
"_" kommt nur einzeln Vor.

seq = term | term "_" seq
term = "A" | "A" lowerterm | lowerterm
lowerterm = "a" | "a" lowerterm

Pascal Schärli 12.04.2019

aaaa

Aaaa

Aaa_aa

Beispiel

BNF - Beispiel

seq = term | term "_" seq
term = "A" | "A" lowerterm | lowerterm
lowerterm = "a" | "a" lowerterm

term "_" seq

Kann man "Aaa_A" mit dieser BNF ausdrücken?

term "_" seq
"A" lowerterm "_" seq

term "_" seq
"A" lowerterm "_" seq
"Aa" lowerterm "_" seq

term "_" seq
"A" lowerterm "_" seq
"Aa" lowerterm "_" seq
"Aaa_" seq

term "_" seq
"A" lowerterm "_" seq
"Aa" lowerterm "_" seq
"Aaa_" seq
"Aaa_" term

term "_" seq
"A" lowerterm "_" seq
"Aa" lowerterm "_" seq
"Aaa_" seq
"Aaa_" term
"Aaa_A"

Pascal Schärli 12.04.2019

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

seq = term | term "_" seq
term = "A" | "A" lowerterm | lowerterm
lowerterm = "a" | "a" lowerterm

seq = term [ "_" seq ]
term = "A" { "a" } | "a" { "a" }

BNF

EBNF

Pascal Schärli 12.04.2019

EBNF

seq = term [ "_" seq ]
term = "A" { "a" } | "a" { "a" }

EBNF

aaaA

Aaaa

A_A

Aa_Aa

Aa__a

Pascal Schärli 12.04.2019

EBNF in C++

// PRE:  Valid stream is.
// POST: Returns true if stream contains seq and
//        extracts it, otherwise false.
bool seq(std::istream& is);

// PRE:  Valid stream is.
// POST: Returns true if stream contains term and
//        extracts it, otherwise false.
bool term(std::istream &is);

Für Jede Regel machen wir eine Funktion vom Typ bool, welche prüft ob die Regel erfüllt ist oder nicht.

seq = term [ "_" seq ]
term = "A" { "a" } | "a" { "a" }

Pascal Schärli 12.04.2019

EBNF in C++

// PRE:  Valid stream is.
// POST: Leading whitespace characters are extracted from is, and the
//       first non-whitespace character is returned (0 if there is none).
char lookahead (std::istream& is)
{
    is >> std::ws;          // skip whitespaces
    if (is.eof())
        return 0;           // end of stream
    else
       return is.peek();    // next character in is
}

Wir erstellen eine lookahead Funktion, welche schaut, was das nächste Zeichen ist, ohne dies vom String zu entfernen.

Pascal Schärli 12.04.2019

EBNF in C++

// PRE:  Valid stream is.
// POST: Reads char from stream and returns true if that char matches
//       the expected char, otherwise false is returned.
bool consume(std::istream& is, char expected)
{
    char actual;
    is >> actual;
    return actual == expected;
}

Wir erstellen eine consume Funktion, welche einen Charakter vom Stream entfernt.

Pascal Schärli 12.04.2019

EBNF in C++

// PRE:  Valid stream is.
// POST: Returns true if stream contains seq and extracts it, otherwise false.
bool seq(std::istream& is){
    // seq = term [ "_" seq ]

    bool valid = term(is); // Every seq has to start with a term
    if(!valid){            // If it does not start with a term, return false
        return false;
    }

    if(lookahead(is) == '_'){ // check if we have another seq
        consume(is, '_');      // "consume" the "_" from the instream
        return seq(is);        // Check if the rest forms a valid seq
    }
    else{               // If there is no following seq
        return true;
    }
}

Die Sequenz Funktion prüft zuerst, ob wir einen Term haben. Danach prüft es ob noch ein optionales '_' kommt, falls ja folgt eine weitere Sequenz.

Pascal Schärli 12.04.2019

EBNF in C++

// PRE:  Valid stream is.
// POST: Returns true if stream contains term and extracts it,
//       otherwise false.
bool term(std::istream &is){
    // term = "A" { "a" } | "a" { "a" }
    char first = lookahead(is);
    if(first == 'A' | first == 'a'){
        consume(is, first);
        while(lookahead(is) == 'a'){
            consume(is, 'a');
        }
        return true;
    }
    else{
        return false;
    }
}

Ein Term liest zuerst ein Buchstabe ein, dieser Kann 'A' oder 'a' sein. Danach liest dieser alle darauf folgenden 'a' ein.

Pascal Schärli 12.04.2019

EBNF in C++

bool seq(std::istream& is){
    bool valid = term(is);
    if(!valid){
        return false;
    }
    if(lookahead(is) == '_'){
        consume(is, '_');    
        return seq(is);      
    }
    else{               
        return true;
    }
}

bool term(std::istream &is){
    char first = lookahead(is);
    if(first == 'A' | first == 'a'){
        consume(is, first);
        while(lookahead(is) == 'a'){
            consume(is, 'a');
        }
        return true;
    }
    else{
        return false;
    }
}

bool seq(std::istream& is){
    bool valid = term(is);
    if(!valid){
        return false;
    }
    if(lookahead(is) == '_'){
        consume(is, '_');    
        return seq(is);      
    }
    else{               
        return true;
    }
}

bool term(std::istream &is){
    char first = lookahead(is);
    if(first == 'A' | first == 'a'){
        consume(is, first);
        while(lookahead(is) == 'a'){
            consume(is, 'a');
        }
        return true;
    }
    else{
        return false;
    }
}

bool term(std::istream &is){
    char first = lookahead(is);
    if(first == 'A' | first == 'a'){
        consume(is, first);
        while(lookahead(is) == 'a'){
            consume(is, 'a');
        }
        return true;
    }
    else{
        return false;
    }
}

bool term(std::istream &is){
    char first = lookahead(is);
    if(first == 'A' | first == 'a'){
        consume(is, first);
        while(lookahead(is) == 'a'){
            consume(is, 'a');
        }
        return true;
    }
    else{
        return false;
    }
}

bool term(std::istream &is){
    char first = lookahead(is);
    if(first == 'A' | first == 'a'){
        consume(is, first);
        while(lookahead(is) == 'a'){
            consume(is, 'a');
        }
        return true;
    }
    else{
        return false;
    }
}

bool term(std::istream &is){
    char first = lookahead(is);
    if(first == 'A' | first == 'a'){
        consume(is, first);
        while(lookahead(is) == 'a'){
            consume(is, 'a');
        }
        return true;
    }
    else{
        return false;
    }
}

bool seq(std::istream& is){
    bool valid = term(is);
    if(!valid){
        return false;
    }
    if(lookahead(is) == '_'){
        consume(is, '_');    
        return seq(is);      
    }
    else{               
        return true;
    }
}

bool seq(std::istream& is){
    bool valid = term(is);
    if(!valid){
        return false;
    }
    if(lookahead(is) == '_'){
        consume(is, '_');    
        return seq(is);      
    }
    else{               
        return true;
    }
}

bool seq(std::istream& is){
    bool valid = term(is);
    if(!valid){
        return false;
    }
    if(lookahead(is) == '_'){
        consume(is, '_');    
        return seq(is);      
    }
    else{               
        return true;
    }
}

bool seq(std::istream& is){
    bool valid = term(is);
    if(!valid){
        return false;
    }
    if(lookahead(is) == '_'){
        consume(is, '_');    
        return seq(is);      
    }
    else{               
        return true;
    }
}

bool term(std::istream &is){
    char first = lookahead(is);
    if(first == 'A' | first == 'a'){
        consume(is, first);
        while(lookahead(is) == 'a'){
            consume(is, 'a');
        }
        return true;
    }
    else{
        return false;
    }
}

bool term(std::istream &is){
    char first = lookahead(is);
    if(first == 'A' | first == 'a'){
        consume(is, first);
        while(lookahead(is) == 'a'){
            consume(is, 'a');
        }
        return true;
    }
    else{
        return false;
    }
}

bool term(std::istream &is){
    char first = lookahead(is);
    if(first == 'A' | first == 'a'){
        consume(is, first);
        while(lookahead(is) == 'a'){
            consume(is, 'a');
        }
        return true;
    }
    else{
        return false;
    }
}

bool term(std::istream &is){
    char first = lookahead(is);
    if(first == 'A' | first == 'a'){
        consume(is, first);
        while(lookahead(is) == 'a'){
            consume(is, 'a');
        }
        return true;
    }
    else{
        return false;
    }
}

bool term(std::istream &is){
    char first = lookahead(is);
    if(first == 'A' | first == 'a'){
        consume(is, first);
        while(lookahead(is) == 'a'){
            consume(is, 'a');
        }
        return true;
    }
    else{
        return false;
    }
}

bool seq(std::istream& is){
    bool valid = term(is);
    if(!valid){
        return false;
    }
    if(lookahead(is) == '_'){
        consume(is, '_');    
        return seq(is);      
    }
    else{               
        return true;
    }
}

bool seq(std::istream& is){
    bool valid = term(is);
    if(!valid){
        return false;
    }
    if(lookahead(is) == '_'){
        consume(is, '_');    
        return seq(is);      
    }
    else{               
        return true;
    }
}

bool seq(std::istream& is){
    bool valid = term(is);
    if(!valid){
        return false;
    }
    if(lookahead(is) == '_'){
        consume(is, '_');    
        return seq(is);      
    }
    else{               
        return true;
    }
}

Pascal Schärli 12.04.2019

EBNF in C++

int main()
{
    std::cout << "please enter a sequence:\n";

    std::string sequence;
    std::cin >> sequence;

    std::stringstream sequence_in(sequence);

    if (seq(sequence_in) && lookahead(sequence_in) == 0) {
        std::cout << "valid\n";
    } else {
        std::cout << "invalid\n";
    }

    return 0;
}

Die Main-Funktion liest eine Zeile ein und übergibt diese dann der Prüfenden Funktion. Danach müssen wir mit lookahead noch prüfen, ob wir alles gelesen haben

Pascal Schärli 12.04.2019

Vorbesprechung

Pascal Schärli 12.04.2019

1: Trains

train        = open | compositions
open         = loco cars
loco         = "*" | "*" loco
cars         = "-" | "-" cars
compositions = composition { composition }
composition  = "<" open loco ">"

Schreibt ein Programm, welches bestimmen kann ob ein eingelesener Input dieser EBNF entspricht.

Tipp:

Analog Zu unserem Beispiel

Pascal Schärli 12.04.2019

train        = open | compositions
open         = loco cars
loco         = "*" | "*" loco
cars         = "-" | "-" cars
compositions = composition { composition }
composition  = "<" open loco ">"

<*-*><***-----******>

<*-*>

<***-----******>

*-

***-----

******

***

-----

1: Trains

Pascal Schärli 12.04.2019

2: Money $$$

Wie Viele Münz/Noten-Kombinationen gibt es für X Rappen?

Beispiel 20 Rappen - 4 Lösungen:

Schreibt ein Rekursives Programm, welches die Anzahl Möglichen Kombinationen für beliebige X Rappen berechnet.

Pascal Schärli 12.04.2019

2: Money $$$

Anzahl Partitionen:

Es gibt 1 Weg kein Geld zu haben

Initiere Anzahl Partitionen mit 0

Wiederhole für alle denominations von 0 bis end:

Prüfe ob die denomination überhaupt Platz hat
Falls ja, Berechne die Anzahl Partitionen bei welchen alle Geldstücke höchstens so viel Wert sind wie die aktuelle denomination. (rekrursion)
Addiere den Wert von 2. zu deiner Anzahl Partitionen.

// PRE: 0 <= end <= v.size(), and
//      0 < denominations[0] < denominations[1] < .. denominators[end-1]
//      describes a (potentially empty)
//      sequence of denominations
// POST: return value is the number of ways to partition amount
//       using denominations from denominations[0], ..., denominations[end-1]
unsigned int partitions (unsigned int amount,
                         const std::vector<unsigned int> & denominations,
                         unsigned int end) {
    // Please write your code here ..
}

Denominations $\rightarrow$ Geldstücke

Die Main-Funktion ist bereits geschrieben, alles was Ihr schreiben müsst ist eine Funktion partitions im File partitions.cpp

Pascal Schärli 12.04.2019

3: Prefix To Infix

Schreibt ein Programm, welches Prefix zu Infix umwandeln kann.

* + a b - c / d e

(a + b) * (c - d / e)

Output:

Pascal Schärli 12.04.2019

Input:

3: Prefix To Infix

// PRE: valid stream is with operator (+-*/) as first char
//      precedence_operator is the precedence of the operator
//      precedence_left is precedence of left sub-expression
//      precedence_right is precedence of right sub-expression
// POST: Read operator followed by two consecutive prefix expressions e_1 and
//       e_2 from is.
//       Print e_1 operator_name e_2 in infix notation with parenthesis around
//       if precedence_operator < precedence_left
void print_operator(std::istream& is, char operator_name,
                    int precedence_operator, int precedence_left,
                    int precedence_right){
    // TODO
}

// PRE: valid stream is,
//       int precedence describes the precedence of the expression to the left
// POST: Converts prefix expression e from input stream and prints it in infix
//       notation with according parenthesis
void convert(std::istream& is, int precedence_left){
    // TODO
}

int main () {
    convert(std::cin, 0);
    return 0;
}

Pascal Schärli 12.04.2019

3: Prefix To Infix

Precedences:	Operator	Right
+	0	0
-	0	1
/	1	1
*	1	2

convert(is, 0)

print_operator(is, "-", 0, 0, 1)

convert(is, 0)

(

)

void print_operator(std::istream& is, char operator_name,
                      int precedence_operator, int precedence_left, int precedence_right)

void convert(std::istream& is, int precedence_left)

convert(is, 1)

print_operator(is, "+", 0, 1, 0)

convert(is, 1)

convert(is, 0)

Pascal Schärli 12.04.2019

precedence_left > precedence_operator

Program of the Week

Pascal Schärli 12.04.2019

Viel Spass!

Pascal Schärli 12.04.2019