Περί αναδρομής και αποτίμησης αριθμητικών παραστάσεων

Προς όφελος όσων μελετούν εισαγωγικά θέματα στη C/C++ και διαδικασιακό προγραμματισμό αυτό τον καιρό και για δικό μου reference όταν γεράσω και ξεκουτιάνω ( :P ), ας δούμε λίγο κώδικα για αποτίμηση αριθμητικών παραστάσεων.

Για λόγους ευκολίας (= τεμπελιάς) θα θεωρήσω ότι το σύστημά μας δέχεται ως αριθμούς μόνο ακέραια ψηφία από το 0 ως το 9. Η γενίκευση για πραγματικούς αριθμούς είναι τετριμμένη και αφήνεται ως άσκηση για το χρήστη ( :P ).

Αυτό που θέλουμε λοιπόν είναι καταρχήν να αναγνωρίζουμε αριθμητικές παραστάσεις του στυλ:

5*2+7/2+4-8

Τι πρέπει να προσέξουμε:

• Οι τελεστές είναι "left associative" δηλαδή το 5*3/2 π.χ., αποτιμάται ως (5*3)/2 και όχι ως 5*(2/3).
• Υπάρχει προτεραιότητα στους τελεστές, δηλαδή το '*' και το '/' έχουν μεγαλύτερη προτεραιότητα από το '+' και '-', δηλ. το 5+3*8 αποτιμάται σαν 5+(3*8) και όχι (5+3)*8.

Τα παραπάνω μας οδηγούν στην εξής στρατηγική σύμφωνα με την πρακτική του "διαίρει και βασίλευε": Ξεκίνα να διαβάζεις από τα αριστερά, όταν βλέπεις σταθερά θυμίσου την, όταν βλέπεις "*" ή "/" και έχεις στη μνήμη σου και τους 2 τελεστέους κάνε την πράξη, όταν βλέπεις "+" ή "-" και έχεις κάνει όλους τους πολ/σμους και διαιρέσεις στους τελεστέους (για σεβασμό της προτεραιότητας) κάνε την πράξη, στο τέλος η τιμή της παράστασης είναι το σύνολο των επιμέρους πράξεων.

Αν αναθέσουμε σε κάθε κομμάτι του προγράμματος μια συνάρτηση, το παραπάνω μπορεί να εκφραστεί σε κώδικα ως εξής:

 double prim(bool get)  
 {  
  if (get) cursor ++;  
  char c = expression[cursor++];  
  //Primaries can only be single digit integers  
  return c - '0';  
 }  
 double term(bool get)  
 {  
  double left = prim(get);  
  for (;;) {  
    switch (expression[cursor]) {  
    case '*':  
     left *= prim(true);  
     break;  
    case '/':  
     left /= prim(true);  
     break;  
    default:  
     return left;  
    }  
  }  
 }  
 double expr(bool get)  
 {  
  double left = term(get);  
  for (;;) {  
    switch (expression[cursor]) {  
    case '+':  
     left += term(true);  
     break;  
    case '-':  
     left -= term(true);  
     break;  
    default:  
     return left;  
    }  
  }  
 }  

Η δυαδική μεταβλητή get καθορίζει αν θέλουμε να καταναλώσουμε το επόμενο σύμβολο ή όχι. Η κλήση π.χ., του παραπάνω κώδικα θα ήταν ως expr(false). Ακόμα και στην περίπτωση της αμοιβαίας αναδρομής, η υλοποίηση αυτή στη C είναι αρκετά αποδοτική καθώς η κλήση συνάρτησης στη C είναι σχετικά "φτηνή".

Υπάρχουν σίγουρα πιο "σοφιστικέ" τρόποι να δουλέψει κανείς με operators (π.χ., Operator precedence parsing) αλλά όταν χρειάζεται να γράψει κάποιος τον κώδικα "με το χέρι" (χωρίς τη βοήθεια γραμματικών και parser generators) όσο πιο απλός και προφανής είναι ο κώδικας τόσο λιγότερο το debugging και αυτό είναι που μετρά στο τέλος της ημέρας ...

Παντελής