Професионална програма
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
g.kolev avatar g.kolev 82 Точки

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

0