Kann mir wer diesen Code erklären?



  • Hallo,
    in diesem Programm:

    #include <stdio.h>
    #include <stdlib.h>
    
    double fnord(double v) {
      int c = getchar();
    
      if(c >= '0' && c <= '9') {
        return fnord(v*10 + (c - '0'));
      }
      ungetc(c,stdin);
    
      return v;
    }
    
    double calc() {
      double tmp = 0.0;
    
      int c = getchar();
      if(c == '+') return tmp = calc(), tmp + calc();
      if(c == '-') return tmp = calc(), tmp - calc();
      if(c == '/') return tmp = calc(), tmp / calc();
      if(c == '*') return tmp = calc(), tmp * calc();
    
      if(c >= '0' && c <= '9') return fnord(c - '0');
    
      if(c == EOF) {
        fprintf(stderr, "Unexpected end of input\n");
        exit(-1);
      }
    
      return calc(); /* skip things we don't understand */
    }
    
    /* Aufruf mittels:
     *  prog.exe < input.txt
     *
     * Beispiele
     *  "* 3 + 5 9" = 42
     *  "+ - * / 1 2 3 4 5" = 2.5
     */
    int main(void) {
      printf("Result = %f\n", calc());
    
      return 0;
    }
    

    In diesem Abschnitt:

    if(c == '+') return tmp = calc(), tmp + calc();
      if(c == '-') return tmp = calc(), tmp - calc();
      if(c == '/') return tmp = calc(), tmp / calc();
      if(c == '*') return tmp = calc(), tmp * calc();
    

    Verstech ich jeweils den letzten Teil nicht:

    return tmp = calc(), tmp + calc();
    

    In tmp speicher ich also den wert von calc(), allerdings hat ja calc() nicht wirklich irgendeinen sinnvollen Wert. Na ja auf jeden Fall ruf ich ja dann nochmal die Funktion calc() auf. Aber was soll denn

    ,tmp - calc()
    

    bedeuten? Also wie ist dieses "," denn zu verstehen? Und wenn ich davor tmp den Wert von calc() zugewiesen habe, dürfte tmp-calc() ja 0 ergeben, bzw. temp+calc() = 2*calc(), etc..

    Kann mir da wer weiterhelfen? In möglichst "einfach" wenn das geht, weil ich noch ein kompletter Anfänger bin.

    mfg



  • suchwort kommaoperator



  • Ok es werden dann also in dem return beide Anweisungen ausgeführt. Also einmal wird tmp den Wert von calc() gegeben (was vermutlich irgendein zufälliger Wert ist?), und es dann wird z.b. tmp+calc() = 2x calc() gerechnet (wenn ein + eingelesen wird), und damit ist der Funktionsaufruf beendet und es wird noch mal calc() aufgerufen. Aber ich versteh das irgendwie immer noch nicht..

    Das Programm soll ja sowas wie +* 3 5 10 ausrechnen, aber ich versteh da die calc() Funktion nicht so recht..



  • kenplan schrieb:

    Ok es werden dann also in dem return beide Anweisungen ausgeführt. Also einmal wird tmp den Wert von calc() gegeben (was vermutlich irgendein zufälliger Wert ist?), und es dann wird z.b. tmp+calc() = 2x calc() gerechnet, und damit ist der Funktionsaufruf beendet und es wird noch mal calc() aufgerufen. Aber ich versteh das irgendwie immer noch nicht..

    Das Programm soll ja sowas wie +* 3 5 10 ausrechnen, aber ich versteh da die calc() Funktion nicht so recht..

    Kann ich verstehen, zuviel Rekursion ist nicht gut für die Übersicht.
    Gibt es zu dem Code keine Beschreibung, oder ist genau das deine Aufgabe?



  • Na ja die Aufgabe ist, den Code zu erweitern damit er auch noch mit Variablen umgehen kann. Also das er sowas rechnen kann:
    „=a + 3 5 * a a“ (Ergebnis 64)
    Aber davor muss ich ja erstmal den Code so wie er jetzt ist verstehen. Erklärungen hab ich zu dem Code nicht. fnord versteh ich ja noch soweit, aber calc() nicht.



  • Ich gehs mal schrittweise durch:
    1. Eingabe von '+' -> calc wird erneut aufgerufen
    2. Eingabe von '-' -> calc wird erneut aufgerufen
    3. Eingabe von '' -> calc wird erneut aufgerufen
    4. Eingabe von '/' -> calc wird erneut aufgerufen
    5. Eingabe von '1' -> fnord wird mit c - '0' also 1 aufgerufen
    6. In fnord Eingabe von 2 -> fnord wird erneut mit 10 + 2 = 12 aufgerufen
    7. In fnord Eingabe von 3 -> fnord wird erneut mit 120 + 3 = 123 aufgerufen
    8. In fnord Eingabe von 4 -> fnord wird erneut mit 1230 + 4 = 1234 aufgerufen
    9. In fnord Eingabe von 5 -> fnord wird erneut mit 12340 + 5 = 12345 aufgerufen
    10. fnord gibt 12345 zurück und schreibt was in den Eingabestrom.
    11. calc gibt auch 12345 zurück was tmp im '/' Zweig zugewiesen wird.
    12. calc wird aufgerufen, getchar() nimmt den Wert den fnord in den Eingabestrom geschrieben hat, ruft fnord auf, dieses schreibet wieder einen Wert in den Eingabe Strom und gibt einen Wert zurück durch den tmp dividiert wird.
    13. Das geht dann in den '
    ', '-' und '+' Zweigen so weiter bis letztendlich 2.5 rauskommt.
    Was ist denn der Zweck des Codes? Sieht nach sehr viel Aufwand für etwas einfaches aus.



  • Also ab Zeile 11 versteh ich nicht so ganz. Wieso gibt denn calc 12345 zurück? Also sobald eine zahl eingegeben wird, wird in calc() fnord ausgerufen und die einzelnen ziffern der zahl wird dann von fnord als double zurückgegeben und das nächste zeichen das keine zahl ist wird in den eingabestrom zurückgestellt (also entweder ein leerzeichen oder EOF). Aber wenns nach mir ginge wäre das Programm dann schon zu ende.. Denn alle aufrufe von calc() wurden doch zuende geführt(weil ja übetrall return steht) und fnord() wurde auch zuende geführt. Wie kommt denn jetzt auf einmal wieder calc() ins Spiel nachdem fnord fertig ist?



  • double calc() {
      double tmp = 0.0;
    
      int c = getchar();
      if(c == '+') return tmp = calc(), tmp + calc();
      if(c == '-') return tmp = calc(), tmp - calc();
      if(c == '/') return tmp = calc(), tmp / calc();
      if(c == '*') return tmp = calc(), tmp * calc();
    
      if(c >= '0' && c <= '9') return fnord(c - '0');
    
      if(c == EOF) {
        fprintf(stderr, "Unexpected end of input\n");
        exit(-1);
      }
    
      return calc(); /* skip things we don't understand */
    }
    

    Wir sind bei Schritt 10: fnord gibt 12345 zurück.
    Damit ist das Programm noch nicht beendet weil: hier in Zeile 10 steht:

    if(c >= '0' && c <= '9') return fnord(c - '0');
    

    calc gibt also den finalen return von fnord zurück, welcher dann in tmp gespeichert wird.
    Damit ist das Programm aber immer noch nicht beendet, es wird jetzt der Ausdruck hinter dem Komma ausgewertet, also: tmp / calc();
    Dieser Ausdruck wird wiederum zurückgegeben usw.
    Bis die Funktion schließlich den eigentlichen Wert durch das return in dem '+' Zweig zurückgibt, der mit printf ausgegeben wird.

    Deswegen meinte ich auch viel Aufwand (Unmengen an Funktionsaufrufen).



  • Was ist denn der Zweck des Codes? Sieht nach sehr viel Aufwand für etwas einfaches aus.

    Wenn du Englisch verstehst, dann guck dir das mal an: https://www.youtube.com/watch?v=7ha78yWRDlE da ist eine Erklärung warum man postfix oder prefix notations verwenden kann.

    Selbst wenn du denkst, dass dein Englisch schlecht ist, guck dir dennoch das Video an, Professor David Brailsford spricht langsam und deutlich und erklärt ziemlich gut.

    Die "Reverse Polish Notation" aka postfix notation ist nur eine andere Schreibweise für arithmetische Aussagen.

    Z.B: 3 + 5

    unser Gehirm liest 3 und speichert es irgendwo, dann liest es + und weiß, dass es eine weitere Zahl braucht und dann lies es 5. Das Gehirn hat sich gemerkt, dass es noch eine Operation + gelesen hatte und somit holt sich aus dem Gedächtnis die 3 und dann addiert die 5 dazu und die 8 ist die Lösung/Ausgabe von "3 + 5".

    Unser Gehirn ist so gut mit dieser Erkennung von Mustern, dass wir keine Probleme haben auch komplizierte Aussagen auszuwerten wie "3 * 4 + 3 + 5 * 9 / 3 ....".

    Desweiteren gibt es in der Arithmetik ein Operatoren Präferenz, "Punkt vor Striche", * und / werden stets vor + und - gerechnet. Für unsere Gehirne nicht schwierig aber für Computer, für die nicht über den gesamten Überblick verfügt wie wir, ist es schwerer.

    Man kann die Operatoren aber auch als reine mathematische Funktionen
    f:R2Rf: \mathbb{R}^2 \longrightarrow \mathbb{R}
    vorstellen, so dass 3 + 5 auch so schreiben können: +(3, 5). Oder 5 * 7 + 3 als +(*(5, 7)) , etc.

    Gehen wir einen Schritt weiter und entfernen wir die lästigen Klammern, so dass wir dann bekommen

    3 + 5 äquivalent zu + 3 5

    3 + 5 * 7 äquivalent zu + 3 * 5 7

    und das nennt sich eine die Prefix Notation. Die "normale" Schreibweise nennt man Infix Notation (weil die Operatoren zwischen den Operanden gehen) und es gibt die Postfix Notation, wo die Operatoren nach den Operanden kommen:

    infix:   3 + 5 * 7
    prefix:  + 3 * 5 7
    postfix: 5 7 * 3 +
    

    Gerade wenn man komplexere Aussagen hat wie "3 * ( 4 + 5 )" sind prefix/postfix in Vorteil, weil sie kürzer geschrieben werden können und die Punkt vor Strich Regel an sich verschwindet.

    infix:   3 * ( 4 + 5 )
    prefix:  * 3 + 4 5
    postfix: 4 5 + 3 *
    

    Mit postfix und prefix kannst du die Aussagen mit Hilfe einer einfachen Datenstruktur (eine Stack) lösen. In Falle deines Programs wird die Prefix Notation ausgewertet:

    calculate_prefix(input, stack)
      if input is empty
        return
    
      c = next_token(input)
      input = input - c  # entferne das gelesene Token von input
    
      if c is a number:
        stack.push(c)
        return
    
      # c is an operand
      # wir brauchen 2 operatoren
      # hier ist die Rekursion
    
      calculate_prefix(input, stack)
      calculate_prefix(input, stack)
    
      # von Rest des Inputs und liefert das Ergebnis zurück
      a1 = stack.pop()
      a2 = stack.pop()
    
      stack.push( c(a1, a2) )
    
      return
    
    Die Lösung bekommt man mit einem pop des Stacks
    
    Beispiel:
    prefix:  * 3 + 5 9
    
    # vars input & stack called by reference
    
    stack = []
    calculate_prefix("* 3 + 5 9", stack) ->
      - c = next_token("* 3 + 5 9")  == *
    
      - input = input - "*"  == "3 + 5 9"
    
      - c ist ein Operator
    
        - calculate_prefix(input, stack) -> (input is "3 + 5 9", stack = [])
    
            - c1 = next_token("3 + 5 9") == 3
    
            - input = input - c1  == "+ 5 9"
    
            - c1 ist eine Zahl
    
            - stack.push(c1) --> stack = [3]
    
            - return
    
        - calculate_prefix(input, stack) -> (input is "+ 5 9", stack = [3])
    
            - c2 = next_token("+ 5 9") == +
    
            - input = input - c2 == "5 9"
    
            - c2 ist Operator
    
            - calculate_prefix(input, stack) -> (input is "5 9", stack = [3])
    
                - c3 = next_token("+ 5 9") == 5
    
                - input = input - c3 == "9"
    
                - c3 ist eine Zahl
    
                - stack.push(c3) --> stack = [3, 5]
    
                - return
    
           - calculate_prefix(input, stack) -> (input is "9", stack = [3 5])
    
             - c3 = next_token("9") == 9
    
             - input = input - c3 == ""
    
             - c3 ist eine Zahl
    
             - stack.push(c3) --> stack = [3, 5, 9]
    
             - return
    
          - a1 = stack.pop()  == 9  # stack = [3, 5]
    
          - a2 = stack.pop()  == 5  # stack = [3]
    
          - stack.push( c2(5, 9) )  # c2 = +, stack = [3, 14]
    
          - return
    
        - calculate_prefix(input, stack) -> (input is "", stack = [3, 14])
    
            - input is empty
    
            - return
    
        - a1 = stack.pop()  == 14  # stack = [3]
    
        - a2 = stack.pop()  == 3   # stack = []
    
        - stack.push( c(14, 3) )  # c = *, stack = [42]
    
        - return
    
    result = stack.pop() --> result = 42
    

    calc() führt genau das, nur dass der Stack nicht explizit programmiert wurde, da durch die Verwendung der Rekursion, der C compiler generiert ein Stack für sich und der Code nutzt das aus. Je nachdem wie die Variable tmp verwenet wird, ist es ein stack.push() oder ein stack.pop .

    calc() liest ein Zeichen und schaut ob es eine Zahl oder ein Operand ist.

    Ist das gelesene Zeichen eine Zahl, dann liefert es den Wert fnord(c - '0') zurück. fnord liest weiter von der Eingabe bis die Zahl zu ende ist und wandelt ein String wie "934" in 9 * 10^2 + 3 * 10^1 + 4 = 934.

    Ist das gelesene Zeichen ein Operator (+-*/), so ruft es calc() zwei Mal auf und bekommt die Operatoranden und mit dem Operator berechnet es die Lösung.

    edit: camper hat auf einen Fehler von mir hingewiesen

    ~~
    Der Code könnte auch "verständlicher" geschrieben werden:

    [cpp]
    double operator(char op, double a1, double a2)
    {
    if(op == '+') return a1 + a2;
    if(op == '-') return a1 - a2;
    if(op == '*') return a1 * a2;
    if(op == '/') return a1 / a2;
    }

    double calc() {
    double tmp = 0.0;

    int c = getchar();

    if(c == '+' || c == '-' || c == '*' || c == '/')
    return operator(c, calc(), calc());

    ...
    [/cpp]
    ~~

    # siehe https://en.wikipedia.org/wiki/Polish_notation



  • Bitmapper schrieb:

    double calc() {
      double tmp = 0.0;
     
      int c = getchar();
      if(c == '+') return tmp = calc(), tmp + calc();
      if(c == '-') return tmp = calc(), tmp - calc();
      if(c == '/') return tmp = calc(), tmp / calc();
      if(c == '*') return tmp = calc(), tmp * calc();
     
      if(c >= '0' && c <= '9') return fnord(c - '0');
     
      if(c == EOF) {
        fprintf(stderr, "Unexpected end of input\n");
        exit(-1);
      }
     
      return calc(); /* skip things we don't understand */
    }
    

    Wir sind bei Schritt 10: fnord gibt 12345 zurück.
    Damit ist das Programm noch nicht beendet weil: hier in Zeile 10 steht:

    if(c >= '0' && c <= '9') return fnord(c - '0');
    

    calc gibt also den finalen return von fnord zurück, welcher dann in tmp gespeichert wird.
    Damit ist das Programm aber immer noch nicht beendet, es wird jetzt der Ausdruck hinter dem Komma ausgewertet, also: tmp / calc();
    Dieser Ausdruck wird wiederum zurückgegeben usw.
    Bis die Funktion schließlich den eigentlichen Wert durch das return in dem '+' Zweig zurückgibt, der mit printf ausgegeben wird.

    Deswegen meinte ich auch viel Aufwand (Unmengen an Funktionsaufrufen).

    Wieso wird denn der finale return von fnord in tmp gespeichert? Klar calc() hat den Wert von fnord, aber wie kommt man denn dann aufeinmal wieder zu zeile 25? Also was ich jetzt glaube ich weiß ist, dass bei z.b.

    if(c == '+') return tmp = calc(), tmp + calc();
    

    Erst das return tmp=calc() gemacht wird, und wenn das abgearbeitet ist, macht das programm nochmal ein return tmp+calc(), wo calc ja im Idealfall wohl den wert von fnord hat (also die zahl) und tmp irgendwas anderes.

    Ich checks einfach nicht. Rekursion hasse ich einfach wie die pest. ich hab bis jetzt bei jeder beschi*** rekursions-aufgabe extrem lang gebraucht.. Da platzt mir echt die schädeldecke. Ist ja kein wunder das jeder das info studium abbricht bei sowas. Das war ursprünglich sogar eine aufgabe, also das wir rekursiv einen rechner programmieren müssen der mit präfix notation umgehen kann, allerdings haben wir dann zum glück die musterlösung bekommen. auf sowas wär ich in 10 jahren nicht gekommen.


  • Mod

    supertux schrieb:

    Der Code könnte auch "verständlicher" geschrieben werden:

    return operator(c, calc(), calc());
    

    Dabei übersiehst du, warum der ursprünglich Code überhaupt den Umweg über tmp und Kommaoperator geht und nicht einfach da steht

    if(c == '+') return calc() + calc(); // usw.
    

    weil dafür gesorgt werden muss, dass die calc-Aufrufe in einer bestimmten Reihenfolge ausgeführt werden (jedenfalls für die nicht kommutativen Operatorn).



  • Ok, ich versuch's nochmal
    Eingabe: + - * / 1 2 3 4 5.
    calc wird aufgerufen -> getchar nimmt '+' -> im '+' Zweig wird calc erneut aufgerufen
    -> getchar nimmt '-' -> im '-' Zweig wird calc erneut aufgerufen -> getchar nimmt '' -> im '' Zweig wird calc erneut aufgerufen
    -> getchar nimmt '/' -> im '/' Zweig wird calc erneut aufgerufen -> getchar nimmt '1' -> eine Zahl, also wird fnord aufgerufen.
    -> Dieses nimmt alle restlichen Zahlen und gibt 12345 zurück welches in diesem tmp:

    if(c == '/') return tmp = calc(), tmp / calc();
    

    gespeichert wird.
    Danach wird der Ausdruck auf der anderen Seite des Kommas ausgewertet welcher als return von calc im tmp von:

    if(c == '*') return tmp = calc(), tmp * calc();
    

    gespeichert wird. Das wird dann im '-' und '+' Zweig wiederholt, bis das hier:
    if(c == '+') return tmp = calc(), tmp + calc();
    im printf ausgegeben wird.



  • Bitmapper schrieb:

    Ok, ich versuch's nochmal
    Eingabe: + - * / 1 2 3 4 5.
    calc wird aufgerufen -> getchar nimmt '+' -> im '+' Zweig wird calc erneut aufgerufen
    -> getchar nimmt '-' -> im '-' Zweig wird calc erneut aufgerufen -> getchar nimmt '' -> im '' Zweig wird calc erneut aufgerufen
    -> getchar nimmt '/' -> im '/' Zweig wird calc erneut aufgerufen -> getchar nimmt '1' -> eine Zahl, also wird fnord aufgerufen.
    -> Dieses nimmt alle restlichen Zahlen und gibt 12345 zurück welches in diesem tmp:

    Nein, fnord gibt nur 1 zurück. Wäre die Eingabe "+ - * / 12345", dann würde es stimmen. Aber das ist keine arithmetische Aussage.

    Nur wenn fnord

    c >= '0' && c <= '9'
    

    als Wahr auswertet (also wenn das nächste gelesene Zeichen eine ein Zeichen ist, das eine Zahl darstellt) wird fnord erneut rekursiv aufgerufen. Weil aber bei Eingabe "1 2 3 4 5" zwischen 1 und 2 ein Leerzeichen ist, ist c >= '0' && c <= '9' false, wird zurück ins Eingabestream geschrieben und v (in diesem Fall '1' - '0' == 1) zurückgegeben.

    Das wird bei

    if(c == '/') return tmp = calc(), tmp / calc();
    

    bei tmp = calc() in tmp gespeicher, also gilt tmp == 1. Danach wird wieder calc aufgerufen und das gelesene Zeichen ist nun ' ' (Leerzeichen). Weil es keine Regel für Leerzeichen gibt, wird Zeile 31 ausgeführt (/* skip things we don't understand */) und calc wieder aufgerufen. Dieses Mal wird '2' aufgerufen und fnord(2) zurückgegeben. Weil bei "2 3 4 5" wieder ein Leerzeichen zwischen 2 und 3 gibt, gibt fnord 2 zurück und somit calc . Somit wird tmp / calc(); als (double) 1 / (double) 2 (0.5) ausgewertet und zurückgegeben.

    Wegen der Rekursion wird diese 0.5 bei

    if(c == '*') return tmp = calc(), tmp * calc();
    

    in tmp gespeichert und calc nochmal aufgeführt, wieder ein Leerzeichen gelesen, wieder /* skip things we don't understand */, wieder 3 zurückgeben und bei tmp * calc() ausgewertet zu 0.5 * 3 (1.5), usw...

    du hast dann den Azsdruck 1.0/2.0 * 3.0 - 4 + 5.

    Schau dir mein Beispiel auf der ersten Seite, da habe ich die Rekursion komplet aufgeschrieben, es hat mir fast eine 1 1/2 Stunden Zeit gekostet, das sollte dir dann calc klar vorkommen.



  • Mit den Leerzeichen macht es auch Sinn, danke supertux.



  • [quote="supertux"]

    Bitmapper schrieb:

    Schau dir mein Beispiel auf der ersten Seite, da habe ich die Rekursion komplet aufgeschrieben, es hat mir fast eine 1 1/2 Stunden Zeit gekostet, das sollte dir dann calc klar vorkommen.

    Ok also ich hab mir den angeschaut. Im grunde genommen wird da ja jede eingelese zahl auf den stack draufgelegt, und wenn keine eingaben mehr folgen wird der zweite teil von z.b.
    if(c == '+') return tmp = calc(), tmp + calc();
    ausgeführt mit den jeweils letzten zwei auf den stack gelegten zahlen. Und dann halt immer so weiter..

    Na ja also ich könnte mir vorstellen das es so funktioniert, aber anhand von dem programm rall ich das nicht. Wenn ich mit nem debugger der reihe nach die schritte durchgehe, macht der auch glaube nicht das was du geschrieben hast.

    Z.b. ganz am anfang

    stack = [] 
    calculate_prefix("* 3 + 5 9", stack) -> 
      - c = next_token("* 3 + 5 9")  == * 
    
      - input = input - "*"  == "3 + 5 9" 
    
      - c ist ein Operator 
    
        - calculate_prefix(input, stack) -> (input is "3 + 5 9", stack = []) 
    
            - c1 = next_token("3 + 5 9") == 3 
    
            - input = input - c1  == "+ 5 9" 
    
            - c1 ist eine Zahl 
    
            - stack.push(c1) --> stack = [3] 
    
            - return
    

    Da wird ja erst das * eingelesen, dann neuer aufruf von calc() und dann wird im neuen aufruf von calc nochmal ein zeichen eingelesen (im falle von dem beispiel "* 3 + 5 9" müsste es eigentlich ein leerzeichen sein, so wie du es geschrieben hast wird direkt die 3 eingelesen, aber kommt ja aufs gleiche raus).

    Aber wenn ich das mitn debugger durchgehe (codeblocks mit gcc compiler) wird im zweiten aufruf von calculate nicht das nächste zeichen eingelesen, sondern der wandert durch die funktion calculate bis zum ende zu return calc(), dann wird zum dritten mal calc() aufgerufen und erst jetzt wird das nächste zeichen eingelesen... Es würde ja sinn machen wenn der debugger das getchar ignoriert, wenn davor in fnord das ungetc stattgefunden hat, hat es aber nicht.

    Also ich kapiers nicht.

    Bitmapper schrieb:

    Ok, ich versuch's nochmal
    Eingabe: + - * / 1 2 3 4 5.
    calc wird aufgerufen -> getchar nimmt '+' -> im '+' Zweig wird calc erneut aufgerufen
    -> getchar nimmt '-' -> im '-' Zweig wird calc erneut aufgerufen -> getchar nimmt '' -> im '' Zweig wird calc erneut aufgerufen
    -> getchar nimmt '/' -> im '/' Zweig wird calc erneut aufgerufen -> getchar nimmt '1' -> eine Zahl, also wird fnord aufgerufen.
    -> Dieses nimmt alle restlichen Zahlen und gibt 12345 zurück welches in diesem tmp:

    if(c == '/') return tmp = calc(), tmp / calc();
    

    gespeichert wird.
    Danach wird der Ausdruck auf der anderen Seite des Kommas ausgewertet welcher als return von calc im tmp von:

    if(c == '*') return tmp = calc(), tmp * calc();
    

    gespeichert wird. Das wird dann im '-' und '+' Zweig wiederholt, bis das hier:
    if(c == '+') return tmp = calc(), tmp + calc();
    im printf ausgegeben wird.

    Das wär ideal, aber für mich machts irgendwie kein sinn. Wenns nach mir geht steht in tmp irgendein zufälliger wert, weil im ersten aufruf von calc(), tmp den wert von calc() gegeben wird.

    na ja wird wohl nicht so wichtig sein schätze ich.. Iterativ und dafür doppelt so lang wär mir lieber glaub ich..



  • Mein Beispiel Code ist kein C code sondern Pseudo Code.

    (im falle von dem beispiel "* 3 + 5 9" müsste es eigentlich ein leerzeichen sein, so wie du es geschrieben hast wird direkt die 3 eingelesen, aber kommt ja aufs gleiche raus).

    Ich habe die magische Funktion next_token , deren Implementierung eigentlich egal ist. Ob input = " 3 5" aussieht oder input = "3 5" aussieht, soll es egal sein, next_token liefert 3, beim nächsten Aufruf 5, usw. Wie gesagt, es ist Pseudocode und solche Details wie "es gibt Leerzeichen, die der Parser extra behandeln muss" zu verstecken.

    Mein Code ist ein genereller Versuch ein Prefix Notation Auswerter zu definieren, ohne auf solche Details, wie oben beschrieben, näher einzugehen. Wenn du den Wiki-Artikel gelesen hättest, hättest du bemerkt, dass viele Implementierungen der Prefix Notation den Input von hinten nach vorne lesen, denn ist es einfacher zuerst die Operanden auf den Stack zu pushen als zuerst den Operator zu lesen und zu wissen, dass ich erst 2 Operanden irgendwie auf dem Stack gepusht werden müssen.

    Weil dein C Code aber genau das tut, habe ich den Standardalgo umgebaut, damit man von vorne liest und nicht von hinten liest (wie beim Wiki-Artikel).

    Mein Fokus im Ganzen war dir ein Beispiel zu geben, wie Rekursion funktioniert und wie Levels der Rekursion aussehen. Von denen Beiträgen merke ich, dass du damit Probleme hast, dir die Rekursion im Kopf vorzustellen.

    Weil ich näher dran am Algorithmus mit einem Stack bleiben wollte, habe ich einen expliziten Stack verwendet. Der von dir geposteten C Code macht das implizit. Gemeint ist folgendes: der Compiler baut einen Stack während des Aufrufs einer Funktion, insbesondere bei Rekusrsion. Der von dir geposteten C Code nutzt das aus, ohne explizit auf diesen Stack zuzugreifen (was mit ANSI C an sich nicht möglich ist) und läßt dem Compiler das pushen und popen erledigen. Das geschieht automatisch beim Aufruf von calc .

    Aber wenn ich das mitn debugger durchgehe (codeblocks mit gcc compiler) wird im zweiten aufruf von calculate nicht das nächste zeichen eingelesen, sondern der wandert durch die funktion calculate bis zum ende zu return calc(), dann wird zum dritten mal calc() aufgerufen und erst jetzt wird das nächste zeichen eingelesen... Es würde ja sinn machen wenn der debugger das getchar ignoriert, wenn davor in fnord das ungetc stattgefunden hat, hat es aber nicht.

    ich glaube, die musst mit dem Debugger nochmal durch, denn es macht keinen Sinn, was du da sagst. Oder baut printfs ein und untersuche die Ausgabe.

    Im Grund ist calc nicht anders als eine Funktion, die durch den Eingabestrom geht und die einzelne Tokens zurückgibt. Sind diese Zahlen, so werden Zahlen zurückgegeben. Ist es ein Operand, muss es sich nochmal 2 Mal aufrufen, weil bei Operatoren 2 Operanden braucht.



  • Anbei der gleiche Code aber mit printfs, um die Rekursion besser verstehen zu können:

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    char *get_padding(char *buffer, int rl, int tree)
    {
    	int i;
    	buffer[0] = 0;
    	if(tree)
    	{
    		strcat(buffer, "+-");
    		for(i = 0; i < rl; ++i)
    			strcat(buffer, "-");
    	} else {
    		strcat(buffer, "| ");
    		for(i = 0; i < rl; ++i)
    			strcat(buffer, " ");
    	}
    	return buffer;
    }
    
    // rl == recursion level, helps to debug it
    double fnord(double v, int rl) {
    	char padding[1024*10]; // should be enough
    	char *tmp_padding = get_padding(padding, 2*rl+2, 0);
    
    	int c = getchar();
    
    	printf("%s fnord() initial value: %lf\n", tmp_padding, v);
    
    	if(c >= '0' && c <= '9') {
    		double res;
    		printf("%s fnord() reads '%c'. Get next digits\n", tmp_padding, c);
    		res = fnord(v*10 + (c - '0'), rl+1);
    		printf("%s fnord() got and returns '%lf'\n", tmp_padding, res);
    		return res;
    	}
    
    	printf("%s fnord() reads '%c', not a digit.\n", tmp_padding, c);
    	printf("%s fnord() puts it back in stdin and returns the inital value %lf\n", tmp_padding, v);
    	ungetc(c, stdin);
    
    	return v;
    }
    
    // rl == recursion level, helps to debug it
    double calc(int rl) {
    	char padding[1024*10]; // should be enough
    
    	double tmp = 0.0;
    	double operand;
    	double res;
    
    	printf("%s calc() recursion level: %d\n", get_padding(padding, 2*rl, 1), rl);
    
    	int c = getchar();
    
    	char *tmp_padding = get_padding(padding, 2*rl+2, 0);
    
    	if(c == '+' || c == '-' || c == '/' || c == '*')
    	{
    
    		printf("%s operator %c: requires 2 operand, calc() will be executed twice\n", tmp_padding, c);
    
    		tmp = calc(rl+1);
    		printf("%s first  operand: tmp = %lf  --> stack.pop()\n", tmp_padding, tmp);
    
    		operand = calc(rl+1);
    		printf("%s second operand: tmp = %lf  --> stack.pop()\n", tmp_padding, operand);
    
    		if(c == '+') res = tmp + operand;
    		if(c == '-') res = tmp - operand;
    		if(c == '/') res = tmp / operand;
    		if(c == '*') res = tmp * operand;
    
    		printf("%s intermediate result %lf %c %lf = %lf\n", tmp_padding, tmp, c, operand, res);
    		printf("%s calc returns %lf  --> stack.push(%lf)\n\n", tmp_padding, res, res);
    		return res;
    	}
    
    	if(c >= '0' && c <= '9')
    	{
    		printf("%s number %c: fnord will get next operand\n", tmp_padding, c);
    		res = fnord(c - '0', rl+1);
    		printf("%s fnord returns operand %lf  --> stack.push(%lf)\n", tmp_padding, res, res);
    		return res;
    
    	}
    
    	if(c == EOF) {
    		fprintf(stderr, "Unexpected end of input\n");
    		exit(-1);
    	}
    
    	printf("%s c='%c' (%d): no rule for this character, ignore it and resume\n", tmp_padding, c, c);
    	return calc(rl+1); /* skip things we don't understand */
    }
    
    /* Aufruf mittels:
      *  prog.exe < input.txt
      *
      * Beispiele
      *  "* 3 + 5 9" = 42
      *  "+ - * / 1 2 3 4 5" = 2.5
      */
    int main(void) {
    
    	printf("Result = %f\n", calc(0));
    	return 0;
    }
    

    Die Ausgabe ist recht lang, also mach dein Terminal sehr lang und am besten eine kleine Schrift, damit die Zeilen nicht umgebrochen werden.

    Fange mit kleinen Beispielen an wie "+ 10 26" und dann komplexre wie "+ 3 * 5 125"

    Beispiel

    $ echo "+ 10 20" | ./prefix_calculator
    +- calc() recursion level: 0
    |    operator +: requires 2 operand, calc() will be executed twice
    +--- calc() recursion level: 1
    |      c=' ' (32): no rule for this character, ignore it and resume
    +----- calc() recursion level: 2
    |        number 1: fnord will get next operand
    |          fnord() initial value: 1.000000
    |          fnord() reads '0'. Get next digits
    |            fnord() initial value: 10.000000
    |            fnord() reads ' ', not a digit.
    |            fnord() puts it back in stdin and returns the inital value 10.000000
    |          fnord() got and returns '10.000000'
    |        fnord returns operand 10.000000  --> stack.push(10.000000)
    |    first  operand: tmp = 10.000000  --> stack.pop()
    +--- calc() recursion level: 1
    |      c=' ' (32): no rule for this character, ignore it and resume
    +----- calc() recursion level: 2
    |        number 2: fnord will get next operand
    |          fnord() initial value: 2.000000
    |          fnord() reads '0'. Get next digits
    |            fnord() initial value: 20.000000
    |            fnord() reads '
    ', not a digit.
    |            fnord() puts it back in stdin and returns the inital value 20.000000
    |          fnord() got and returns '20.000000'
    |        fnord returns operand 20.000000  --> stack.push(20.000000)
    |    second operand: tmp = 20.000000  --> stack.pop()
    |    intermediate result 10.000000 + 20.000000 = 30.000000
    |    calc returns 30.000000  --> stack.push(30.000000)
    
    Result = 30.000000
    

Anmelden zum Antworten