Fakultät in Taschenrechner implementieren

[Lieschen Müller]

Hallo,

ich bin bei der Programmierung eines Taschenrechners, der +-*/ kann (aus dem Buch von Stroustrup) und möchte nun die Fakultät implementieren. Meine Fakultätsfunktion lautet:

double fak (double val) //berechnet rekursiv die Fakultät einer Zahl
				  // rekursiv: Die Funktion ruft sich selbst auf
{
	if (val > 1) 
	{
		return fak(val-1) * val;
    }
	else
		return 1;
}

Das der double-Typ nicht gut gewählt ist, weiß ich. Ich würd's gern erst zum Funktionieren bringen, bevor ich mir darüber Gedanken mache.

Das Programm läuft nach der Grammatik:

Ausdruck:
Term
Ausdruck "+" Term
Ausdruck "-" Term
Term:
Faktor
Term "*"Faktor
Term "/" Faktor
Faktor: (-> primary() )
Zahl
Ausdruck "!"
"(" Ausdruck ")"
Zahl:
Gleitkomma

Der Taschenrechner an sich ist ziemlich lang und ich will euch nicht unbedingt mit Code zu müllen. Daher hier nur der Abschnitt, in dem ich die Fakultät unterbringen will. Vielleicht hat jemand auch mal das Buch bearbeitet und kann sich erinnern, wie es ging.

double primary()
{
    Token t = ts.get();

    switch (t.kind) {
	case '{': 
		 {    
            double d = expression();
            t = ts.get();
			if (t.kind != '}') error("'}' expected");
            return d;
        }
    case '(':    // behandle'(' Ausdruck ')'
        {    
            double d = expression();
            t = ts.get();
            if (t.kind != ')') error("')' expected");
            return d;
        }
    case '8':     // wir verwenden '8' zur Repräsentation einer Zahl
		{
			double a = t.value;
			t = ts.get();
			if(t.kind == '!')
				return fak(a); //liefere die Fakultät der Zahl zurück
			else
				return a;  // liefere den Wert der Zahl zurück
		}
    default:
        error("Faktor erwartet");
    }
}

Es wird ein Token erzeugt, das eine Kategorie und einen Zahlenwert speichert. Für Zahlen wird als Kategorie '8' gewählt (willkürlich) und der Zahlenwert abgelegt. Für die Rechenoperationen wird nur die Kategorie (+-*/!) gespeichert.

Mein Problem:
Das Token liefert mir einen Zahlenwert, ich bin also bei

case '8':

An der Stelle müsste ich doch jetzt gucken, was dahinter steht, und wenn's ein '!' ist, dann die fak() aufrufen.

Sofern ich nur die Fakultät berechnen will, funktioniert das auch, allerdings geht sonst nichts mehr. Hat jemand eine Idee?

[wxSkip]

Ich vermute, dass das, was ich gelesen habe, so ähnlich war. Ich denke aber, dass du die Fakultät nicht in dieser Funktion unterbringen kannst/solltest. Du hast doch bestimmt noch Funktionen für Plus/Minus und Mal/Geteilt. So eine müsstest du noch für die Fakultät erstellen. Könntest du mal mehr Code liefern?

[seldon]

"Ausdruck !" dürfte nicht die richtige Regel sein -- 2 + 3! bedeutet nicht (2 + 3)!. Was du eigentlich haben willst, ist "Faktor !" (damit ginge dann auch n!!). Das Problem ist natürlich, dass diese Regel linksrekursiv wäre, was in einem Recdesc-Parser stumpf nicht geht.

Da du nicht vorher entscheiden kannst, ob der Ausdruck, den du gerade parst, eine Fakultät ist oder nicht, wirst du es hinterher tun müssen. Eine Möglichkeit wäre einen LL-freundliche Zwischenregel, etwa

Fakultät := Faktor "!"*

Umzusetzen beispielsweise als

double factorial()
{
    double n = primary(); // Hier rekursiv weiter zu primary

    Token t;

    while((t = ts.get()).kind == '!') {
        n = fak(n);
    }

    ts.putback(t);

    return n;
}

...und dann überall factorial() zu benutzen, wo vorher primary() stand.

[Lieschen Müller]

Das stimmt, eigentlich will ich "Faktor !".

Deine Variante finde ich sehr gut, wäre aber von allein nie darauf gekommen.

Noch zwei Fragen: Wieso ist das linksrekursiv? Was ist ein Recdesc-Parser?

Da wxSkip danach gefragt, hier noch etwas mehr Code, falls es noch interessant ist (seldons Vorschlag ist noch nicht eingearbeitet):

class Token {
public:
    char kind;        // welche Kategorie von Token
    double value;     // für Zahlen: ein Wert  
    Token(char ch)    // erstelle ein Token aus einem char
        :kind(ch), value(0) { }    
    Token(char ch, double val)     // erstelle ein Token aus einem char und einem double
        :kind(ch), value(val) { }
};

//------------------------------------------------------------------------------

class Token_stream {
public:
   Token_stream();        // erstelle einen Token_stream, der aus cin liest 
   Token get();           // lies ein Token ein (get() ist anderswo definiert)
   void putback(Token t); // lege ein Token zurück 
private:
   bool full;    // befindet sich ein Token im Puffer?
   Token buffer; // hier legen wir ein Token ab, das mit putback() 
                 // zurückgestellt wurde
};

//------------------------------------------------------------------------------

// Der Konstruktor setzt full auf false, um anzuzeigen, dass der Puffer leer ist:
Token_stream::Token_stream()
:full(false), buffer(0)    // kein Token im Puffer
{
}

//------------------------------------------------------------------------------

// Die Memberfunktion putback() stellt ihr Argument zurück in den Puffer von Token_stream:
void Token_stream::putback(Token t)
{
    if (full) error("putback(): Zurueckstellen nicht moeglich, Puffer voll");
    buffer = t;       // kopiere t in den Puffer
    full = true;      // Puffer ist jetzt voll
}

//------------------------------------------------------------------------------

Token Token_stream::get()
{
    if (full) {       // gibt es bereits ein fertiges Token?
        // Token aus dem Puffer entfernen
        full=false;
        return buffer;
    } 

    char ch;
    cin >> ch;    // beachten Sie, dass >> Whitespace-Zeichen wie 
                  // Leerzeichen, Zeilenumbruch, Tabulatorzeichen, etc. überspringt

    switch (ch) {
    case ';':    // für "Ausgeben"
    case 'q':    // für "Verlassen"
	case '(': case ')': case '+': case '-': case '*': case '/': case '{': case '}': case '!':
        return Token(ch);        // jedes Zeichen repräsentiert sich selbst 
    case '.':
    case '0': case '1': case '2': case '3': case '4':
    case '5': case '6': case '7': case '9':
        {    
            cin.putback(ch);         // lege die Ziffer zurück in den Eingabestream
            double val;
            cin >> val;              // lies eine Gleitkommazahl 
            return Token('8',val);   // '8' repräsentiert "eine Zahl"
        }
    default:
        error("Ungueltiges Token");
    }
}

//------------------------------------------------------------------------------

double fak (double val) //berechnet rekursiv die Fakultät einer Zahl
				  // rekursiv: Die Funktion ruft sich selbst auf
{
	if (val > 1) 
	{
		return fak(val-1) * val;
    }
	else
		return 1;
}

//------------------------------------------------------------------------------

Token_stream ts;        // stellt get() und putback() zur Verfügung  

//------------------------------------------------------------------------------

double expression();    // Deklaration, damit primary() expression() aufrufen kann

//------------------------------------------------------------------------------

// behandelt Zahlen und Klammern 
double primary()
{
    Token t = ts.get();
	//Token t2 = ts.get();

    switch (t.kind) {
	case '{': 
		 {    
            double d = expression();
            t = ts.get();
			if (t.kind != '}') error("'}' expected");
            return d;
        }
    case '(':    // behandle'(' Ausdruck ')'
        {    
            double d = expression();
            t = ts.get();
            if (t.kind != ')') error("')' expected");
            return d;
        }
	case '8':     // wir verwenden '8' zur Repräsentation einer Zahl
		/*{
			double a = t.value;
			t = ts.get();
			if(t.kind == '!')
				return fak(a);
			else
				return a;  // liefere den Wert der Zahl zurück
		}*/
		return t.value;
    default:
        error("Faktor erwartet");
    }
}

//------------------------------------------------------------------------------

// behandelt *, / 
double term()
{
    double left = primary();
    Token t = ts.get();        // lies das nächste Token aus dem Token-Stream ein

    while(true) {
        switch (t.kind) {
        case '*':
            left *= primary();
            t = ts.get();
			break;
        case '/':
            {    
                double d = primary();
                if (d == 0) error("Division durch null");
                left /= d; 
                t = ts.get();
                break;
            }
		default: 
            ts.putback(t);     // stelle t wieder zurück in den Token-Stream
            return left;
        }
    }
}

//------------------------------------------------------------------------------

// behandelt + und –
double expression()
{
    double left = term();       // liest einen Token ein und wertet ihn aus
    Token t = ts.get();        // lies das nächste Token aus dem Token-Stream ein

    while(true) {    
        switch(t.kind) {
        case '+':
            left += term();    // werte Term aus und addiere
            t = ts.get();
            break;
        case '-':
            left -= term();    // werte Term aus und subtrahiere
            t = ts.get();
            break;
        default: 
            ts.putback(t);     // stelle t wieder zurück in den Token-Stream
            return left;       // keine weiteren + oder –; Antwort zurückliefern
        }
    }
}

//------------------------------------------------------------------------------

int main()
try
{
	double val = 0;
    while (cin) {
        Token t = ts.get();

        if (t.kind == 'q') break; // 'q' für "verlassen"
        if (t.kind == ';')        // ';' für "jetzt ausgeben"
            cout << "=" << val << '\n';
        else
            ts.putback(t);
        val = expression();
    }
	keep_window_open();
}
catch (exception& e) {
    cerr << "Fehler: " << e.what() << '\n'; 
    keep_window_open();
    return 1;
}
catch (...) {
    cerr << "Hoppla: unbekannte Ausnahme!\n"; 
    keep_window_open();
    return 2;
}

Die Fakultät an der Stelle einzuarbeiten, wo +-*/ bearbeitet werden, funktioniert in sofern nicht, da ja immer $2+3!= 2+(3!)$ gelten soll, solange keine Klammern bei der Eingabe gesetzt werden.

[Gast]

Wie wäre es mit einem ts.peek() aufruf, der nur schaut was kommt, das Token aber nicht entfernt? Aber ich hab nur kurz drübergeschaut.

[Lieschen Müller]

Noch eine Korrektur zu seldons Variante:

double factorial()
{
    double n = primary(); // Hier rekursiv weiter zu primary

    Token t = ts.get();

    while(t.kind == '!') 
	{
        n = fak(n);
	    t = ts.get();
    }

    ts.putback(t);

    return n;
}

Im while fehlte ein

t = ts.get();

Sonst geht's in eine Endlosschleife der Fakultätsberechnung.

Hm, peek() klingt erstmal interessant. Muss ich mich mal reinlesen.

Edit: Ah, ich glaube, es geht - zumindest im Prinzip doch so wie von seldon vorgeschlagen. Mein Kompilier hat leider gemeckert, als ich nur Token t aufgerufen habe. Hab's darum so gemacht, wie hier in meinem Beispiel.

[Gast]

Ahh, siehst du. Die Kombination aus get()+putback() ist sozusagen das peek(), das ich meinte. Hätte ich genauer lesen müssen, sorry, mea culpa.

[Lieschen Müller]

Nein, ich danke dir. Ich lern doch dazu. Ich bin auch erst später drauf gestoßen, dass es im Prinzip das gleiche ist.

[Th69]

P.S: "Recdesc Parser" meint einen Recursive Descent Parser, d.h. der LL-Parser wird implizit durch Aufruf der passenden Funktionen (expression, term, factor, primary) implementiert.
Und dies geht nur rechtsrekursiv (bei linksrekursiven Beschreibungen entsteht sonst eine Endlosrekursion).

P.S. Die Grammatik müßte eigentlich bei einem rechtsrekursiven Parser so aussehen

Ausdruck:
Term
Term "+" Ausdruck
Term "-" Ausdruck

(also Term und Ausdruck bei "+" und "-" vertauscht)

Noch ein P.S. Ich habe mal gerade im Buch "Die C++ Programmiersprache" (4. Auflage) nachgeschaut: dort ist die Grammatik auch linksrekursiv angegeben...

[Lieschen Müller]

Ehrlich gesagt ... hab ich das jetzt nicht verstanden. Werde mal drüber nachdenken.