Evaluar la expresión de Postfix usando un árbol en C ++

c++ expression-trees postfix-notation

Pregunta

Se supone que debo evaluar una expresión postfix usando un árbol de expresiones. Supongamos que tengo un árbol como este

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

Primero necesito evaluar un subárbol a + b y almacenar su resultado en el nodo +, luego c * d y así sucesivamente hasta que tenga el resultado en el nodo raíz.

Intenté el enfoque recursivo utilizando una pila, pero eso no estaba funcionando. El pseudocódigo se veía así.

  1. función eval (nodo)
  2. eval (nodo-> izquierda)
  3. eval (nodo-> derecha)
  4. si (el nodo es un nodo de hoja) empújelo en la pila
  5. si no (el nodo es un operando), haga clic en pop a y pop b desde stack node-> value = a-> value op b-> value delete ab;

Sin embargo esto no funcionó. También tengo que mostrar el árbol en cada paso para mostrar que los nodos se están reduciendo. Busqué en Google muchas veces pero no pude encontrar la respuesta requerida. Alguien por favor ayúdame a hacer esto.

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;
        }

}

Respuesta aceptada

tienes 2 opciones:

eval de hoja:

1 - solo presiona el valor para apilar

eval de non_leaf:

1 - eval izquierda, - RECUERDE: el resultado de eval agregado a la pila.

2 - evalua derecha,

3 - Pop 2 artículos,

4 - calcular,

5 - Empuje el resultado.

al final tendrás 1 elemento en la pila: el último resultado

EDITAR:

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);
}

Respuesta popular

Olvidaste obj2.push(temp->balue); en la otra parte

Sin embargo, hay más errores, la pila debe compartirse entre las llamadas de función, por lo que la función puede procesarla



Licencia bajo: CC-BY-SA with attribution
No afiliado con Stack Overflow
Licencia bajo: CC-BY-SA with attribution
No afiliado con Stack Overflow