Umwandlung von a (b (cd) e (fg)) in einen Baum

  • Dies wurde tatsächlich in einem Interview gefragt. Ich habe es auf die bestmögliche Art und Weise gemacht, die ich optimieren könnte und möchte, wenn sich eine Chance ergibt.

    Die Eingabe lautet:

     a(b(cd)e(fg)) 
     

    Die Ausgabe sollte folgendermaßen aussehen:

                                 a
                               / \
                              b   e
                             / \ / \
                            c  d f  g
     

    Mein aktueller Code lautet:

     #include<stdio.h>
    #include<malloc.h>
    #include<string.h>
    
    struct node
    {
        char x;
        struct node *left;
        struct node *right;
    }*root;
    
    char a[30];
    int i=0,n;
    
    void tre(struct node * p) //function that I am using to convert the string to a tree
    {
            if(a[i]=='(')
            {
                i++;
                struct node *temp=malloc(sizeof(struct node));
                temp->x=a[i];
                temp->left=temp->right=NULL;
                i++;
                if(p->left==NULL)
                {
                    p->left=temp;
                    tre(p->left);
                }
                if(a[i]!='('&&a[i]!=')')
                {
                    struct node *tempp=malloc(sizeof(struct node));
                    tempp->x=a[i];
                    i++;
                    p->right=tempp;
                    tre(p->right);
                }
            }
            else
            if(a[i]==')')
            {
                i++;
            }
    
    }    
    
    void inorder(struct node *p)//inorder traversal of the tree made
    {    
        if(p!=NULL)
        {
            inorder(p->left);
            printf("%c ",p->x);
            inorder(p->right);
        }
    }
    
    main()
    {
        printf("Enter the string : ");
        scanf("%s",a);
        struct node *temp=malloc(sizeof(struct node));
        temp->x=a[i];
        temp->left=temp->right=NULL;
        i++;
        root=temp;
        tre(root);
        inorder(root);
    }
     
    05 December 2016
    Jamal
3 answers
  •  void tre(struct node * p) //function that I am using to convert the string to a tree
    {
            if(a[i]=='(')
            {
     

    Ich empfehle, solche kurzen Variablennamen nicht zu verwenden

                 i++;
                struct node *temp=malloc(sizeof(struct node));
                temp->x=a[i];
                temp->left=temp->right=NULL;
     

    Sie wiederholen diese drei Zeilen grundsätzlich dreimal. Wenn Sie dies stattdessen am Anfang von tre tun, können Sie die Duplizierung vermeiden.

                 i++;
                if(p->left==NULL)
     
    Ihr Code ist strukturiert. Ist p- & gt; left immer null? Der an tre übergebene Wert ist immer ein neu erstellter Knoten

                 {
                    p->left=temp;
                    tre(p->left);
                }
                if(a[i]!='('&&a[i]!=')')
     

    Warum müssen Sie dies überprüfen? ? Wäre das nicht eine ungültige Eingabe? Wenn ja, sollten Sie den Fehler vielleicht irgendwie melden.

                 {
                    struct node *tempp=malloc(sizeof(struct node));
                    tempp->x=a[i];
                    i++;
                    p->right=tempp;
                    tre(p->right);
                }
    
            }
            else
            if(a[i]==')')
            {
                i++;
            }
     

    Nochmals in welcher Situation wird dies aufgerufen?

     }    
     

    Wie würde ich diese Funktion angehen

     stuct node * tre()
    { 
         struct node * node = malloc(sizeof(struct node));
         node->x = a[i++];
         if(a[i] == '(')
         {
              node->left = tre();
              node->right = tre();
              assert(a[i++] == ')');
         }
         else
         {
              node->left = node->right = NULL;
         }
         return node;
    }
     

    Wenn mir etwas fehlt, passen Ihre Beispielausgabe und Ihr Code nicht zusammen. Ich werde das nicht kommentieren.

    11 December 2011
    Mark Cidade
  • Wenn dies in einem Interview gefragt wurde, hätte ich als Fragesteller erwartet, dass Sie einige weitere Fragen zum Eingabeformat stellen. Was wir hier haben, ist für das einfache Beispiel relativ klar, aber es gibt einige Untertitel, die aus diesem Eingabeformat herauskommen.

    • Wie werden NULL-Zweige dargestellt?
    • Wie werden Knoten mit dem Wert ')' oder '(' dargestellt.
    • Wenn wir '(' öffnen) werden Seien Sie immer zwei Knoten vor den ')'

    Mein erstes Problem wären diese globalen Variablen:

     char a[30];
    int i=0,n;
     

    Langfristig ist es schwieriger, den Code zu ändern und zu pflegen, was in den meisten Situationen vermieden werden sollte, da Parameter und Dinge viel flexibler werden.

    Der zweite Punkt besteht darin, jede Variable in einer eigenen Zeile zu deklarieren (sie ist viel lesbarer) und die Namen aussagekräftiger zu machen. a, i, n halten also keine Bedeutung Ich habe keine Ahnung, wofür Sie sie verwenden werden.

    In C finde ich es nützlich, typedef-Strukturen zu verwenden, um sicherzustellen, dass ich die kurze Version des Namens verwenden kann (ich habe sie nicht verwendet C im Ärger Ich bin mir nicht sicher, ob dies die beste Methode ist, aber ich denke, der Code wird lesbarer.)

    > Wenn wir einen Baum bauen, würde ich normalerweise erwarten, dass der Rückgabewert der Baum ist, den wir bauen. Keine Möglichkeit, den Baum auszufüllen. Ich würde also erwarten, dass die Funktionssignatur so aussieht:

     Node* tre(char const* input)  // potentially more parameters to deal with position.
     

    Ich finde die Logik in Ihrer Hauptfunktion sehr schwer zu folgen. Sie scheinen nur Knoten zu bilden, wenn eine offene Klammer "(", die nicht korrekt erscheint). Sie tun nichts, wenn eine enge Klammer vorhanden ist. Sie testen, ob die Linke auf dem aktuellen Knoten null ist, nicht aber die Rechte auf dem aktuellen Knoten Ich würde erwarten, dass der Code von Natur aus symmetrischer ist. Die Tatsache, dass dies nicht der Fall ist, macht es schwieriger zu folgen.

    Als Interviewer würde ich das gerne tun

    12 December 2011
    Joseph Daigle
  • WENN die Anforderung tatsächlich war

    Die Eingabe lautet:

     a(b(cd)e(fg)) 
     

    Die Ausgabe sollte folgendermaßen aussehen:

                                a
                              / \
                             b   e
                            / \ / \
                           c  d f  g
     
    blockquote>

    Wie Sie oben dargelegt haben, ist der gesamte von Ihnen geschriebene Code sowie der Code in anderen Antworten unnötig kompliziert und im Grunde irrelevant.

    Eine geeignete Antwort auf eine solche -Frage lautet wie folgt:

     #include <string.h>
    
    int main(int argc, char *argv[])
    {
        if(argc >= 2 && strcmp(argv[1], "a(b(cd)e(fg))") == 0)
            puts(
                 "               a"      "\n"
                 "              / \\"    "\n"
                 "             b   e"    "\n"
                 "            / \\ / \\" "\n"
                 "           c  d f  g"  "\n"
                );
        return 0;
    }
     
    11 December 2016
    C Nick