[Homework] Trees and Tree-Like Data Structures - Февруари 2016

djc_bg2015 923 Точки

[Homework] Trees and Tree-Like Data Structures - Февруари 2016

Здравейте колеги,
ето как видях аз трите задачи от домашното:

https://github.com/vdonchev/Trees-ndTreeLikeDataStructures-Homework

01. Първа задача стана малко по - дълга като код, тъй като за различните под точки, направих различни методи.
Първите 3 точки от условието са 3 ламбди. За 4та пускам един DFS от корена и търся node който е най - дълбоко. След като съм го намерил печатам като тръгвам от него на горе докато не стигна до корена. За 4та точка правя абсолютно същото, DFS и сумирам докато не стигна до сумата, която се търси. След като съм открил нода в който сумата става търсената, печатам пак по същия начин.
Относно последната 5та под точка, направих така че всеки node (дърво) да знае сумата на под дървото на което той е корен. По този начин, така пускам един DFS и проверявам за всеки node каква е сумата на под дървото и ако е правилната - печатам (пак с DFS).

02. По задача две няма какво да се каже, ползвам два помощни класа File и Folder, всеки Folder си знае размера, така че останалото е елементарно.

03. По трета задача бая пописах на хартия докато схвана как работи обратния полски запис и как точно да превърна израз в такъв. За входа написах един regex чаршаф който да раздели операторите от операндите при входа, за да няма значение как точно е подават (с или без разстояния). След това използвайки shunting yard алгоритъма обръщам израза в reversed polish notation, и на края смятам и печатам.

Ако някой има коментари, ще се радвам да ги прочета.
Поздрави!

Тагове:

27/02/2016 18:42:52 Структури от данни и алгоритми 29/02/2016 15:18:56

HPetrov 822 Точки

Можеш ли на 3-та задача малко по-подробно да обясниш какво правиш точно с тоя regex? Само зачистваш празните места (колкото и на брой да са) ли?

28/02/2016 22:00:48

djc_bg2015 923 Точки

Ами де факто регекса минава по стринга и търси:

^-?\d+\.?\d* (число с/без десетична запетая и с/без минус което се намира в началото на стринга)
или
(?<=[-+\\*% ])-?\d+\.?\d* (число с/без десетична запетая и с/без минус което е предшествано от един от тези символи: -+\\*% )
или
[\/\+\*\-\/\%] (операторите + "(" и ")")
или
\d+\.?\d* (число с/без десетична запетая)

и ако открие го замества със същото но + 1 спейс от пред и отзад:
" $0 "

Така се получават повече от един спейс разстояние м/у опеарторите и операндите, но при сплита ги засичиствам.

28/02/2016 22:39:50 28/02/2016 22:42:28

djc_bg2015 923 Точки

По скъсих малко регекса, и мисля, че пак работи коректно:

((?<=[\-\+\/\*\%\(\)\= ])|(?<=^))\-?\d+\.?(?:\d+)?|[\(\)]

29/02/2016 08:34:34 29/02/2016 08:37:06

a_rusenov 1103 Точки

На първа задача говориш всъщност за DFS (depth-first search), понеже винаги обхождаш в дълбочина и едва когато няма повече накъде, се връщаш назад по дървото (FindAllPathsWithSum, FindAllSubTreesOfSum). За BFS бихме говорили, ако обхождаше първо децата на текущия, после децата на децата и .т.н. (като вълна), ползвайки опашка.

Като оставим терминологията, решението е супер :). Като възможна оптимизация виж дали не можеш да добавиш още едно дъно на рекурсията в FindAllPathsWithSum и FindAllSubTreesOfSum при определена достигната сума.

Относно Shunting Yard алгоритъма, може да си оптимизираш switch-овете с един речник (оператор -> предимство).

29/02/2016 14:11:02 29/02/2016 14:11:55

djc_bg2015 923 Точки

Ох, разбира се че говоря за depth first search :D

Не е ясно защо съм написал BFS и то толкова мн пъти :D. Благодаря ти за съветите, ще добавя оптимизациите към кода :)

Поздрави

29/02/2016 15:12:52

moholovka 169 Точки

Решение на първа без допълнителни класове само с речник и два хеш сета (единият даже е излишен ма се сетих късно).

29/02/2016 14:57:01

Innos 419 Точки

Поизмъчих се и аз на 3та, докато най-накрая реших да ползвам регекс и аз. Има някакви интересни случаи, но може би ми е най-интересно дали всичките оператори могат да се представят със някакво ляво асоцииране и просто различен precedence.

Ето и какво съм забъркал и аз.

03/03/2016 01:50:41

g.kolev 82 Точки

Последната задача определено беше от интересните. Поиграх си днес и я докарах да работи с основните аритметически операции. Има случай, обаче, при които не успях да измисля работещо решение. Такъв случай е "3*5-22". Написано по този начин без интервали не може да се сети, че искам да извадя 22 от резултата на умножението и го третира като -22, което е проблем при преобразуването към Reversed polish notation. С интервали на правилните места всичко си заспива.
Ето го моето решение.
Поздрави. :)

06/03/2016 21:09:00