Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.77/13: Рейтинг темы: голосов - 13, средняя оценка - 4.77
Monceber
1 / 1 / 0
Регистрация: 16.09.2011
Сообщений: 5
#1

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

16.09.2011, 01:07. Просмотров 2349. Ответов 2
Метки нет (Все метки)

Доброго времени суток, уважаемые.

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

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

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

Построение бинарного дерева на основе не бинарного
В лабораторной работе есть такое задание: Создайте процедуру построения...

Построение бинарного дерева
Написать программу построения бинарного дерева с помощью связных структур и...

Построение бинарного дерева
Доброй ночи! Пятые сутки не могу разобрать реализацию алгоритма на С++ Console...

Построение бинарного дерева. Где ошибка?
Насколько понял, tree-&gt;left, tree-&gt;right указывает на NULL. Почему, не могу...

Построение бинарного дерева из двумерного массива
Стыдно, если честно, об этом просить, но &quot;возник стопор&quot; и путных идей не...

2
talis
793 / 545 / 61
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
16.09.2011, 01:53 #2
Monceber, для начала поищите информацию по нисходящему рекурсивному парсингу. У Страуструпа в его книге "Программирование. Принципы и практика использования C++" о нём говорится (глава про разработку калькулятора), однако я не помню там информации о превращении всего этого в бинарное дерево. В любом случае, для начала будет полезно.
1
Monceber
1 / 1 / 0
Регистрация: 16.09.2011
Сообщений: 5
16.09.2011, 08:24  [ТС] #3
talis, да, именно принцип работы программы-калькулятора я и взял за основу алгоритма (правда читал я ее в Хортона, а не Страуструпа, не уверен та ли это программа - там производится разбиение всего выражения на операторы и операнды, верно?) и по логике этой программы я и пришел к тому решению, которое описал выше. Но результат получается неудовлетворительный, т.к. приходится делать слишком много проверок и такой алгоритм работает не со всякой строкой (к примеру, если взять строку 2+2+2+2+2, где приоритет все операций одинаковый, то дерево получится несбалансированным, поскольку узлы будут добавляться с левой его стороны).
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.09.2011, 08:24

Код Хаффмана реализованный через построение бинарного дерева
Здравствуйте, есть код Хаффмана реализованный через построение бинарного...

Вычислить выражение, содержащееся в строке, с использованием бинарного дерева поиска (парсинг строки)
В символьной строке записано правильное арифметическое выражение, которое может...

Запись бинарного дерева в файл и восстановление из него этого дерева
Задача такая: есть бинарное дерево. Каждый элемент дерева содержит 3 указателя...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru