[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)



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

[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