и?

жесть. уже можно не делать. фирма явно странная

Наверное у них задача есть похожая

Наверно просто надо чтобы человек _сам_ парсер написал, а не использовал что-то вроде lex+bison   

ну да
во-первых STL уже часть стандартной библиотеки
во-вторых boost::spirit это покруче чем "lex+bison":)

Эта задача уже лет -цать как решается make.

Указан Буст, в Бусте есть Spirit, для данной задачи не хуже упомянутых тулз.

Так что максимальное внимание последним шести строкам 

Вся сложность в предобработке файла, все остальное сделать в принципе легко...
предлагаю такую предобработку:

1) Для каждого имени запоминаем в каких строках оно есть, и в качестве кого (родителя\ребенка)

итого у нас формируется массив структур - по структуре на имя

2) Если одно имя - является сыном нескольких отцов - выводим ошибку

Пункты 3) - 4) выполняем пока не конец файла

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

4) Все такие (не упоминающиеся)  имена добавляем в качестве детей к своим родителям (родители ищутся среди выделенных строк, если не находятся - это имя без родителей) и выделяем эти строки.

5) Выводим дерево на экран.... GAME OVER


P.S: Классный тест... еще такие попадутся - пиши обязательно!!!!

P.P.S: Народ, видимо вам предлагали решить задачу а не обсуждать фирму         

Этот тест очень хорошо проверяет наличие работающего мозга.... а библиотеки в общем то не помогут здесь ИМХО.

Это сообщение отредактировал(а) Alexey_2007 - 18.1.2007, 00:13

Интересно, надо будет почитать   

ЗЫ

Это имхо не ошибка, просто тогда выйдет не дерево зависимостей, а граф:


Это сообщение отредактировал(а) nickless - 18.1.2007, 00:28

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

codelord, а сроки? У меня висит аналогичное задание, только за клаву я сяду не раньше сдачи сессии) 19го - 21 го намереваюсь кончить...если еще надо будет - скину)

Это сообщение отредактировал(а) KpoHyc - 18.1.2007, 00:50

 
да мне не надо, лучше здесь, любопытно будет посмотреть.

Это сообщение отредактировал(а) codelord - 18.1.2007, 00:55

codelord, Я вроде написал логику на форуме.... если что не понятно - спрашивай...

nickless, просто я так понял, что возможно только дерево.. ну если возможен граф - убрать это условие и всё


Это сообщение отредактировал(а) Alexey_2007 - 18.1.2007, 00:58

вы шутите штоль  вы лучше для себя ее решите. для меня не надо. 
проблемы начнуться когда начнешь свою логику применять.

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

Это сообщение отредактировал(а) codelord - 18.1.2007, 01:06

Ок просто не понял тогда

Если судить по примеру вывода после разбора - то все-таки там дерево, а не граф. Этот вопрос принципиальный с точки зрения вывода: показанный пример выводит дерево. А как выводить граф?

Связный граф без циклов и есть дерево.
Если есть циклы — надо сообщить об этом без вывода зависимостей, я так понял.

В примере nickless'а выше[A->{B C}->D на языке dot]  циклических зависимостей как раз и нет. Потому как D зависит от B и C, B зависит от A и C зависит от A. и других зависимостей нет.
нет цикла. граф здесь ориентированный, и это надо учитывать.
я безсовестно заменил в примере графа длинные названия ItemN... на A...

Добавлено @ 17:43 
Кстати, если под "выводом зависимостей на экран" подразуметь (подобно tsort(1)) 

и забить на красивые отступы, то эта самая топологическая сортировка как раз даст искомый результат, то у nickless'овского графа A->{B C}->D будет два валидных выхода:

и




Это сообщение отредактировал(а) Mayk - 18.1.2007, 17:46

Честно говоря, мне не видится эта задача слишком сложной с точки зрения создания самой структуры зависимостей.

Но пост Maykа как раз о той проблеме, которую я вижу: как это правильно вывести, если один потомок зависит от двух предков сразу? Или данная ситуация считается ошибочной? Если немного расширить исходные данные:
A B C D
B E F
C E F

То как это должно быть выведено?
A
 B
  E <--- Т.е. по два раза вывести? Или это ошибочные данные
  F <---
 C
  E <---
  F <---
 D

 Или надо так вывести (полный бред по-моему)
A
 B C
  E F

Не совсем понятны условия.

Если это обычное дерево - то не намного сложнее дерева подкаталогов получится 

Чтоб выполнить эти пункты логику программы, думаю, надо основвывать на паттерне "Composite" (Компоновшик) (см. книгу четырёх "Design Patterns. Elements of Reusable Object-Oriented Software.", есть на русском). Это не только прояснит логику, но и к тому же сразу скажет проверющему о хорошей квалификации программиста. Было бы время, я бы с удовольствием наваял решение. Хорошая задачка 

Дело не в написании парсера... Файл читается вполне стандартными средствами - оператором >> в строковые переменные.
Дело именно в логике...
Но логика тож не сильно сложная...
Так как скорость в качестве критерия не фигурирует (видимо не случайно), то нужно использовать стандартный список list из STL
list<string> children - это список детей...
struct element
{ string родитель;
   list<string> children;
}
list<element> tree; // фактически список-списков...
После прочтения файла он просто выводится на экран в цикле...


Для отслеживания циклических связей досточно проверять каждого дитятю на совпадение с родителем...
Алгоритм скорости вроде O(n^2)

codelord, 
Готовь тесты, чтобы убедиться в работоспособности =) Мож найдется время вечерком - напишу чего-нить.

Добавлено @ 19:28 
Так действительно интересно, сколько давалось на эту задачку времени?

Блин, времени вообще выделить не могу на это дело. Сейчас на работе полный аврал, плюс диплом доделывать надо. Единственное сложное и интересное место в этой задаче - это сортировка частично упорядоченного множества (упорядоченность заключается в правилах "кто чей родитель"). 
Ее алгоритм мы в универе давно еще проходили. Могу быстренько накидать, если нужно.

imho это замыкание множества атрибутов над множеством функциональных зависимостей, алгоритм из области реляционных баз данных.



к примеру имеем множество функциональных зависимостей:
A->D
AB->E
BF->E
CD->F
E->C

находим замыкание для множества атрибутов:
AE

Получаем:
{AE, AEDC, AEDCF}

Вроде так, если ничего не напутал.

codelord, где-то валяются исходники, но к сожалению на Delphi. если нужно - стучи в ПМ.

p.s.: imho странноватое тестовое задание. std::set + рутина, особые знания языка или ООП  такое задание не покажет, зато напрягает большое кол-во требований по интерфейсу(в какой строке ошибка и т.п., требование к возможности реутилизации кода). imho надо быть осторожней с этим работодателем. 

Если используется стандартные контейнеры, то STL уже имеет нужные сортировки... Нужно просто использовать...