Infix-Ausdruck in einen Stapel lesen

Question

Ich habe Code geschrieben, um einen Ausdrucksbaum in Vorbestellung und Postorder umzuwandeln, aber ich habe Mühe, den Ausdrucksbaum aus einem Infix-Ausdruck zu erstellen. Ich habe eine .cc-Datei, die die Funktion build_expression_tree aufruft, die Konvertierungsfunktionen aufruft und die konvertierten Ausdrücke ausgibt.

Dies ist meine aktuelle Nicht-Arbeitsfunktion:

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

Die Fehler ich an dieser Stelle bekommen sind: Expression_Tree.h: 61: 40: Fehler: ISO C++ verbietet Vergleich zwischen Zeiger und integer

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

Expression_Tree.h: 62: 13: Fehler: 'Temp' wurde nicht in diesem Bereich erklärt

temp->right = tree_stack.top(); 

Expression_Tree.h: 62: 13: Fehler: ‚Temp‘ wurde in diesem Rahmen

temp->left = tree_stack.top(); 

Ich weiß, warum die letzten beiden Fehler (nicht im Gültigkeitsbereich deklariert) auftreten, aber ich weiß nicht erklärt einfach nicht wissen, was zu tun ist, um es zu beheben, während ich meinen Code richtig arbeiten lasse.

Ich weiß nicht einmal, ob mein Code völlig falsch ist, aber irgendwelche Tipps würden unglaublich geschätzt werden! Danke.

EDIT: Dies sind die Klassen, die die Build_Expression_Tree-Funktion beeinflussen.

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

Hier habe ich Ihre Beispieleingabe in eine Darstellung aufgeteilt, wie der Stack verwendet werden kann und welche Entscheidungen bei jedem Input getroffen werden.

// _ = 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 

Bitte beachte, dass ich viele doppelte Aussagen haben, einen Typ für ( eine für ) eine für eine Reihe 0-9 und eine für jeden Betrieb +-*/. Sie haben bereits diese Unterteilungen in Ihrem Code, damit Sie auf dem richtigen Weg sind.

( Der einzige Job sollte sein, einen neuen Knoten oben auf dem Stapel zu erstellen. In Ihrem Code gibt es keinen Sinn, input = '(' zu setzen, da es später von einer tatsächlichen Eingabe überschrieben wird und seine Position im Stapel ist alles was benötigt wird, um es zu verfolgen. Sie sollten input zu '\0' oder etwas anderes, das leer bedeutet, initialisieren.

) 's Aufgabe sollte sein, den Deckel vom Stapel zu knallen und ihn dorthin zu bringen, wo es hingehört. Das ist entweder der linke Knoten der nächsten oberen Ebene, wenn es Null ist, andernfalls ist es der rechte Knoten von oben. Sie müssen den Stack nicht wie bei Ihnen durchlaufen, denn es ist immer nur das Top, an dem wir interessiert sind.

Der Job einer Nummer sollte sein, sich selbst als ein neuer Knoten zu erstellen und sich dorthin zu setzen, wo es hingehört. Genau wie ) ist das der linke Knoten der obersten Ebene, wenn es Null ist, sonst ist es der rechte Knoten von Top. In Ihrem Code erstellen Sie den Knoten, aber Sie setzen ihn nicht auf den Stapel.Es tut nicht gut dort, weil ein Zahlknoten immer ein Blattknoten ist (kein Recht oder verlassen).

Schließlich sollte ein Job die Aufgabe sein, sich einfach auf die Top input zu setzen. Es gibt jedoch einen speziellen Fall, bei dem der Anfang bereits ausgefüllt wurde (wenn Sie 1+2+3 tun, ist der 1+2 Knoten oben). Also, was Sie in diesem Fall tun können, ist Pop von der Spitze, schieben Sie einen neuen Knoten an der Spitze, fügen Sie die alte Spitze als die linke, und dann stellen Sie sich selbst auf Top input. Sie brauchen keine Schleife.

Nachdem alles fertig ist, können Sie einfach root = tree_stack.top() setzen.

Wenn Sie den Code möchten, kann ich es liefern, aber ich hoffe, meine Erklärung ist genug.

Code: Dies scheint für mich

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

Ein kurzer Blick zeigt, dass Sie ein ETNode *temp = new ETNode; kurz nach while(tree_stack.top() != '(') benötigen. Ich habe die Logik jedoch nicht überprüft.