[c/c++] lettura albero di espressioni aritmetiche

[pmhwp]

Ciao,
ho un albero binario che fa il parsing di una espressione matematica, come ad esempio 5+(4*3)

http://img46.imageshack.us/img46/6238/immagineaq3.th.jpg (http://img46.imageshack.us/my.php?image=immagineaq3.jpg)http://img46.imageshack.us/images/thpix.gif (http://g.imageshack.us/thpix.php)

Come posso fare per rileggerlo e risolverlo trovando il valore finale?

Grazie.

[Vincenzo1968]

Ciao,

devi attraversare ricorsivamente l'albero chiedendo ad ogni nodo di valutare se stesso.
Un nodo valuta se stesso restituendo il proprio valore se si tratta di un operando; se si tratta invece di un operatore, restituisce il valore dell'applicazione dell'operatore ai propri figli.

Questo è un esempio:


double EvalTree(Tree *pTree)
{
double dblLeft;
double dblRight;

if ( !pTree )
return 0.0;

switch ( pTree->tok->Type )
{
case VALUE:
return pTree->tok->Value;
case PLUS:
return EvalTree(pTree->left) + EvalTree(pTree->right);
case MINUS:
return EvalTree(pTree->left) - EvalTree(pTree->right);
case MULT:
return EvalTree(pTree->left) * EvalTree(pTree->right);
case DIV:
dblLeft = EvalTree(pTree->left);
dblRight = EvalTree(pTree->right);
if ( dblRight == 0 )
{
printf("Errore: divisione per zero!\n");
return 0.0;
}
else
{
return dblLeft / dblRight;
}
case EXP:
return pow(EvalTree(pTree->left), EvalTree(pTree->right));
case UPLUS:
return EvalTree(pTree->right);
case UMINUS:
return -1 * EvalTree(pTree->right);
default:
if ( pTree->tok->Type == OPAREN )
printf("Errore: parentesi non bilanciate.\n");
else
printf("Operatore non riconosciuto: %c\n", pTree->tok->str);
//printf("Operatore non riconosciuto: %s", pTree->tok->str);
return 0.0;
}
}


Il codice completo lo trovi qui (http://www.guidealgoritmi.it/ShowArticle.aspx?ID=4) :)

[sottovento]

Riassumendo: visita simmetrica

[pmhwp]

mi puoi fare un esempio di visita in pre ordine?? grazie

[sottovento]

Quella che ha fatto Vincenzo1968 e' una visita simmetrica.
Cmq, questa e' la mia versione (praticamente uguale a quella di Vincenzo):


double EvalTree(Tree *pTree)
{
if (pTree)
{
if (!pTree->left && !pTree->right)
return toDouble(pTree->token);

double leftVal = EvalTree(pTree->left);
double rightVal = EvalTree(pTree->right);
double val = executeOperation (pTree->token, leftVal, rightVal);
}
return 0.0;
}


L'implementazione di toDouble() ed executeOperation() immagino sia banale