Форум программистов, компьютерный форум CyberForum.ru

Построение бинарного дерева из строки - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.60
Monceber
1 / 1 / 0
Регистрация: 16.09.2011
Сообщений: 5
16.09.2011, 01:07     Построение бинарного дерева из строки #1
Доброго времени суток, уважаемые.

Хотел бы спросить у вас спросить совета относительно реализации следующей проблемы:
Задано арифметическо-логическое выражение (к примеру, (A+B-7*(3+C)>12)OR(B-A+19<7)), которое нужно перевести в дерево.
Собственно интересует меня не код программы, а возможные алгоритмы решения данной задачи - т.е. последовательность построения дерева и добавления узлов.

Сам я представляю решение примерно таким образом:
Есть функция Node* Somefunc(/*другие аргументы*/, Node* prevNode = nullptr), последством рекурсивного вызова которой и осуществляется добавление узлов к дереву.
Производится считывание строки слева направо, и, в зависимости от того, какой символ был встречен, выполняются разные условия. В следствии, если функция передается с заданным параметром prevNode, значит передаваемый узел будет левой ветвью следующего. Возвращаемое же значение функции становится правой ветвью.

Но такая реализация кажется мне слишком громоздкой и не оптимальной, поэтому если кто-то посоветует лучшее решение, буду очень благодарен.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.09.2011, 01:07     Построение бинарного дерева из строки
Посмотрите здесь:

Построение бинарного дерева из двумерного массива C++
Построение бинарного дерева C++
C++ Построение бинарного дерева на основе не бинарного
Построение бинарного дерева C++
C++ Вывод бинарного дерева на экран в виде "дерева"
C++ Код Хаффмана реализованный через построение бинарного дерева
C++ Построение бинарного дерева. Где ошибка?
Написать шаблон бинарного дерева с функцией распечатки дерева C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
16.09.2011, 01:53     Построение бинарного дерева из строки #2
Monceber, для начала поищите информацию по нисходящему рекурсивному парсингу. У Страуструпа в его книге "Программирование. Принципы и практика использования C++" о нём говорится (глава про разработку калькулятора), однако я не помню там информации о превращении всего этого в бинарное дерево. В любом случае, для начала будет полезно.
Monceber
1 / 1 / 0
Регистрация: 16.09.2011
Сообщений: 5
16.09.2011, 08:24  [ТС]     Построение бинарного дерева из строки #3
talis, да, именно принцип работы программы-калькулятора я и взял за основу алгоритма (правда читал я ее в Хортона, а не Страуструпа, не уверен та ли это программа - там производится разбиение всего выражения на операторы и операнды, верно?) и по логике этой программы я и пришел к тому решению, которое описал выше. Но результат получается неудовлетворительный, т.к. приходится делать слишком много проверок и такой алгоритм работает не со всякой строкой (к примеру, если взять строку 2+2+2+2+2, где приоритет все операций одинаковый, то дерево получится несбалансированным, поскольку узлы будут добавляться с левой его стороны).
Yandex
Объявления
16.09.2011, 08:24     Построение бинарного дерева из строки
Ответ Создать тему
Опции темы

Текущее время: 10:43. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru