О деревьях и префиксной (польской) нотации?

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

        '-'
         |
     +---+---+
     |       |
    '+'     '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 вот так.

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

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

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

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

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

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