Loading...
djc_bg2015 avatar 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, и на края смятам и печатам.

 

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

 

5
Структури от данни и алгоритми 29/02/2016 15:18:56
HPetrov avatar HPetrov 822 Точки

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

0
djc_bg2015 avatar djc_bg2015 923 Точки

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

 

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

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

 

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

0
28/02/2016 22:42:28
djc_bg2015 avatar djc_bg2015 923 Точки

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

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

1
29/02/2016 08:37:06
a_rusenov avatar a_rusenov 1103 Точки

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

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

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

2
29/02/2016 14:11:55
djc_bg2015 avatar djc_bg2015 923 Точки

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

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

Поздрави

0
moholovka avatar moholovka 169 Точки

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

1
Innos avatar Innos 419 Точки

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

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

2
g.kolev avatar g.kolev 82 Точки

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

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.