A propos des arbres et la notation Prefix (polonais)?

Question

Mon MIPS classe Assemblée m'a obligé de lire dans une expression de taille inconnue dans une arborescence Parse. Je ne l'ai jamais eu à traiter avec des arbres, donc voilà comment je suis allé dans le stockage des valeurs:

permet de dire que l'utilisateur est entré dans l'expression 1 + 3 - 4 (chaque opérande ne peut être un chiffre 1-9)

Mon nœud enfant à gauche serait le point de départ et contiennent 2 morceaux de données

1. The operand
2. Pointer to the next node (operator)

Voici comment je construisais l'arbre. Je voudrais signaler à l'opérateur de l'opérande à opérande suivant à l'opérateur suivant jusqu'à ce qu'il n'y avait pas plus de valeurs de gauche à être lu.

Ma tâche suivante était de parcourir l'arborescence récursive et sortie les valeurs infix / préfixe / notation Postfix.

Infix Sonceboz était pas de problème compte tenu de la façon dont je construisais mon arbre.

Je suis bloqué sur le préfixe. Tout d'abord, je ne comprends pas pleinement.

Quand je sortie notre expression (1 + 3 - 4) préfixe devrait-il sortir - + 1 3 4? Je vais avoir du mal à suivre les exemples en ligne.

Aussi, vous ne pensez que mon arbre est construit correctement? Je veux dire, je n'ai aucun moyen d'aller à un nœud précédent à partir du noeud courant qui signifie que je dois toujours commencer traversal à l'extrême gauche nœud enfant qui ne instinctivement sonne pas juste, même si mon TA dit que c'était la voie à suivre.

Merci pour toute aide.

Answer 1

Votre arbre d'analyse syntaxique devrait ressembler à ceci:

        '-'
         |
     +---+---+
     |       |
    '+'     '4'
     |
 +---+---+
 |       |
'1'     '3'

Chaque nœud a deux pointeurs. Un enfant à son gauche et un à son enfant droit. Il n'y a pas besoin de pointeurs vers des nœuds parents, lors de l'utilisation traversal récursive.

Voici une pseudo-code:

Traversal pour notation infixe :

void traverse(Node *node) {
    if (node->leftChild != 0) {
        traverse(node->leftChild);
    }

    print(node->value);

    if (node->rightChild != 0) {
        traverse(node->rightChild);
    }
}

Traversal pour notation préfixe :

void traverse(Node *node) {
    print(node->value);

    if (node->leftChild != 0) {
        traverse(node->leftChild);
    }

    if (node->rightChild != 0) {
        traverse(node->rightChild);
    }
}

Traversal pour notation postfix :

void traverse(Node *node) {
    if (node->leftChild != 0) {
        traverse(node->leftChild);
    }

    if (node->rightChild != 0) {
        traverse(node->rightChild);
    }

    print(node->value);
}

Vous appelez la méthode traverse avec le nœud racine de l'arborescence.

Votre structure de données Node aurait besoin de trois membres:

struct Node {
    char value;
    Node *leftChild;
    Node *rightChild;
}

Les feuilles de l'arbre contiendrait des pointeurs nuls pour leftChild et rightChild.

Parfois, il aide à écrire ce genre de choses dans un langage de haut niveau (ce que vous sentez à l'aise) pour comprendre le problème et « traduire » ce code assembleur. Je me souviens d'une programmation en assembleur MIPS comme celui-ci.

Answer 2

En général, vous devez construire un arbre de telle sorte que tous les nœuds feuilles (ceux sans enfants) sont opérandes, et les noeuds internes (tout le reste) sont des opérateurs. Cela devrait être pour que les enfants d'un noeud opérateur sont ses opérandes, ou eux-mêmes opérateurs qui ont opérandes. Si vous pouvez construire un arbre de cette manière, formant les différentes notations (préfixe, Postfix, infixes) sont assez simples - Vous suivez simplement la pré-commande, et postorder afinde traversals de l'arbre, pour lesquels il existe des algorithmes bien connus

Pour autant que je peux dire, vous n'êtes pas construire un arbre plutôt une liste chaînée, et cela ne va pas bien vous servir. Vous avez 2 entités différentes - opérandes et opérateurs - vous devez les traiter différemment

.

Answer 3

Je suis d'accord avec ce que dit Sykora. Je voudrais ajouter que vous pouvez également utiliser une pile dans ce cas. Si votre mission vous oblige à utiliser spécifiquement un arbre, puis la suggestion de Sykora fonctionnerait mieux. Cependant, une pile peut être plus facile à programmer pour une évaluation simple expression.

Answer 4

Ceci est un exemple du problème général de la compilation, ce qui est un problème résolu. Si vous faites un google sur les techniques de compilation, vous trouverez toutes sortes d'informations relatives à votre problème.

Votre bibliothèque doit avoir une copie de Compilateurs: principes, techniques et outils par Aho, Sethi et Ullman. Si elle ne l'a pas, en faire la demande à l'achat (c'est le travail standard dans le domaine). La première partie de celui-ci devrait vous aider.

lien Troisième édition