Newsgroup: it.comp.lang.c
Titolo: notazione infissa

Ciao a tutti,
sto cercando di implementare un algoritmo che trasformi un espressione
matematica in forma infissa:
2+(3-5)*4/2
in un albero binario o in un espressione in forma prefissa tipo:
+ 2 * - 3 5 / 4 2
L'espressione è data da una lista dai seguenti elementi:
union elemento{
    int  numero;
    char operatore; /* può essere '+' '-' '*' '/' oppure '\0' */
};                  /* in questo caso l'elemento è un numero  */
union elemento *lista;
NOTA: Va bene anche una struct anzichè una union ovviamente..
L'elemento può essere valutato come numero o come operatore..
Ne viene fuori un albero tipo (scusate il disegno abbastanza
stilizzato):
 Albero:(NOTA: Cip, Ciop e le loro ghiande non vengono rappresentati)
 ---2
 |               -----3
'+'      -------'-'
 |       |       -----5
 -------'*'
         |       -----4
         -------'/'
                 -----2
E' un bel problema, non credete?
Grazie in anticipo, anzi, in anticiPOST (ah ah),
       tano

+ 2 * - 3 5 / 4 2
L'algoritmo non e' complicato.  L'importante e' che tu abbia
due stack, uno degli operandi ed uno degli operatori.
Scorri la stringa, inserendo cio' che incontri nel
rispettivo stack, ignorando le parentesi aperte.
Non appena incontri una parentesi chiusa, allora estrai i
due operandi, estrai l'operatore e crei la sottoespressione,
reinserendola nello stack operandi.
Procedi cosi' finquando ci sono parentesi chiuse.
Procedi cosi' finquando nello stack operandi non c'e' un
solo elemento.
Prendendo ad esempio la tua stringa:
2+(3-5)*4/2
Ecco i vari passi:
1. stack operatori  -  stack operandi
                              2 
2. stack operatori  -  stack operandi
         +                    2 
3. la parentesi aperta viene ignorata
4. stack operatori  -  stack operandi
         +                    2 
                              3
5. stack operatori  -  stack operandi
         +                    2 
         -                    3
6. stack operatori  -  stack operandi
         +                    2 
         -                    3
                              5
7. incontrata parentesi chiusa, si estrae 5, poi si estrae
3, si estrae l'operatore - e si crea "- 3 5" reinserendola
nello stack operandi:
   stack operatori  -  stack operandi
           +                    2 
                             - 3 5
8. stack operatori  -  stack operandi
          +                    2 
          *                  - 3 5
                               4
9. stack operatori  -  stack operandi
          +                    2 
          *                  - 3 5
          /                    4
                               2
10. a questo punto c'e' la fine della stringa e si procede 
ai vari pop/push negli stack:
11. stack operatori  -  stack operandi
          +                    2 
          *                  - 3 5
                             / 4 2
12. stack operatori  -  stack operandi
          +                    2 
                         * - 3 5 / 4 2
13. stack operatori  -  stack operandi
                       + 2 * - 3 5 / 4 2
E' rimasto un solo elemento nello stack operandi, che
equivale alla stringa in notazione prefissa.

 union elemento *lista;
quella che c'è sotto è una funzione simile a quella che stai cercando di realizzare, legge da file
un'espressione (senza parentesi e divisa da spazi bianchi) e la mette su un'albero per calcolarla.
ha qualche limitazione (non considera le divisioni per zero...) ma ti può servire come spunto per
realizzare il tuo algoritmo....
--
~*dyablo*~
mail: 
dya...@virgilio.it
typedef struct nodo
{ int value;
  char op;
  struct nodo *sx;
  struct nodo *dx;
} NODO;
void makesx(NODO *ptr, int value)
{ ptr->sx=(NODO *)malloc(sizeof(NODO));
  ptr->sx->sx=ptr->sx->dx=NULL;
  ptr->sx->op=0;
  ptr->sx->value=value;
}
void makedx(NODO *ptr, int value)
{ ptr->dx=(NODO *)malloc(sizeof(NODO));
  ptr->dx->sx=ptr->dx->dx=NULL;
  ptr->dx->op=0;
  ptr->dx->value=value;
}
NODO *CreaAlbero( FILE *fp)
{ NODO *root, *last, *ptr, *prec;
  char op, level=0;
  int x;
  fscanf(fp,"%d", &x);
  prec=last=root=(NODO *)malloc(sizeof(NODO));
  root->sx=root->dx=NULL;
  root->op=0;
  root->value=x;
  while(fread(&op,1,1,fp))
  { fscanf(fp,"%c",&op);
    fscanf(fp,"%d",&x);
    if ((op=='*' || op=='/'))
    { if(level==0)
      { last->op=op;
        makesx(last,last->value);
        makedx(last,x);
        prec=last;
        last=last->dx;
      }
      else
      { ptr=(NODO *)malloc(sizeof(NODO));
        ptr->op=op;
        if(prec==root)
        { ptr->sx=root;
          root=ptr;
        }
        else
        { ptr->sx=root->dx;
          root->dx=ptr;
        }
        makedx(ptr,x);
        last=ptr->dx;
      }
      level=1;
    }
    else
    { ptr=(NODO *)malloc(sizeof(NODO));
      ptr->sx=root;
      ptr->op=op;
      makedx(ptr,x);
      last=ptr->dx;
      prec=root=ptr;
      level=0;
    }
  }
  return root;
}
void Calcola(NODO *ptr)
{ if(ptr->sx->op)
    Calcola(ptr->sx);
  if(ptr->dx->op)
    Calcola(ptr->dx);
  switch (ptr->op)
  { case '+': ptr->value=ptr->sx->value + ptr->dx->value; break;
    case '-': ptr->value=ptr->sx->value - ptr->dx->value; break;
    case '*': ptr->value=ptr->sx->value * ptr->dx->value; break;
    case '/': ptr->value=ptr->sx->value / ptr->dx->value; break;
  }
  ptr->op=0;
  free(ptr->sx);
  free(ptr->dx);
}