О деревьях и префиксе (польском языке)

Question

Мой класс сборки MIPS потребовал, чтобы я прочитал выражение неизвестного размера в дерево разбора. Мне никогда не приходилось иметь дело с деревьями, поэтому я хранил значения:

Допустим, пользователь ввел выражение 1 + 3 - 4 (каждый операнд может быть только цифрой 1-9)

Мой самый левый дочерний узел будет отправной точкой и будет содержать 2 элемента данных

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

Так я построил дерево. Я бы указывал от операнда до оператора к следующему операнду до следующего оператора, пока не останется больше значений для чтения.

Моей следующей задачей было рекурсивно пройти по дереву и вывести значения в нотациях infix / prefix / postfix.

Обход инфикса не был проблемой, учитывая, как я построил свое дерево.

Я застрял на префиксе. Во-первых, я не до конца понимаю.

Когда я вывожу наше выражение (1 + 3 - 4) в префиксе, оно должно получиться - + 1 3 4? У меня проблемы с отслеживанием онлайн-примеров.

Как вы думаете, моё дерево построено правильно? Я имею в виду, что у меня нет возможности перейти к предыдущему узлу с текущего узла, что означает, что мне всегда нужно начинать обход с самого левого дочернего узла, который инстинктивно звучит неправильно, даже если мой TA сказал, что это путь.

Спасибо за любую помощь.

Answer 1

Ваше дерево разбора должно выглядеть примерно так:

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

Каждый узел имеет два указателя. Один слева от него и один справа от него. При использовании рекурсивного обхода указатели на родительские узлы не нужны.

Вот какой-то псевдокод:

Обход для инфиксной записи :

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

    print(node->value);

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

Обход для обозначения префикса :

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

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

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

Обход для постфиксной записи :

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

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

    print(node->value);
}

Вы бы вызвали метод traverse с корневым узлом вашего дерева.

Для вашей Node структуры данных потребуется три члена:

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

Листья дерева будут содержать нулевые указатели для leftChild и rightChild.

Иногда бывает полезно написать этот материал на языке более высокого уровня (независимо от того, что вам удобно), чтобы понять проблему, а затем «перевести» этот код на ассемблер. Я помню программирование мира блоков симуляция в ассемблере MIPS следующим образом.

Answer 2

В общем случае вы должны построить дерево таким образом, чтобы все конечные узлы (те, у которых нет дочерних элементов) были операндами, а внутренние узлы (все остальное) - операторами. Это должно быть так, чтобы потомками узла оператора были его операнды или сами операторы, у которых есть операнды. Если вы можете построить дерево таким способом, Формирование различных обозначений (префикс, постфикс, инфикс) довольно прост - вы просто следуйте обходам дерева по предварительному заказу, порядку и порядку, для которых существуют хорошо известные алгоритмы. *

Насколько я могу судить, вы создаете не дерево, а связанный список, и это вам не очень пригодится. У вас есть 2 разных объекта - операнды и операторы - вы должны обращаться с ними по-разному.

Answer 3

Это пример общей проблемы компиляции, которая является решенной проблемой. Если вы изучите методы компиляции, вы найдете всю информацию, касающуюся вашей проблемы.

В вашей библиотеке должна быть копия Компиляторы: принципы, методы и инструменты от Aho, Sethi и Ullman. Если у него его нет, запросите его на покупку (это стандартная работа в поле). Первая часть этого должна вам помочь.

Третье издание ссылка

Answer 4

Я согласен с тем, что говорит Сикора. Я хотел бы добавить, что вы также можете использовать стек в этом случае. Если ваше задание требует, чтобы вы специально использовали дерево, то предложение Sykora будет работать лучше всего. Однако стек может быть проще для программирования для простого вычисления выражений.