Перевод инфиксной записи выражения в бинарное дерево. Язык- С++.

[Artemy]

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

[eoln]

Один из вариантов алгоритма
Например, есть 2*(2 - 3)/3 - (4*4/2 - 4)

Если скобки стоят на первой и последней позициях, то их убираем. Далее ищем первый подходящий знак + или - вне скобок, он будет вершиной дерева (если их нет, то первый попавшийся вне скобок знак * или /)
Создаём новые подстроки (для формирования узлов) из правой и левой частей частей относительно первого найденного подходящего знака.
В данном случае вершиной будет второй знак -, а левые и правые части соответственно 2*(2 - 3)/3 и (4*4/2 - 4)

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

Всё это дело можно оформить в виде рекурсии. Вычисление также можно сделать рекурсивной функцией.

[ura_111]

Я точно не уверен, но может быть так:





Пиши, что думаешь.

[eoln]

В дереве достаточно 2-х указателей *лево, *право (на левую и правую часть), информационного поля chislo и информационного поля тип_операции.
Например, если операции дальше нет, то тип_операции = 0, если знак минус - тип_операции = 1, если плюс - тип_операции = 2 и т.д.