UŽDAVINIO "PAPRASČIAUSIAS KELIAS" SPRENDIMAS
(Koduotė utf-8)

Uždavinį "Paprasčiausias kelias" galima spręsti keliais būdais. Šiame dokumente aprašomi du. Tačiau pirmiausia reikia pastebėti, kad kelias bus trumpiausias (ir paprasčiausias) tada ir tik tada, kai jame neliks katalogų "." ir "..". Samprotavimas yra visai paprastas: jei yra bent vienas katalogas "." arba "..", tai jį nesunku panaikinti ir tuo pačiu sutrumpinti kelią. Kita vertus, jei nei vieno tokio katalogo kelyje nėra, tai nėra jokio kito būdo keliui sutrumpinti, nes visi likę katalogų vardai yra būtina informacija keliui failų sistemoje nurodyti.

Taigi belieka korektiškai panaikinti katalogus "." bei "..".

Pirmasis būdas išskaidyti duotąjį kelią į katalogų vardų seką (kitaip tariant, eilutę "sukarpyti" ties pasviro brūkšnio simboliais) ir tuomet "lipdyti" paprasčiausią kelią iš duotojo paeiliui nagrinėjant katalogų vardus. "Lipdomam" keliui saugoti naudojama duomenų struktūra stekas - tai yra elementų sąrašas, kuriame elementai tiek dedami į galą, tiek ir imami iš galo.
Nagrinėjant paeiliui katalogų vardus atliekami veiksmai:
- jei katalogas nėra nei ".", nei "..", jis įdedamas į steką
- jei katalogas yra ".." ir steke yra bent vienas katalogas, tai jis išimamas iš steko
- priešingu atveju, neatliekama nieko.

Šiuo būdu tarsi einama nurodytu keliu. Pabaigoje tereikia išspausdinti "nueitą" kelią - visą steko turinį, atskiriant pasviro brūkšnio simboliais, arba tiesiog vieną pasviro brūkšnio simbolį, jei stekas liko tuščias. Pavyzdinis sprendimas yra realizuotas C++ kalba faile "path.cpp".

Antrasis sprendimas yra naudojantis standartinėmis eilučių funkcijomis rasti ir iškirpti katalogus "." ir "..". Šis būdas yra pakankamai paprastas, tačiau turi kabliukų, už kurių nesunku užkliūti.
Norint rasti katalogus "." ir ".." simbolių eilutėje, svarbu nepamiršti, kad "." yra ".." dalis, o dar svarbiau - kad galimi katalogų vardai ".trash", "hmm..." ar "...". Katalogus "." ir ".." teisingai rasime, ieškodami fragmentų "/./" bei "/../", išskyrus vieną atvejį: jei kelias baigiasi tokiu katalogu, tai antrojo brūkšnio nebus (pavyzdžiui, "/."). Paprasčiausia šią problemą spręsti prie kelio pridedant papildomą pasviro brūkšnio simbolį, o vėliau, jei reikia, nepamiršti jo nuimti. (Uždavinį sprendžiant Paskaliu, reikia turėti omenyje, kad standartinis string tipas turi ribotą 255 simbolių ilgį, taigi kad sutalpinti visą kelią (maks. 255 simboliai) ir dar vieną simbolį, reikia naudoti ansistring tipą arba kitaip išsisukti šioje situacijoje.)
Fragmentą "/./" turime pakeisti į "/", o fragmentą "*/../" (čia * yra katalogo vardas, arba tučia eilutė) turime tiesiog iškirpti. Būtina "/./" pakeitimus atlikti pirmiau, kad visi likę katalogai būtų ".." arba tikri. Priešingu atveju, turėtume problemų su situacijomis "/a/./../" bei panašiomis. "/./" pakeitimus galima atlikti bet kokia tvarka, nieko nesugadinsime, nes taškas reiškia tiesiog likimą tame pačiame kataloge.
"*/../" iškirpimus svarbu atlikti visuomet randant patį kairiausią tokį fragmentą. Priešingu atveju turėtume problemų su situacijomis "/a/../../" bei panašiomis. Standartinės eilučių funkcijos paiešką eilutėje atlieka iš kairės į dešinę, taigi galima jomis naudotis.
Pavyzdinis sprendimas yra realizuotas Paskalio kalba faile "path.pas".

TESTAI

Numeris Komentaras
01      Kelią sudaro tik šakninis simbolis
02      Elementarus "." panaudojimas
03      Elementarus ".." panaudojimas
04      "." ir ".." naudojami kartu, bet ne greta
05      "." ir ".." naudojami kartu ir greta
06      Kelią sudaro vien tik "." ir ".." katalogai
07      Kelią sudaro vienas maksimalaus ilgio katalogas
08      Kelias labai gilus (labai daug trumpų katalogų) ir vienas "." katalogas
09      Ilgas kelias su įvairiais "." ir ".." panaudojimais
10      Ilgas kelias su įvairiais "." ir ".." panaudojimais. Katalogų įvairiai panaudoti taško simboliai.