Sobre los árboles y el prefijo de notación (polaco)?

Question

Mi clase Asamblea MIPS me obligó a leer en una expresión de tamaño desconocido en un árbol de análisis sintáctico. Nunca he tenido que lidiar con los árboles, así que esta es la forma en que fui alrededor de almacenar valores:

Digamos que el usuario ha introducido la expresión 1 + 3 - 4 (cada operando sólo podría ser un dígito 1-9)

Mi nodo hijo más a la izquierda sería el punto de partida y contener 2 piezas de datos

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

Esta es la forma en que se construyo el árbol. Me volvería a punto de operando al operador siguiente operando al lado del operador hasta que no había más valores de la izquierda para ser leído en.

Mi siguiente tarea consistía en recorrer el árbol de forma recursiva y la salida de los valores en infija prefijo / notación / postfix.

Infijo recorrido había ningún problema teniendo en cuenta cómo construí mi árbol.

Estoy atascado en el prefijo. En primer lugar, no entiendo por completo.

Cuando la salida nuestra expresión (1 + 3 - 4) en caso de que el prefijo salido - + 1 3 4? Estoy teniendo problemas para seguir los ejemplos en línea.

También cree usted que mi árbol se construye correctamente? Quiero decir, no tengo manera de ir a un nodo anterior del nodo actual que significa que siempre tengo que comenzar el recorrido desde el nodo hijo más a la izquierda, que instintivamente no suena bien, aunque mi TA dijo que era el camino a seguir.

Gracias por cualquier ayuda.

Answer 1

Su árbol de análisis debería ser algo como esto:

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

Cada nodo tiene dos punteros. Uno a su hijo izquierdo y uno derecho a su hijo. No hay ninguna necesidad de punteros a nodos padre, cuando se utiliza recorrido recursivo.

Aquí hay algo pseudocódigo:

Traversal para notación infija :

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

    print(node->value);

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

Traversal para notación de prefijo :

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

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

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

Traversal para notación postfix :

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

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

    print(node->value);
}

Se podría llamar al método traverse con el nodo raíz del árbol.

Su estructura de datos Node necesitaría tres miembros:

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

Las hojas del árbol contendrían punteros nulos para leftChild y rightChild.

A veces es útil para escribir estas cosas en un lenguaje de alto nivel (lo que sea que se sienta cómodo) para entender el problema y luego "traducir" el código de ensamblador. Recuerdo la programación de la simulación de un mundo en MIPS ensamblador como este.

Answer 2

En general, usted debe construir un árbol de tal manera que todos los nodos hoja (aquellos que no tienen hijos) son operandos, y los nodos internos (todo lo demás) son los operadores. Esto debe ser así que los hijos de un nodo de operador son sus operandos, o ellos mismos operadores que tienen operandos. Si usted puede construir un árbol de esta manera, que forman las diversas notaciones (prefijo, Postfix, infijos) son bastante simple - sólo tienes que seguir el orden previo, a finde orden posterior y recorridos del árbol, para los que existen algoritmos conocidos

Por lo que yo puedo decir, no se está construyendo un árbol, en lugar de una lista enlazada, y esto no va a servir bien. Usted tiene 2 entidades diferentes - operandos y operadores - hay que tratarlos de forma diferente

.

Answer 3

Estoy de acuerdo con lo que dice sykora. Me gustaría añadir que también se puede utilizar una pila en este caso. Si su asignación requiere el uso de un árbol en concreto, a continuación, la sugerencia de sykora funcionaría mejor. Sin embargo, una pila puede ser más fácil de programar para la evaluación simple expresión.

Answer 4

Este es un ejemplo del problema general de compilación, que es un problema resuelto. Si lo hace un google en técnicas de compilación, se encuentra todo tipo de información relacionada con su problema.

Su biblioteca debe tener una copia de Compiladores: Principios, Técnicas y Herramientas por Aho, Sethi y Ullman. Si no lo tiene, solicitarlo para su compra (que es la obra de referencia en el campo). La primera parte de Que le ayudará.

Tercera edición enlace