Sobre Árvores e Prefixo Notation (polonês)?

Question

classe Meu Assembléia MIPS obrigava-me a ler em uma expressão de tamanho desconhecido em uma árvore de análise. Eu nunca teve de lidar com árvores, por isso esta é a forma como eu fui em torno de armazenar valores:

Vamos dizer que o usuário inseriu a expressão 1 + 3-4 (cada operando só poderia ser um dígito 1-9)

Meu nó mais à esquerda criança seria o ponto de partida e contêm 2 partes de dados

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

Isto é como eu construí a árvore. Gostaria de partir operando para o operador para o próximo operando para o próximo operador até que não houvesse mais valores deixaram de ser lido em.

A minha próxima tarefa era percorrer a árvore de forma recursiva e fornecer os valores em infix / prefixo / postfix notação.

Infix travessia havia nenhum problema considerando como eu construí minha árvore.

Eu estou preso no prefixo. Em primeiro lugar, eu não compreendê-lo totalmente.

Quando eu saída a nossa expressão (1 + 3 - 4) no prefixo que deve sair - + 1 3 4? Estou tendo dificuldade para seguir os exemplos on-line.

Além disso você acha que minha árvore é construída corretamente? Quer dizer, eu não tenho como ir a um nó anterior do nó atual que significa que eu sempre tenho que começar a travessia do nó filho mais à esquerda que instintivamente não soa bem, embora o meu TA disse que era o caminho a percorrer.

Obrigado por qualquer ajuda.

Answer 1

A sua árvore de análise deve ser algo como isto:

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

Cada nó tem dois ponteiros. Um para seu filho esquerdo e um para a sua criança direita. Não há necessidade de ponteiros para nós pai, quando se utiliza travessia recursiva.

Eis alguns pseudocódigo:

Traversal para infix notação :

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

    print(node->value);

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

Traversal para prefixo notação :

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

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

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

Traversal para postfix notação :

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

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

    print(node->value);
}

Você chamaria o método traverse com o nó raiz de sua árvore.

A sua estrutura de dados Node precisaria de três membros:

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

As folhas da árvore que contêm ponteiros nulos para leftChild e rightChild.

Às vezes ele ajuda a escrever este material em uma linguagem de alto nível (o que quer que você se sinta confortável) para entender o problema e, em seguida, "traduzir" este código de assembler. Lembro-me de programação de um blocos mundo simulação em MIPS assembler como esta.

Answer 2

Em geral, você deve construir uma árvore de tal maneira que todos os nós de folha (aqueles sem filhos) estão operando, e os nós internos (tudo mais) são operadores. Isso deve ser de modo que os filhos de um nó de operador são seus operandos, ou próprios operadores que têm operandos. Se você pode construir uma árvore dessa maneira, formando a várias notações (prefixo, postfix, infixas) são bastante simples - É só seguir a pré-venda, pós-ordem e inorder traversals da árvore, para o qual existem algoritmos bem conhecidos

Tanto quanto eu posso dizer, você não está construindo uma árvore, em vez de uma lista ligada, e isso não vai atendê-lo bem. Você tem 2 entidades diferentes - operandos e operadores - você tem que tratá-los de forma diferente

.

Answer 3

Concordo com o que sykora diz. Gostaria de acrescentar que você também pode usar uma pilha neste caso. Se sua tarefa exige que você use especificamente uma árvore, em seguida, a sugestão de sykora iria funcionar melhor. No entanto, uma pilha pode ser mais fácil de programa para a avaliação da expressão simples.

Answer 4

Este é um exemplo do problema geral da compilação, que é um problema resolvido. Se você fizer um google em técnicas de compilação, você vai descobrir todos os tipos de informações relativas ao seu problema.

A sua biblioteca deve ter uma cópia do Compiladores: Princípios, técnicas e ferramentas por Aho, Sethi, e Ullman. Se ele não tiver, solicitá-lo para a compra (que é o padrão de trabalho no campo). A primeira parte do que deve ajudá-lo.

terceiro elo edição