tree - significado - ¿Acerca de la notación de árboles y prefijo(polaco)?

trie significado

Question

Mi clase de ensamblaje de MIPS me requería que leyera en una expresión de tamaño desconocido en un Árbol Parse. Nunca tuve que lidiar con árboles, así es como me fui almacenando valores:

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

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

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

Así es como construí el árbol. Apuntaría del operando al operador al siguiente operando al siguiente operador hasta que no quedaran más valores para leer.

Mi siguiente tarea fue recorrer el árbol recursivamente y dar salida a los valores en notación infijo / prefijo / postfijo.

El recorrido infijo no fue un problema considerando cómo construí mi árbol.

Estoy atascado en el prefijo. En primer lugar, no lo entiendo completamente.

Cuando emita nuestra expresión (1 + 3 - 4) en el prefijo, ¿debería salir - + 1 3 4? Tengo problemas para seguir los ejemplos en línea.

¿También crees que mi árbol está construido correctamente? Quiero decir, no tengo forma de ir a un nodo anterior desde el nodo actual, lo que significa que siempre tengo que comenzar el cruce desde el nodo secundario 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

En general, debe construir un árbol de tal manera que todos los nodos hoja (aquellos sin hijos) sean operandos, y los nodos internos (todo lo demás) sean operadores. Esto debería ser así para que los hijos de un nodo operador sean sus operandos, o ellos mismos operadores que tienen operandos. Si puede construir un árbol de esta manera, Formar las diversas anotaciones (prefijo, postfijo, infijo) es bastante simple: simplemente sigue los recorridos preordenados, postorden e inorden del árbol, para los cuales existen algoritmos bien conocidos.

Por lo que puedo decir, no estás construyendo un árbol, sino una lista enlazada, y esto no te va a servir bien. Tienes 2 entidades diferentes, operandos y operadores, tienes que tratarlos de manera diferente.

Answer 2

Esta es una instancia del problema general de la compilación, que es un problema resuelto. Si realiza un google sobre técnicas de compilación, encontrará toda clase de información relacionada con su problema.

Su biblioteca debe tener una copia de Compiladores: Principios, técnicas y herramientas de Aho, Sethi y Ullman. Si no lo tiene, solicítelo para comprarlo (es el trabajo estándar en el campo). La primera parte de esto debería ayudarte.

Enlace de la tercera edición

Answer 3

Estoy de acuerdo con lo que dice Sykora. Me gustaría agregar que también puedes usar una pila en este caso. Si su tarea requiere que use específicamente un árbol, entonces la sugerencia de Sykora funcionaría mejor. Sin embargo, una pila puede ser más fácil de programar para la evaluación de expresiones simples.

Answer 4

Su árbol de análisis debe tener un aspecto similar a este:

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

Cada nodo tiene dos punteros. Uno a su hijo izquierdo y otro a su hijo derecho. No hay necesidad de punteros para los nodos principales, cuando se utiliza el recorrido recursivo.

Aquí hay un pseudocódigo:

Recorrido 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);
    }
}

Recorrido 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);
    }
}

Recorrido para la notación postfix :

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

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

    print(node->value);
}

traverse método traverse con el nodo raíz de tu árbol.

Su estructura de datos de 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 ayuda escribir estas cosas en un lenguaje de nivel superior (lo que sea que se sienta cómodo) para comprender el problema y luego "traducir" este código a ensamblador. Recuerdo programar una simulación mundial de bloques en un ensamblador MIPS como este.