2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Построение дерева разбора
Сообщение09.04.2013, 23:16 
Доброго времени суток, столкнулся с сабжевой проблемой. Есть выражение состоящее из +-*/() и переменных. Требуется построить дерево разбора.

(Оффтоп)

Написал на коленке свой алгоритм(если интересно есть рабочий говнокод на C++):

1 Создаю массив очередей, помещаю индексы операторов в разные очереди в зависимости от приоритета, в первой очереди операторы которые выполнятся последними и будут на вершине дерева
(например для выражения a+b*c/(d-e)
в 1 очереди +
в 2 */
в 3 -
написал в примере операторы, а не индексы, чтобы было понятней)

2 Беру оператор с меньшим приоритетом, теперь у меня есть две части, то что левее этого оператора, и то, что правее

3 Выполняю рекурсивно пункт 2, для обоих частей, указываю в каком диапазоне индексов находится эта часть

Погуглил и утонул в количестве информации, мне не хочется особо сильно вникать в теорию формальных грамматик и т.д. Какой алгоритм лучше использовать для моей задачи?

 
 
 
 Re: Построение дерева дерева разбора
Сообщение09.04.2013, 23:30 
Аватара пользователя
http://ru.wikipedia.org/wiki/Алгоритм_сортировочной_станции

 
 
 
 Re: Построение дерева разбора
Сообщение10.04.2013, 02:05 
А в чём проблема, не понял. У вас есть алгоритм разбора; вникать не буду, но, полагаю, он работает. Зачем вам ещё? В нём чего-то не хватает?

 
 
 
 Re: Построение дерева разбора
Сообщение10.04.2013, 22:14 
Pavia, я получил обратную польскую запись и построил по ней дерево с помощью рекурсии, но там написано:
Цитата:
Может быть использован для получения вывода в виде обратной польской нотации или в виде абстрактного синтаксического дерева.
я правильно понимаю, что переводить в польскую запись не обязательно, а можно сразу построить дерево с помощью этого алгоритма? если да то что в нем надо изменить?
iifat, у меня частенько так: пишу велосипеды, а потом переписываю по нормальному :-)

 
 
 
 Re: Построение дерева разбора
Сообщение10.04.2013, 22:31 
Можно и сразу дерево, и без рекурсии, и без обратной польской и вообще как угодно topic68959.html

 
 
 
 Re: Построение дерева разбора
Сообщение11.04.2013, 01:12 
pavlov_ivan в сообщении #708373 писал(а):
iifat, у меня частенько так: пишу велосипеды, а потом переписываю по нормальному

Я так и понял. Занятие почтенное и весьма полезное, именно поэтому я спрашивал о другом: таки ж чем вас не устроило получившееся средство передвижения?
На всякий случай: обратная польская запись -- это и есть дерево разбора. Да, оно обойдено из глубины вверх и вытянуто в одну цепочку -- деревом оно от того быть не перестало. Как, кстати говоря, и прямая польская, и обычная инфиксная записи -- вот только в последней надо все скобки расставить.

 
 
 
 Re: Построение дерева разбора
Сообщение11.04.2013, 08:18 
Аватара пользователя
iifat
Польская запись не является деревом, так как в ней не определены ни корень ни ветви ни узлы, ни операции обхода. Но польская запись легко превращается в дерево.


pavlov_ivan
Советую вначале решить задачку по проще. Задача заключается в проверки правильности расположения скобок трёх видов "()[]{}"
Например, "({()[]})"— правильная структура, а "({()[)}]" — неправильная.
Описание задачи.
http://acm.mipt.ru/twiki/bin/view/Cintr ... Structures

Когда вы решите то с легкостью разберётесь в алгоритме перевода из инфиксной нотации в дерево.
Цитата:
я правильно понимаю, что переводить в польскую запись не обязательно, а можно сразу построить дерево с помощью этого алгоритма? если да то что в нем надо изменить?

Когда из стека вынимаешь, то в этот момент и формируешь дерево.

 
 
 
 Re: Построение дерева разбора
Сообщение11.04.2013, 08:47 
Pavia в сообщении #708476 писал(а):
Польская запись не является деревом, так как в ней не определены ни корень ни ветви ни узлы
Ага. Вычислить значение -- легко! А определить ветки -- ну никак.
Pavia в сообщении #708476 писал(а):
ни операции обхода

А что, по-вашему, делает вычислитель? Он что, не обходит дерево из глубины наверх, проставляя в вершинах значения?

 
 
 
 Re: Построение дерева разбора
Сообщение11.04.2013, 15:15 
Дерево вместо обратной польской записи получить просто: сначала заметим, что можно вычислять обратную польскую запись не в число, а в дерево выражения, а потом заметим, что можно не генерировать всю запись, а обойтись последовательно получаемыми элементами (т. к. при её вычислении требуется один раз посмотреть на каждый её последовательный элемент, никуда не возвращаясь).

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

 
 
 
 Re: Построение дерева разбора
Сообщение11.04.2013, 15:20 
Цитата:
http://acm.mipt.ru/twiki/bin/view/Cintr ... Structures
Да, я такую знаю
arseniiv, Pavia, для того, чтобы сразу строить дерево мне нужно, чтобы первый оператор который я выну из стека имел приобретет меньше, чем у всех остальных, но я могу вынуть из стека только тот оператор, приоритет которого меньше приоритета предыдущих (об остальных я ничего не знаю т.к. до них не дошел), получается мне все равно нужна еще очередь или стек(в которых будет польская запись). Если я сразу начину строить дерево, то придется строить его не от вершины, а от листа.
_Ivana, четно пытался найти дерево, но ничего не понял в исходниках :roll:
iifat, дерево больше подходит, там узлах можно хранить дополнительную информацию

 
 
 
 Re: Построение дерева разбора
Сообщение11.04.2013, 15:30 
pavlov_ivan в сообщении #708627 писал(а):
arseniiv, Pavia, для того, чтобы сразу строить дерево мне нужно, чтобы первый оператор который я выну из стека имел приобретет меньше, чем у всех остальных, но я могу вынуть из стека только тот оператор, приоритет которого меньше приоритета предыдущих (об остальных я ничего не знаю т.к. до них не дошел), получается мне все равно нужна еще очередь или стек(в которых будет польская запись). Если я сразу начину строить дерево, то придется строить его не от вершины, а от листа.
Какая разница, как строить дерево? У вас будет стек, доставшийся в наследство от алгоритма вычисления обратной польской записи. Храните в этом стеке поддеревья (а не числа, как при «обычном» вычислении). Вместо вычисления суммы, когда приходит +, «вычисляйте» соответствующее дерево.

По-моему, обобщение совершенно прозрачное. :roll:

 
 
 
 Re: Построение дерева разбора
Сообщение11.04.2013, 15:55 
Посмотрел ваш алгоритм. Ну что ж, настало время слегка разобраться, как делаются подобные велосипеды промышленно ;) Алгоритм по ссылке, которую вам давали -- самый простой из таековых, специально заточенный под выражения (не знаю, нужны ли вам функции; если нет, то он ещё и упрощается).
Для построения дерева в связанном виде (хотя я таки настаиваю, что обратная польская запись -- вполне себе дерево разбора) можно, например, слегка модифицировать вывод: там где в оригинале перенос в очередь вывода числа либо переменной -- заносим в стек вершину дерева (лист), соответствующиую числу либо переменной; там где в оригинале перенос в очередь вывода оператора либо функции, извлекаем из стека соответствующее количество деревьев, строим новое, в вершину -- оператор либо функцию, потомками подвешиваем извлечённые и суём новое дерево обратно в стек.
В конце концов в стеке должно остаться ровно одно дерево -- дерево разбора.

 
 
 
 Re: Построение дерева разбора
Сообщение12.04.2013, 14:57 
Всем спасибо, осилил таки :D

 
 
 
 Re: Построение дерева разбора
Сообщение12.04.2013, 23:14 
pavlov_ivan в сообщении #709022 писал(а):
Всем спасибо, осилил таки :D

Поделишься кодом?)

 
 
 
 Re: Построение дерева разбора
Сообщение14.04.2013, 21:21 
12301230 в сообщении #709324 писал(а):
pavlov_ivan в сообщении #709022 писал(а):
Всем спасибо, осилил таки :D

Поделишься кодом?)

Вот та часть кода, которая строит дерево

(Оффтоп)

Код:
void hang_up(stack <char>& st1, stack <node*>& st2)
{
   node* p;
   p=new_node(st1.top(),NULL,NULL); st1.pop();
   p->l=st2.top(); st2.pop();
   p->r=st2.top(); st2.pop();
   st2.push(p);
}

node* expr_to_tree(char *expr)
{
   stack <char> st1;
   stack <node*> st2;
   int i, len;
   node* p;
   len=strlen(expr);
   for(i=0;i<len;++i)         
   {
      if(expr[i]==')')             
      {
         while(st1.top()!='(')
         {
            hang_up(st1,st2);
         }
         st1.pop();
      }
      if(is_var(expr[i]))
      {
         p=new_node(expr[i],NULL,NULL);
         st2.push(p);
      }
      if(expr[i]=='(')                         
         st1.push(expr[i]);           
      if(is_oprt(expr[i]))
      {
         while(!st1.empty()&&(oprt_prior(st1.top())>=oprt_prior(expr[i])))
         {
            hang_up(st1,st2);
         }
         st1.push(expr[i]);           
      }                                   
   }
   while(!st1.empty())
   {                     
      hang_up(st1,st2);
   }
   return st2.top();
}

 
 
 [ Сообщений: 25 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group