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

[pavlov_ivan]

Доброго времени суток, столкнулся с сабжевой проблемой. Есть выражение состоящее из +-*/() и переменных. Требуется построить дерево разбора.

(Оффтоп)

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

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

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

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

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

[Pavia]

http://ru.wikipedia.org/wiki/Алгоритм_сортировочной_станции

[iifat]

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

[pavlov_ivan]

Pavia, я получил обратную польскую запись и построил по ней дерево с помощью рекурсии, но там написано:

Цитата:

Может быть использован для получения вывода в виде обратной польской нотации или в виде абстрактного синтаксического дерева.

я правильно понимаю, что переводить в польскую запись не обязательно, а можно сразу построить дерево с помощью этого алгоритма? если да то что в нем надо изменить?
iifat, у меня частенько так: пишу велосипеды, а потом переписываю по нормальному

[_Ivana]

Можно и сразу дерево, и без рекурсии, и без обратной польской и вообще как угодно topic68959.html

[iifat]

pavlov_ivan в сообщении #708373 писал(а):

iifat, у меня частенько так: пишу велосипеды, а потом переписываю по нормальному

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

[Pavia]

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


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

Когда вы решите то с легкостью разберётесь в алгоритме перевода из инфиксной нотации в дерево.

Цитата:

я правильно понимаю, что переводить в польскую запись не обязательно, а можно сразу построить дерево с помощью этого алгоритма? если да то что в нем надо изменить?

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

[iifat]

Pavia в сообщении #708476 писал(а):

Польская запись не является деревом, так как в ней не определены ни корень ни ветви ни узлы

Ага. Вычислить значение -- легко! А определить ветки -- ну никак.

Pavia в сообщении #708476 писал(а):

ни операции обхода

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

[arseniiv]

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

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

[pavlov_ivan]

Цитата:

http://acm.mipt.ru/twiki/bin/view/Cintr ... Structures

Да, я такую знаю
arseniiv, Pavia, для того, чтобы сразу строить дерево мне нужно, чтобы первый оператор который я выну из стека имел приобретет меньше, чем у всех остальных, но я могу вынуть из стека только тот оператор, приоритет которого меньше приоритета предыдущих (об остальных я ничего не знаю т.к. до них не дошел), получается мне все равно нужна еще очередь или стек(в которых будет польская запись). Если я сразу начину строить дерево, то придется строить его не от вершины, а от листа.
_Ivana, четно пытался найти дерево, но ничего не понял в исходниках
iifat, дерево больше подходит, там узлах можно хранить дополнительную информацию

[arseniiv]

pavlov_ivan в сообщении #708627 писал(а):

arseniiv, Pavia, для того, чтобы сразу строить дерево мне нужно, чтобы первый оператор который я выну из стека имел приобретет меньше, чем у всех остальных, но я могу вынуть из стека только тот оператор, приоритет которого меньше приоритета предыдущих (об остальных я ничего не знаю т.к. до них не дошел), получается мне все равно нужна еще очередь или стек(в которых будет польская запись). Если я сразу начину строить дерево, то придется строить его не от вершины, а от листа.

Какая разница, как строить дерево? У вас будет стек, доставшийся в наследство от алгоритма вычисления обратной польской записи. Храните в этом стеке поддеревья (а не числа, как при «обычном» вычислении). Вместо вычисления суммы, когда приходит +, «вычисляйте» соответствующее дерево.

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

[iifat]

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

[pavlov_ivan]

Всем спасибо, осилил таки

[12301230]

pavlov_ivan в сообщении #709022 писал(а):

Всем спасибо, осилил таки

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

[pavlov_ivan]

12301230 в сообщении #709324 писал(а):

pavlov_ivan в сообщении #709022 писал(а):

Всем спасибо, осилил таки

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

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

(Оффтоп)

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();
}