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

С++ для начинающих

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

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

16.09.2011, 01:07. Просмотров 2030. Ответов 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
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Построение бинарного дерева из строки (C++):

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

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

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

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

Построение бинарного дерева из двумерного массива - C++
Стыдно, если честно, об этом просить, но &quot;возник стопор&quot; и путных идей не приходит. Суть задачи: Есть массив n*n состоящий из целых...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
talis
791 / 543 / 37
Регистрация: 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
Привет! Вот еще темы с ответами:

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

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

Написать шаблон бинарного дерева с функцией распечатки дерева - C++
Не понимаю, что от меня хотят. Дано такое задание: Написать шаблон бинарного дерева с функцией распечатки дерева *(+(d,e),c) в виде...

Создание бинарного дерева из бинарного файла - C++
struct Bin { string name; string city; int players; int score; }; void ReadFromBin(Point*&amp; Tree) { Bin q;


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

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

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