Как вычислить мат.выражение представленное в виде дерева?

Question

[McLightning]

struct Node {
Node A;
Node B;
float ValueDigit;
char ValueChar;
}

Изображение дерева

Answer 1

[Dmitrii]

Можно пройтись поиском в глубину (DFS) до последнего узла и дальше двигаясь в обратном направлении выполнить вычисления.
1. вначале мы находим самую нижнюю ноду, а она точно цифра (в противном случае смысла нет)
2. делаем шаг назад и выполняем вычисление
3. редактируем имеющуюся структуру "укорачивая" дерево (то есть вместо знака действия у нас теперь цифра)
4. делаем так пока не получим дерево состоящее только из корня, которое и будет решением.

Попробовал написать решение твоей задачки, код по ссылке
https://godbolt.org/z/PzWjYjvfz

Comments

[Dmitrii]

Нюанс только в том, чтобы учесть приоритеты (останется ли дерево прежним, если поменять сложение и умножение местами?)

[Станислав Макаров]

Dmitrii приоритеты нужно учитывать тогда, когда дерево строится. Это часть задачи разбора синтаксиса мат. выражения

[Dmitrii]

Станислав Макаров, я абсолютно согласен, но подумал вдруг это задание подразумевает проверку приоритетов и переписывание дерева, поэтому и спросил) (выглядит как учебная/тестовая задача, а в них бывает разное)

Answer 2

[Василий Банников]

Раз тут уже посчитаны приоритеты вычисления - просто рекурсивно проходишься по каждому узлу, вычисляя его.