Valuta l'espressione di Postfix usando un albero in C ++

c++ expression-trees postfix-notation

Domanda

Dovrei valutare un'espressione postfissa usando un albero di espressioni. Supponiamo che io abbia un albero come questo

    -
   / \
  +   *
 / \  / \
a  b  c  d

Prima devo valutare un sottoalbero + b e memorizzarne il risultato nel nodo +, poi c * d e così via fino a quando non ho il risultato nel nodo radice.

Ho provato l'approccio ricorsivo usando uno stack, ma non funzionava. Lo pseudocodice sembrava così

  1. funzione eval (nodo)
  2. eval (node-> a sinistra)
  3. eval (node-> a destra)
  4. se (il nodo è un nodo foglia), spingerlo sullo stack
  5. altrimenti if (node ​​è un operando) pop ae pop b dallo stack node-> value = a-> valore op b-> valore delete ab;

Tuttavia questo non ha funzionato. Devo anche mostrare l'albero ad ogni passo in modo da mostrare la riduzione dei nodi. L'ho cercato su Google molte volte ma non sono riuscito a trovare la risposta richiesta. Qualcuno per favore aiutami come fare questo.

void expression_tree::evaluate(node *temp)
{
    if(!temp)
    return;
/// stack_postfix obj;
    stack_postfix obj2;
    evaluate(temp->left);
    evaluate(temp->right);
        if(temp->right == NULL && temp->left == NULL)
        {
            obj2.push(temp);
        }
        else
        {
            node * a = obj2.pop();
            node *b = obj2.pop();
            temp->value = a->value + b->value;
            delete a;
            delete b;
        }

}

Risposta accettata

hai 2 opzioni:

eval della foglia:

1 - basta premere il valore per impilare

eval di non_leaf:

1 - eval left, - REMEMBER: il risultato eval aggiunto allo stack.

2 - eval right,

3 - pop 2 elementi,

4 - calcola,

5 - spingere il risultato.

alla fine avrai 1 oggetto in pila - l'ultimo risultato

MODIFICARE:

void expression_tree::evaluate(node *temp, stack& s)
{
   if(!temp)
      return;

   if(temp->left != NULL && temp->right  != NULL){
       //only 1 pointer is illegal!
       evaluate(temp->left);
       evaluate(temp->right);
       node* n2 = s.pop();
       node* n1 = s.pop();
       //in the stack should be only leaves
       temp->value = n1->value + n2->value;//use switch by operator 
       delete temp->left; 
       temp->left = NULL;
       delete temp->right; 
       temp->right=NULL;
   }
   s.push (temp);
}

Risposta popolare

Hai dimenticato obj2.push(temp->balue); nella parte opposta

Tuttavia, ci sono più errori, lo stack deve essere condiviso tra le chiamate di funzione, quindi la funzione può effettivamente elaborarlo



Autorizzato sotto: CC-BY-SA with attribution
Non affiliato con Stack Overflow
È legale questo KB? Sì, impara il perché
Autorizzato sotto: CC-BY-SA with attribution
Non affiliato con Stack Overflow
È legale questo KB? Sì, impara il perché