À propos des arbres et des préfixes (polonais) Notation?

Question

Ma classe d'assemblage MIPS m'a demandé de lire une expression de taille inconnue dans un arbre d'analyse. Je ne l'ai jamais eu à traiter avec des arbres, donc voilà comment je suis allé autour de valeurs: stockage

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) 

Voilà comment je construit l'arbre. Ma tâche suivante consistait à parcourir récursivement l'arborescence et à générer les valeurs en notation infix/prefix/postfix.

La traversée d'infixes n'était pas un problème compte tenu de la façon dont j'ai construit mon arbre.

Je suis bloqué sur le préfixe. Premièrement, je ne comprends pas tout à fait.

Lorsque j'exprime notre expression (1 + 3 - 4) dans le préfixe devrait-il sortir - + 1 3 4? J'ai de la difficulté à suivre les exemples en ligne.

Pensez-vous également que mon arbre est construit correctement? Je n'ai aucun moyen d'aller à un nœud précédent à partir du nœud actuel, ce qui signifie que je dois toujours commencer la traversée depuis le nœud enfant le plus à gauche qui ne semble pas correct, même si mon AT a dit que c'était le chemin à parcourir.

Nous vous remercions de votre aide.

Answer 1

Votre arbre d'analyse syntaxique devrait ressembler à ceci:

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

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

Voici quelques 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 la 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:Vous appelez la méthode traverse avec le nœud racine de votre arborescence. Vous pouvez appeler cette méthode traverse.

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.

Il est parfois utile d'écrire ces informations dans un langage de niveau supérieur (quel que soit votre niveau de compréhension) pour comprendre le problème, puis "traduire" ce code en assembleur. Je me souviens avoir programmé une simulation blocks world dans l'assembleur MIPS comme ceci.

Answer 2

En général, vous devez construire un arbre de telle sorte que tous les nœuds feuilles (ceux sans enfant) soient des opérandes, et les nœuds internes (tout le reste) sont des opérateurs. Cela devrait être fait de sorte que les enfants d'un nœud d'opérateur soient ses opérandes, ou eux-mêmes des opérateurs qui ont des opérandes. Si vous pouvez construire un arbre de cette manière, Former les différentes notations (préfixe, postfixe, infixe) est assez simple - Vous suivez juste les traversées de précommande, de post-commande et d'inorder de l'arbre, pour lesquelles il existe des algorithmes bien connus. Pour autant que je sache, vous ne construisez pas un arbre, mais plutôt une liste liée, et cela ne vous servira pas bien. 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 sykora dit. Je voudrais ajouter que vous pouvez également utiliser une pile dans ce cas. Si votre mission vous oblige à utiliser spécifiquement un arbre, alors la suggestion de sykora fonctionnerait mieux. Cependant, une pile peut être plus facile à programmer pour une évaluation d'expression simple.

Answer 4

Ceci est une instance du problème général de la compilation, 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 ce n'est pas le cas, demandez-le à l'achat (c'est le travail standard dans le domaine). La première partie devrait vous aider.

Third edition link