Newsgroup: it.comp.lang.c
Titolo: Gestire espressioni con parentesi

Devi gestire (calcolare) delle espressioni con un livello qualsiasi di
parentesi. Qualcuno mi puņ aiutare? O sa dirmi dove posso trovare
qaulche esempio?
Grazie
------------
  maXRoby
------------

qaulche esempio?
Se sei sotto Unix/Linux :
man lex
man yacc

qaulche esempio?
Io ho scritto proprio qualche giorno fa un programma che accetta
in input una espressione composta da numeri, +-*/ e parentesi
e ne calcola il risultato... il programma lo allego visto che
non occupa molto ... ma ti avviso che quando lo ho scritto non
mi sono preoccupato di renderlo comprensibile e facilmente
manutenibile :)
#include <stdio.h>
#include <ctype.h>
int c,l=2;void s(void){scanf(" %c",&c);}double e(void){
double a=0;if(l){l--;a=e();while((l?(c-'+'?(c-'-'?0:(s(
),a-=e(),1)):(s(),a+=e(),1)):(c-'*'?(c-'/'?0:(s(),a/=e(
),1)):(s(),a*=e(),1))));l++;}else{isdigit(c)?ungetc(c,
stdin),scanf("%lf",&a),s(),1:c-'('?(c-'-'?puts("??"):(s
(),a=-e())):(s(),l=2,a=e(),l=0,c-')'?puts(")!"):(s(),1)
);}return a;}main(){s();printf("=%f\n",e());return 0;}
Scherzi a parte il sistema che preferisco per queste cose e'
scrivere dei parser ricorsivi a discesa; il codice da scrivere
e' semplice e deriva in modo abbastanza naturale dalla
grammatica del linguaggio che devi implementare.
Come alternativa puoi usare anche dei generatori di parser
come yacc o bison (di cui pero' personalmente non sono un
grande tifoso).
Un descrizione seria dei parser ricorsivi a discesa e'
un po' troppo lunga per questo messaggio; se ti servono
maggiori informazioni e quello che trovi in rete non ti
e' chiaro mandami pure una mail.
Forse se ci fosse qualche informazione in piu' si
potrebbero valutare piu' seriamente le alternative. A cosa
ti serve questo programma per calcolare le espressioni ?
 - E' un esercizio ?
 - E' parte di un progetto piu' ampio ?
 - Sono solo semplici calcoli con un solo tipo numerico o
   prevedi tipi diversi con conversioni implicite ?
 - Devi implementare anche una symbol table ?
 - Chiamate a funzioni predefinite come sin(x), atan2(y,x) ?
 - Riferimenti ad altre espressioni (spreadsheet) ?
 - Definizione di funzioni ? Ricorsive ?
Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

 - Definizione di funzioni ? Ricorsive ?
Anche.
Ti ringrazio, cercherò di capirci qualcosa.
Il mio problema è gestire le parentesi, cioè come trovare la parentesi
più interna per iniziale a calocalare i parziali (si fa cosi, vero? o
no?) e dove mettere i valori calcolati e saperli poi ripescare. Il
tutto con il C di più basso livello, visto che andrà tradotto in MIPS.
Grazie ancora.
------------
  maXRoby
------------

no?) e dove mettere i valori calcolati e saperli poi ripescare.
La discesa ricorsiva (che non so come implementerai col MIPS) ti
consente di esaminare le parentesi al livello + profondo.
Cioe', quando incontri una parentesi sai che devi elaborare un'altra
espressione.  Trovandoti al livello + profondo, il calcolo
dell'espressione possiede gia' la precedenza che le compete.
E' piu' facile a dirsi che a farsi.
Cioe', se ho 5 * (2 - 3)
La discesa e'
5
*
(
ho incontrato una parentesi, quindi calcolo un'altra espressione :
2
-
3
)
ho incontrato la parentesi chiusa e risalgo...

 tutto con il C di piů basso livello, visto che andrŕ tradotto in MIPS.
Anche se il codice che ti presento e' in C++ non dovrebbe crearti problemi,
tanto piu' che a te interessa l'algoritmo e non l'implementazione !
<CODE>
/* Parser di espressioni matematiche:
   operatori : * / + - . ( )
   tipi : decimali e non senza segno
#include<iostream.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
#define MAX 80
void EatSpaces(char* buffer);
double Expr(char* str);
double Term(char* str,int& index);
double Number(char* str,int& index);
char* Extract(char* str, int& index);
int main()
{
     char buffer[MAX];
     cout << "Scrivi una espressione: ";
     cin.getline(buffer,MAX);
     cout << (EatSpaces(buffer),buffer) << " = ";
     cout << Expr(buffer) << endl;
     return 0;
}
void EatSpaces(char* buffer)
{
     int a=0,b=0;
     while((buffer[b]=buffer[a++])!='\0'){
          if(buffer[b]!=' ') ++b;
     }
}
double Expr(char* str)
{
     double val=0.0;
     int index=0;
     val=Term(str,index);
     for(;;){
          switch(str[index++]){
          case '\0':
               return val;
          case '+':
               val+=Term(str,index);
               break;
          case '-':
               val-=Term(str,index);
               break;
          default:
               {
                    cout << endl;
                    for(int x=0;x<index-1;++x)
                         cout << " ";
                    cout << "^" << endl;
               }
               cout << "ARGH!! Errore!!!\n"
                     << "Controllare : '" << str[index-1] << "'"
                     << endl;
               exit(1);
          }
     }
}
double Term(char* str, int& index)
{
     double val=0.0;
     val=Number(str,index);
     while((str[index]=='*')||(str[index]=='/')){
          if(str[index]=='*')
               val*=Number(str,++index);
          if(str[index]=='/')
               val/=Number(str,++index);
     }
     return val;
}
double Number(char* str, int& index)
{
     double val=0.0;
     double factor=1.0;
     if(str[index]=='('){
          char* psubstr=0;
          psubstr=Extract(str,++index);
          val=Expr(psubstr);
          delete[]psubstr;
          return val;
     }
     while(isdigit(str[index]))
          val=10*val+(str[index++]-'0');
     if(str[index]!='.')
          return val;
     while(isdigit(str[++index])){
          factor*=0.1;
          val=val+((str[index]-'0')*factor);
     }
     return val;
}
char* Extract(char* str, int& index)
{
     char buffer[MAX];
     char *pstr;
     int numL=0;
     int bufindex=index;
     do{
          buffer[index-bufindex]=str[index];
          switch(buffer[index-bufindex]){
          case ')':
               if(numL==0){
                    buffer[index-bufindex]='\0';
                    ++index;
                    pstr=new char[index-bufindex];
                    if(!pstr){
                         cout << "Errore, memoria esaurita!" << endl;
                         exit(1);
                    }
                    strcpy(pstr,buffer);
                    return pstr;
               }else{
                    --numL;
               }
               break;
          case '(':
               ++numL;
               break;
          }
     }while(str[index++]!='\0');
     cout << "Errore, le parentesi non sono bilanciate! " << endl;
     exit(1);
     return pstr;
}
</CODE>
Il parser accetta numeri decimale (con il .) ed interi, entrambi senza
segno.
Come operatori : + - * /
Inoltre accetta qualsiasi livello di nidificazione delle parentesi.
Per cio' che riguarda la ricorsione (sul Mips) puoi benissimo implementarla
con uno stack ed in questo modo l'algoritmo rimane identico. Altrimenti se
ne cerchi uno iterativo, beh cerchero' di procurartelo, visto che adesso che
ci penso non l'ho mai implementato ! (polacca inversa a parte).
Alex

tutto con il C di più basso livello, visto che andrà tradotto in MIPS.
Questo e' il sistema che avevo usato nel primo programma di calcolo
espressione con parentesi che ho scritto (basic applesoft... quasi
20 anni fa :(((((( ). Cercavo la prima parentesi chiusa della stringa;
quindi tornavo indietro sino alla prima parentesi aperta e poi mi
occupavo del contenuto di quella sezione. Una volta calcolato il
valore sostituivo il risultato nella stringa originale e ripetevo
il procedimento da capo. Un giochetto simile lo usavo per calcolare
moltiplicazioni e divisioni prima di somme e sottrazioni.
Un parser ricorsivo a discesa usa un sistema completamente diverso;
quello che ti scrivo ora e' un esempio con aritmetica intera che
non usa funzioni di libreria C per il calcolo.
-------------------------------
  #include <stdio.h>
  #include <stdlib.h>
  /*
   * Definizione formale di espressione
   * 
   * <term>     ::= <integer> | - <term> | ( <add_expr> ) .
   * <mul_expr> ::= <term> [ <mul_op> <term> ] .
   * <mul_op>   ::= '*' | '/' .
   * <add_expr> ::= <mul_expr> [ <add_op> <mul_expr> ] .
   * <add_op>   ::= '+' | '-' .
   * <integer>  ::= <digit> [ <digit> ] .
   * <digit>    ::= '0' | '1' | '2' | '3' | '4' |
   *                '5' | '6' | '7' | '8' | '9' .
   * <expr>     ::= <add_expr> ';' .
   * 
   */
  char *expr;   /* Puntatore al carattere corrente */
  char *error;  /* Messaggio di errore o NULL se tutto ok */
  int calc_add_expr(void); /* Forward */
  int calc_integer(void)
  {
    int acc=0,x;
    do
    {
      x=-1;
      switch(*expr)
      {
        case '0' : x=0; break;
        case '1' : x=1; break;
        case '2' : x=2; break;
        case '3' : x=3; break;
        case '4' : x=4; break;
        case '5' : x=5; break;
        case '6' : x=6; break;
        case '7' : x=7; break;
        case '8' : x=8; break;
        case '9' : x=9; break;
      }
      if (x!=-1)
      {
        acc=acc*10+x;
        expr++;
      }
    } while (x!=-1);
    return acc;
  }
  void skip_spaces(void)
  {
    while (*expr==' ') expr++;
  }
  int calc_term(void)
  {
    int v;
    skip_spaces();
    switch(*expr)
    {
      case '-':
        expr++;
        v=-calc_term();
        break;
      case '(':
        expr++;
        v=calc_add_expr();
        if (!error)
        {
          if (*expr!=')')
            error="')' mancante";
          else
            expr++;
        }
        return v;
      case '0':
      case '1':
      case '2':
      case '3':
      case '4':
      case '5':
      case '6':
      case '7':
      case '8':
      case '9':
        v=calc_integer();
        break;
      default:
        error="Atteso <term>";
    }
    return v;
  }
  int calc_mul_expr(void)
  {
    int v=calc_term();
    skip_spaces();
    while (!error && (*expr=='*' || *expr=='/'))
    {
      char c=*expr++;
      int v2=calc_term();
      switch(c)
      {
        case '*':
          v*=v2;
          break;
        case '/':
          if (v2==0) error="Divisione per zero";
                else v/=v2;
          break;
      }
    }
    return v;
  }
  int calc_add_expr(void)
  {
    int v=calc_mul_expr();
    skip_spaces();
    while(!error && (*expr=='+' || *expr=='-'))
    {
      char c=*expr++;
      int v2=calc_mul_expr();
      switch(c)
      {
        case '+':
          v+=v2;
          break;
        case '-':
          v-=v2;
          break;
      }
    }
    return v;
  }
  int calc_expr(void)
  {
    int v=calc_add_expr();
    if (!error && *expr!=';')
      error="Atteso ';'";
    return v;
  }
  int main()
  {
    char line[200];
    int value;
    puts("Inserire l'espressione chiusa da ';':");
    fgets(line,sizeof(line),stdin);
    error=NULL; expr=line;
    value=calc_expr();
    if (error)
    {
      printf("%*s^\n",expr-line,"");
      printf("Errore: %s\n",error);
      return EXIT_FAILURE;
    }
    printf("Valore = %i\n",value);
    return EXIT_SUCCESS;
  }
-------------------------------
Nota come la struttura del programma derivi quasi
direttamente dalla descrizione BNF del linguaggio in
cui sono enunciate le espressioni.
Questo programma puo' ovviamente essere migliorato di molto...
in questo caso ho cercato di essere il piu' chiaro possibile
su quale fosse l'algoritmo di parsing a discesa ricorsiva.
Una variante abbastanza semplice permette di accorpare tutti
gli operatori in una sola tabella in cui si puo' indicare la
priorita' e l'associativita' a destra oppure a sinistra.
Facendo in questo modo diventa piu' comoda l'aggiunta di nuovi
operatori; qui non e' complicata... ma si tratta di copia-incolla
(cosa se possibile da evitare). Nota come ad esempio
calc_add_expr sia molto simile a calc_mul_expr... e' possibile
fare in modo di dover indicare semplicemente le differenze.
HTH


       }
con:
 if((*expr>='0') && (*expr<='9'))
      x=*expr-'0';
Lo so, sono un fanatico, forse potrei fare qualche programma per la tua
sezione dei Piccoli, ma che ci vuoi fare ....
Alex

       x=*expr-'0';
Non è portabile, a differenza della versione di Andrea Griffini.
EMG

sezione dei Piccoli, ma che ci vuoi fare ....
Bravo genio, peccato che la tua soluzione non sia portabile.
Come la mettiamo su un sistema in cui i caratteri da '0' a '9' non
sono in sequenza ?

 Non è portabile, a differenza della versione di Andrea Griffini.
Lo so, e' vero !
E' anche vero che quasi tutti i computer usano la codifica ASCII, e quelli
che non la usano usano sempre (o quasi) una codifica in cui i numeri da '0'
a '9' sono in sequenza.
Conosci qualche computer attuale in cui questo non accada ? Sono sicuro che
esista, ma e' che questa cosa (i numeri in  sequenza) sono cosi' comuni che
vi ci si basa sopra moltissimo codice del K&R !
Certo a loro questo appunto non lo avete mai fatto !
Ero stato abbastanza chiaro che la mia non era un correzzione, che il suo
codice andava benone, e che io, non riesco pero' a controllarmi quando vedo
del codice cosi' lungo e ripetitivo.
Alex



Io ho le idee un po' confuse al riguardo. Non possiedo lo
standard ma ho visto posting di gente che dice che le cifre
numeriche devono necessariamente essere in sequenza e posting
di gente che dice che questo non e' vero.
Io personalmente non ho mai incontrato un encoding in cui i
numeri non fossero in sequenza (per le lettere invece il
discorso e' diverso: anche nel diffusissimo EBCDIC con cui ho
avuto a che fare le lettere non sono in sequenza) ma ho
preferito stare sul sicuro con dei test caso-per-caso.
Qualcuno che ha accesso allo standard puo' chiarire questo
punto (meglio se citando il passo) ?
Nei documenti (non ufficiali) in mio possesso non sono riuscito
a trovare nulla al riguardo (non ho pero' indagato a fondo).


per la tua sezione dei Piccoli, ma che ci vuoi fare ....
I programmi che ho scritto nella sezione "quelli piccoli" ho
cercato di farli portabili demandando questa cosa a isdigit
e a scanf. Nel programma di calcolo espressione ho preferito
non usare nessuna funzione di libreria durante il calcolo
visto che chi aveva il problema doveva tradurre la cosa in
un altro linguaggio.
Tu sei sicuro che quel codice sia portabile ?


 del codice cosi' lungo e ripetitivo.
Il problema č che il tuo codice non ha le stesse caratteristiche di
quello di Andrea e quindi non ne č un sostituto.
EMG

un altro linguaggio.
La mia in effetti era una battuta. La soluzione migliore e'
senza dubbio quella di usare la libreria standard.
Se tu invece, come mi dici, hai scritto il programma per poter
essere tradotto anche in altri linguaggi allora la scelta
di non usare le funzioni di libreria e' ben valutata.
Per concludere ti riporto una parte del K&R:
<QUOTE>
c-'0'
Questo vale soltanto se '0', '1', ...... , '9' possiedono tutti valori
crescenti e consecutivi. Fortunatamente cio' e' vero per tutti i set di
caratteri.
[CUT]
Usare una simile convenzione e' molto vantaggiosa.
</QUOTE>
In sostanza anche il K&R conferma che oggi giorno non esistono
set di caratteri in cui il mio codice non sia portabile.
Alex

 sono in sequenza ?
Ti riporto una parte del K&R:
<QUOTE>
c-'0'
Questo vale soltanto se '0', '1', ...... , '9' possiedono tutti valori
crescenti e consecutivi. Fortunatamente cio' e' vero per tutti i set di
caratteri.
[CUT]
Usare una simile convenzione e' molto vantaggiosa.
</QUOTE>
In sostanza anche il K&R conferma che oggi giorno non esistono
set di caratteri in cui il mio codice non sia portabile.
Alex
P.S. lamentati anche con gli autori del libro ;-)

 quello di Andrea e quindi non ne è un sostituto.
Mah... io la penso diversamente !
Alex

di gente che dice che questo non e' vero.
Non ho messo mano allo standard, ma come ho letto
da qualche parte, e come e' anche sottointeso nel K&R:
Le cifre non devono essere necessariamente sequenziali.
Di fatto pero' lo sono in tutti i seti di caratteri sul mercato.
Quindi, a mio parere, il codice che fa uso di questa convenzione
e' da considerarsi portabile fino a che non venga introdotto un
set di caratteri che non faccia uso di questa convenzione.
Dubito sinceramente che tale cosa accadra' !
Non avendo messo mano allo standard attendo anche io
conclusioni piu' ufficiali.
Alex

Fortunatamente cio' e' vero per tutti i set di caratteri.
Il K&R II ed. e' stato scritto quando lo standard non era ancora stato
approvato.  Finquando non leggo un documento ufficiale su questo
argomento, continuo a ritenere il tuo codice non portabile.
Se e' per questo, il K&R, a pag. 52, dice testualmente :
<K&R>
L'header standard <ctype.h> descritto nell'Appendice B definisce una
famiglia di funzioni che forniscono meccanismi di controllo
econversione indipendenti dal set di caratteri. Per esempio, la
funzione tolower(c) restituisce il valore minuscolo di c se c e'
maiuscolo [...].
Analogamente, il controllo :
c >= '0' && c <= '9'
puo' essere sostituito con 
isdigit(c)
D'ora in poi, useremo spesso le funzioni definite in <ctype.h>
</K&R>

controllarmi quando vedo del codice cosi' lungo e ripetitivo.
Controllati.

set di caratteri in cui il mio codice non sia portabile.
A pag. 362 dice anche: 
"Notiamo con piacere che it.comp.lang.c, il ng italiano sul linguaggio
C, e' frequentato da un geniaccio di nome Alex".

non-ASCII, quindi ho optato per la versione "srotolata".
Niente paura, il nostro amico e' famoso per voler correggere a tutti i
costi programmi gia' corretti.

 isdigit(c)
Per restituire il carattere minuscolo di un carattere e' fondamentale usare
tolower() !!!
Infatti non esiste solo la codifica ASCII, ne esistono altre ed in alcune le
lettere minuscole sono di piu' di quelle maiuscole**. Quindi fare c+'a'-'A'
non e' detto che dia il giusto risultato su tutte le macchine.
Inoltre in molti character set le lettere minuscole vengono prima di quelle
maiuscole(il contrario di ASCII).
Altri ancora hanno le lettere "interlaced" ovvero aAbBcC e cosi' via. In
passato esistevano anche character sets con solo lettere maiuscole ;-)
** Anche sui PC ASCII EX ci sono piu' lettere minuscole che maiuscole .Sono
le lettere accentate. Ma e' diverso, visto che fanno parte dei caratteri
estesi e sono tutte messe in fondo. Non trovi insomma ABCDE...Z e
aאbcdeטי...z ma trovi abcde...z e poi, in fondo אטיעלש etc... (in questo
modo non danno fastidio).
Vuoi un esempio. Uno a caso, non so nemmeno dove sia utilizzato questo
charset, ma il IBM256 ad esempio ha tutte le lettere sparse.
Ovviamente tutti i charseti piu' utilizzati rendono sensato il codice
c+'a'-'A' ! (ma non tutti, mentre c-'0'  in tutti).
Il fatto e' che invece TUTTE le codifiche hanno una codifica dei numeri
crescenti e consecutivi, ed in tutte vanno da '0' a '9'. Di conseguenza
isdigit() non e' altrettanto indispensabile ! (anche se e' il modo piu'
sicuro ed elegante).
Certo, esiste la funzione isdigit() che ogni compilatore implementera' al
meglio !
Sono convinto che usare isdigit() sia la soluzione migliore.
Ad ogni modo il testo da te riportato non dice mica che esiste un set di
caratteri in cui il controllo c >= '0' && c <= '9' non funzioni ! Anzi, come
ti ho detto nell'altro messaggio, il libro, dice esplicitamente che alla
data di stesura dello stesso non esisteva alcun set di caratteri che renda
il controllo c >= '0' && c <= '9' non valido.
In conclusione io ho detto che c-'0' e' sicuro visto che non esiste
character set che non funzioni con tale codice, non ho mai detto che
c+'a'-'A' e' sicuro, visto che esistono parecchi character sets per i quali
tale codice non ha senso.
Alex

 costi programmi gia' corretti.
Per prima cosa ho detto in modo molto chiaro che non ho voluto correggere
nessuno, visto che il codice e' giusto.
Seconda cosa il tuo programma "famoso" non era corretto:
aveva un errore e lo hai corretto e poi ti ho fatto notare che nonostante la
tua correzzione risulta ANCORA errato ! (e tu d'altra parte hai corretto il
mio che era altrettanto errato, solo che io non mi vergogno a dirlo).
Terza ed ultima cosa non sono tuo amico, come tu non sei mio amico.
Che scopo aveva questo messaggio che voleva solamente essere una lamentela
su di me ?!? Sono stanco di sentirmi dire : "stupido", "geniaccio", "nostro
amico", "imbecille" etc... Vedi di non prendere troppa confidenza, ok ?!?
Io dico quello che penso e tu pure. Se la pensiamo in modo diverso pazienza.
Vedi solo di non insultare e di non prendere troppa confidenza.
Se vuoi rispondi pure a questo messaggio. Ma non credo abbia senso
altrimenti rischiamo di fare come su it.comp.programmare.win32. Certo che
sei sempre tu che attacchi e "cerchi rogna". Che bisogno c'era di questo
messaggio cosi' inutile ?!?
Alex

C, e' frequentato da un geniaccio di nome Alex".
???????????
Alex

 Mah... io la penso diversamente !
E fai bene. Sai che pizza se la pensassimo tutti allo stesso modo?
Comunque, da quello che hai scritto, potresti avere ragione.
EMG

  }
Non e' fondamentale in questo contesto in cui viene valutata
solo una <expr> ma per completezza e' giusto che ci sia.
Una <expr> termina con un ';' ed e' giusto che questo ';'
venga tolto dalla sequenza in input.


On Thu, 07 Jun 2001 23:30:30 GMT, 
agr...@tin.it
 (Andrea Griffini)
wrote:
Dopo aver chiesto in comp.lang.c ho scoperto che sia nel C90
che nel recente C99 (paragrafo 5.2.1) e' garantito che le cifre
numeriche decimali siano caratteri consecutivi e positivi.
Questo permette di riscrivere calc_integer come
  int calc_integer(void)
  {
    int acc=0;
    while (*expr>='0' && *expr<='9')
      acc=acc*10+(*expr++ - '0');
    return acc;
  }
e di modificare calc_term in
  int calc_term(void)
  {
    int v=0;
    skip_spaces();
    switch(*expr)
    {
      case '-':
        expr++;
        v=-calc_term();
        break;
      case '(':
        expr++;
        v=calc_add_expr();
        if (!error)
        {
          if (*expr!=')')
            error="')' mancante";
          else
            expr++;
        }
        return v;
      default:
        if (*expr>='0' && *expr<='9')
          v=calc_integer();
        else
          error="Atteso <term>";
    }
    return v;
  }
guadagnando in compattezza e leggibilita' (senza nulla
perdere in termini di portabilita' ANSI).
Andrea
PS:
  Il loop di calc_integer e' quello che scrivo di
  solito in questi casi... pero' non ero sicuro che
  fosse garantito funzionare su sistemi non ASCII.
  Non si finisce mai di imparare :)


   Non si finisce mai di imparare :)
Infatti, tanto piu' che l'informatica oltre ad essere una materia
praticamente infinita e' anche in continua espansione ;-)
Grazie ancora per il chiarimento,
Alex

Grazie a tutti, mi avete dato dei buoni spunti (e un bel algoritmo)
per iniziare a lavorarci. Visto che ci sono, come funziona l'opzione
-mmips-as di gcc e soprattutto, perchè non funziona? Dovrebbe generare
codice assembler mips da un sorgente C (se non erro) ma non mi
funziona, mi da 'invalid option mips-as'.

maXRoby wrote:

La butto la' xche non è un xcross compiler. Segui il followup, la ti 
sapranno dare la risposta giusta.