Lire l'expression infixe dans une pile

Question

J'ai écrit du code pour convertir une arborescence d'expression en précommande et en post-commande, mais j'ai du mal à construire l'arbre d'expression à partir d'une expression infixe. J'ai un fichier .cc qui appellera la fonction build_expression_tree, appellera les fonctions de conversion et imprimera les expressions converties.

Ceci est ma fonction actuelle de non-travail:

void Expression_Tree::build_expression_tree(char input[], int size) 
{ 
    for (int i = 0; i < size; i++) 
    { 
     if (input[i] == ' ') 
     { 
      i++; 
     } 
     if(input[i] >= '0' && input[i] <= 9) 
     { 
      ETNode *temp = new ETNode; 
      temp->left = temp->right = NULL; 
      temp->input = input[i]; 

      tree_stack.push(temp); 
     } 
     else if (input[i] == '(') 
     { 
      ETNode *temp = new ETNode; 
      temp->left = temp->right = NULL; 
      temp->input = input[i]; 

      tree_stack.push(temp); 
     } 
     else if (input[i] == ')') 
     { 
      while (tree_stack.top() != '(') 
      { 
       temp->right = tree_stack.top(); 
       tree_stack.pop(); 
       temp->left = tree_stack.top(); 
       tree_stack.pop(); 
       tree_stack.pop(); 
       tree_stack.push(temp); 
      } 
     } 
     else if (input[i] == '+' || input[i] == '-' || input[i] == '*' || input[i] == '/') 
     { 
      while (!tree_stack.empty()) 
      { 
       ETNode *temp = new ETNode; 
       temp->left = temp->right = NULL; 
       temp->input = input[i]; 

       tree_stack.push(temp); 

       temp->right = tree_stack.top(); 
       tree_stack.pop(); 
       temp->left = tree_stack.top(); 
       tree_stack.pop(); 

       tree_stack.push(temp); 
      } 
     } 
    } 
} 

Les erreurs que je reçois à ce stade sont les suivants: Expression_Tree.h: 61: 40: Erreur: ISO C++ interdit comparaison entre pointeur et entier

while(tree_stack.top() != '(') 

Expression_Tree.h: 62: 13: erreur: 'temp' n'a pas été déclarée dans ce champ

temp->right = tree_stack.top(); 

Expression_Tree.h: 62: 13: Erreur: « temp » n'a pas été déclarée dans ce champ

temp->left = tree_stack.top(); 

Je sais pourquoi les deux dernières erreurs (non déclarées dans la portée) se produisent, mais je ne tout simplement pas Je sais quoi faire pour résoudre le problème tout en faisant fonctionner correctement mon code.

Je ne sais même pas si mon code est complètement faux, mais tous les conseils seraient incroyablement appréciés! Merci.

EDIT: Ce sont les classes qui affectent la fonction Build_Expression_Tree.

class ETNode { 
public: 
    char input; 
    ETNode *left, *right; 
}; 

class Expression_Tree { 
public: 
    Expression_Tree() { root = 0; }; 
    ~Expression_Tree() { clear(root); } 
    void build_expression_tree(char[], int); 
    void inorder() { inorder(root); } 
    void preorder() { preorder(root); } 
    void postorder() {postorder(root); } 
private: 
    ETNode* root; 
    std::stack<ETNode*> tree_stack; 
    void visit(ETNode* p) { std::cout << p->input << " "; } 
    void inorder(ETNode*); 
    void preorder(ETNode*); 
    void postorder(ETNode*); 
    void clear(ETNode*); 
}; 

Answer 1

Ici, j'ai divisé votre entrée d'exemple en une représentation de la façon dont la pile peut être utilisée et les décisions prises à chaque entrée.

// _ = nullptr or empty 
// # = pointer to subtree (not just a number) 
// | ___ |  |  |  begin (empty element on stack) 
// | 2__ |  |  | 2 make number node and set to top->left if empty, else top->right 
// | 2+_ |  |  | + set top->input if not set, else pop parent into left of new node 
// | 2+_ | ___ |  | ( make new node on stack 
// | 2+_ | 3__ |  | 3 make number node and set to top->left if empty, else top->right 
// | 2+_ | 3*_ |  | * set top->input if not set, else pop parent into left of new node 
// | 2+_ | 3*_ | ___ | ( make new node on stack 
// | 2+_ | 3*_ | 2__ | 2 make number node and set to top->left if empty, else top->right 
// | 2+_ | 3*_ | 2+_ | + set top->input if not set, else pop parent into left of new node 
// | 2+_ | 3*_ | 2+2 | 2 make number node and set to top->left if empty, else top->right 
// | 2+_ | 3*# |  | ) pop it off into its parent 
// | 2+# |  |  | ) pop it off into its parent 
// | #+_ |  |  | + set top->input if not set, else pop parent into left of new node 
// | #+5 |  |  | 5 make number node and set to top->left if empty, else top->right 

Notez que j'ai beaucoup de déclarations en double, un type de ( un pour ) un pour plusieurs 0-9 et un pour chaque opération +-*/. Vous avez déjà ces divisions dans votre code, donc vous êtes sur la bonne voie. Le seul travail devrait être de créer un nouveau nœud en haut de la pile. Dans votre code, il n'y a aucun point à définir input = '(' car il va être remplacé par une entrée réelle plus tard et sa position dans la pile est tout ce qui est nécessaire pour garder une trace de celui-ci. Vous devez initialiser input à '\0' ou autre chose signifiant vide.

) Le travail devrait être de faire tomber le haut de la pile et de le placer là où il doit aller. Ce sera le noeud gauche du prochain sommet si c'est nul, sinon ce sera le bon noeud du dessus. Vous n'avez pas besoin de boucler la pile comme vous le faites, car ce sera toujours le top que nous sommes intéressés à éclater.

Le travail d'un numéro devrait être de se créer comme un nouveau nœud et de se placer là où il doit aller. Tout comme ) qui sera soit le nœud de gauche du top s'il est nul, sinon ce sera le nœud de droite du top. Dans votre code, vous faites le noeud mais vous ne le placez nulle part ailleurs sur la pile.Cela ne sert à rien parce qu'un nœud numérique sera toujours un nœud feuille (pas de droite ou de gauche).

Enfin, le travail d'une opération devrait être simplement de se mettre à input du sommet. Cependant, il y a un cas spécial où le sommet a déjà été rempli (quand vous faites 1+2+3, le 1+2 est le nœud en haut). Donc, ce que vous pouvez faire dans ce cas est de sauter du haut, de pousser un nouveau nœud sur le dessus, d'ajouter l'ancien sommet comme étant à gauche, puis de simplement se placer sur le input du sommet. Vous n'avez pas besoin d'une boucle.

Après tout, vous pouvez simplement définir root = tree_stack.top().

Si vous voulez le code je peux le fournir mais j'espère que mon explication est suffisante.

code: Cela semble fonctionner pour moi

void Expression_Tree::build_expression_tree(char input[], int size) 
{ 
    // assuming empty tree_stack, it shouldn't really be a member 
    // variable since its only used for building 
    //std::stack<ETNode*> tree_stack; 

    // make empty node, should really make a default constructor set all this up 
    tree_stack.push(new ETNode); 
    tree_stack.top()->left = nullptr; 
    tree_stack.top()->right = nullptr; 
    tree_stack.top()->input = '\0'; 

    for (int i = 0; i < size; i++) 
    { 
    if (input[i] == ' ') 
    { 
     i++; 
    } 
    if (input[i] >= '0' && input[i] <= '9') // this 9 had a typo before 
    { 
     // create number leaf 
     ETNode *temp = new ETNode; 
     temp->left = nullptr; 
     temp->right = nullptr; 
     temp->input = input[i]; 

     // put where it needs to go 
     if (tree_stack.top()->left == nullptr) 
     tree_stack.top()->left = temp; 
     else 
     tree_stack.top()->right = temp; 
    } 
    else if (input[i] == '(') 
    { 
     // make empty node 
     ETNode *temp = new ETNode; 
     temp->left = nullptr; 
     temp->right = nullptr; 
     temp->input = '\0'; 

     tree_stack.push(temp); 
    } 
    else if (input[i] == ')') 
    { 
     // pop top from the stack 
     ETNode *temp = tree_stack.top(); 
     tree_stack.pop(); 

     // put where it needs to go 
     if (tree_stack.top()->left == nullptr) 
     tree_stack.top()->left = temp; 
     else 
     tree_stack.top()->right = temp; 
    } 
    else if (input[i] == '+' || input[i] == '-' || input[i] == '*' || input[i] == '/') 
    { 
     // shuffle node if already filled 
     if (tree_stack.top()->input != '\0') 
     { 
     ETNode *old = tree_stack.top(); 
     tree_stack.pop(); 

     ETNode *temp = new ETNode; 
     temp->left = old; 
     temp->right = nullptr; 

     tree_stack.push(temp); 
     } 

     tree_stack.top()->input = input[i]; 
    } 
    } 

    // set root node 
    root = tree_stack.top(); 
} 

Answer 2

Un rapide coup d'oeil révèle que vous avez besoin d'un ETNode *temp = new ETNode; juste après while(tree_stack.top() != '('). Je n'ai pas vérifié la logique, cependant.