A proposito di alberi e del prefisso notazione (polacco)?

Question

La mia classe Assembly MIPS mi ha richiesto di leggere in un'espressione di dimensioni sconosciute in un albero sintattico. Non ho mai avuto a che fare con gli alberi, quindi questo è come sono andato in giro per la memorizzazione di valori:

Diciamo che l'utente ha immesso l'espressione 1 + 3 - 4 (ogni operando non poteva che essere una cifra 1-9)

Il mio nodo figlio più a sinistra sarebbe il punto di partenza e contenere 2 pezzi di dati

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

Questo è come ho costruito l'albero. Vorrei ricordare da operando operatore successivo operando al successivo operatore fino non c'erano più valori lasciati da leggere in.

Il mio prossimo compito era quello di attraversare l'albero in modo ricorsivo e in uscita i valori in infisso / prefisso / suffisso notazione.

Infix attraversamento era un problema considerando come ho costruito il mio albero.

Sono bloccato sul prefisso. In primo luogo, non capisco appieno.

Quando ho uscita nostra espressione (1 + 3 - 4) nel prefisso deve venire fuori - + 1 3 4? Sto avendo difficoltà a seguire gli esempi on-line.

Anche pensi che il mio albero è costruito in modo corretto? Voglio dire, non ho modo di andare in un nodo precedente dal nodo corrente che significa che devo sempre iniziare la traversata dal nodo figlio più a sinistra, che istintivamente non suona bene anche se la mia TA ha detto che era la strada da percorrere.

Grazie per tutto l'aiuto.

Answer 1

Il tuo albero di analisi dovrebbe essere simile a questo:

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

Ogni nodo ha due puntatori. Un bambino alla sua sinistra e una a suo figlio destro. Non v'è alcuna necessità di puntatori ai nodi padre, quando si utilizza attraversamento ricorsivo.

Ecco alcuni pseudocodice:

Traversal per infissa notazione :

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

    print(node->value);

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

Traversal per prefisso notazione :

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

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

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

Traversal per postfix notazione :

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

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

    print(node->value);
}

Si potrebbe chiamare il metodo traverse con il nodo radice del vostro albero.

Il tuo struttura di dati Node avrebbe bisogno di tre membri:

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

Le foglie dell'albero conterrebbero puntatori nulli per leftChild e rightChild.

A volte aiuta a scrivere questa roba in un linguaggio di alto livello (qualunque cosa si sente a proprio agio con) per capire il problema e poi "tradurre" il codice di assembler. Mi ricordo di programmazione di simulazione di un mondo in MIPS assembler come questo.

Answer 2

In generale si dovrebbe costruire un albero in modo tale che tutti i nodi foglia (quelle senza figli) sono operandi, ei nodi interni (tutto il resto) sono operatori. Questo dovrebbe essere così che i figli di un nodo operatore sono i suoi operandi, o se stessi operatori che hanno operandi. Se si riesce a costruire un albero in questo modo, che forma le varie notazioni (prefisso, postfix, infisso) sono abbastanza semplice - Basta seguire il preorder, postorder e simmetrico attraversamenti dell'albero, per i quali sono ben noti algoritmi

Per quanto ne so, non si sta costruendo un albero, piuttosto una lista collegata, e questo non è andare a servire bene. Hai 2 diversi soggetti - operandi e operatori - è necessario trattare in modo diverso

.

Answer 3

Sono d'accordo con quello che dice Sykora. Vorrei aggiungere che è anche possibile utilizzare una pila in questo caso. Se il vostro incarico richiede di utilizzare in modo specifico un albero, poi il suggerimento di Sykora avrebbe funzionato meglio. Tuttavia, una pila potrebbe essere più facile da programmare per una semplice valutazione delle espressioni.

Answer 4

Questo è un esempio del problema generale di compilazione, che è un problema risolto. Se fate un google sulle tecniche di compilazione, troverete tutti i tipi di informazioni relative al tuo problema.

La vostra biblioteca dovrebbe avere una copia di compilatori: principi, tecniche e strumenti di Aho, Sethi, e Ullman. Se non ce l'ha, richiesta per l'acquisto (è il lavoro standard nel campo). La prima parte del Dovrebbe aiutare.

terzo anello edizione