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

[Sam Dark]

Нужно решить вот такую задачку:

Построить дерево арифметического выражения, нарисовать дерево и посчитать выражене.

Вид дерева для (A+B)*(C+D)-E:

                           -
                          / \
                         /   \
                        *     E
                       / \
                      /   \
                     /     \
                    /       \
                   +         +
                  / \       / \
                 /   \     /   \
                A     B   C     D

Забрёл сюда:
http://algolist.manual.ru/syntax/revpn.php

Решил строить дерево из польской записи. (Запись получил. Delphi.)
Как реализовать?

Спасибо.

[Trotil]

А дерево нужно строить в текстовом режиме или можно графическими библиотеками?
В любом случае,можно написать некоторую рекурсивную процедуру (пример для графичекого отображения), основные шаги которой таковы:
x,y - координаты дерева
N - номер просматриваемого символа - перменная должна быть глобальной или введена в выражении польской записи спец символом или иметь там фиксированное место, пусть это будет первый символ - вариантов масса на самом деле

char * tree(char* str, int x, int у)
{
1)Отрисовываем знак текущей операции (N-тый символ в выражении) в точке (x,y)
2) Отрисовываем две ветви, определяем координаты концов ветвей
3) просматриваем (N--) символ:
если это "знак операции", то tree(str, текущее X, текущее Y, текущее N)
иначе отрисовываем этот символ
4) просматриваем (N--) символ:
если это "знак операции", то tree(str, текущее X, текущее Y, текущее N)
иначе отрисовываем этот символ
}

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

[Trotil]

Решил подкрепить свою идею надлядным примером работы алгоритма.
Возьмем, например, такое выражение: "CD*E+AB+*FG*-#" (решетка - символ-указатель на просматриваемый элемент)

1) Вход в функцию: рисуем "-" и ветви:

                            -
                           / \
                          /   \
                         /     \
                        /       \

2) Сдвигаем указатель "#" и обнаруживаем на месте первого аргумента "знак операции" "*". Запускаем ту же функцию, но уже строкой: "CD*E+AB+*FG*#-".
3) Отрисовываем "*" и ветви:

                            -
                           / \
                          /   \
                         /     \
                        /       \
                                 *      
                                 / \
                                /   \

Отрисовываем аргументы F,G. Знаков операции не обнаружено, поэтому новая функция не запускается, данная функция завершает работу и передается управление самой первой функции. Дерево имеет вид:

                            -
                           / \
                          /   \
                         /     \
                        /       \
                                 *      
                                 / \
                                /   \
                               F     G

В первой функции начинает выполняться инструкция 4: но на месте аргумента стоит знак операции "умножение".
Опять вызывается функция tree со строкой "CD*E+AB+*#FG*-" (при каждой отрисовке символа решетка сдвигается на один символ влево)

И так далее. В конце получаем дерево след. вида:

                            -
                           / \
                          /   \
                         /     \
                        /       \
                        *        *      
                       / \      / \
                      /   \    /   \
                     /     \   F    G 
                    /       \
                   +         +
                  / \       / \
                 /   \     /   \
                A     B   *     E
                         / \
                        /   \
                       С     D

[Sam Dark]

Спасибо. Попробую реализовать такой алгоритм.