Salutare,
Astăzi vom discuta despre un algoritm cât se poate de simplu pentru simplicarea unei căi din sistemul de fișiere Unix. Algoritmul folosește o stivă pentru a putea face acest lucru.
Sistemul de fișiere Unix permite definirea unor căi ca fiind un string cu următoarele proprietăți:
- Orice path începe cu "/".
- Oricare două directoare din path sunt separate prin "/".
- Este permisă următoarea construcție: "//", caz în care ne aflăm de fapt în același director.
- Este permisă următoarea construcție: "/./", caz în care ne aflăm tot în același director.
- Este permisă următoarea construcție: "/../", caz în care revenim la directorul părinte.
Descrierea problemei
Să se construiască un algoritm prin care să se simplifice un path și să dispară toate construcțiile de genul: "//", "/./" și "/../". În plus, se cere și o validare formală a path-ului.
Să spunem că avem următorul sistem de fișiere cu o structură arborescentă:
Example:
- Următoarea cale este considerată validă:
/home//mihai/./../alina. Forma ei simplificată va fi:/home/alina. - Următoarea cale este considerată validă:
/home/tmp/apps/chrome/.... Forma ei simplificată va fi:/home/tmp/apps/chrome/.... "..." va fi considerat tot un nume de folder și algoritmul nu va verifica dacă acest director există sau nu fizic pe disk. - Următoarea cale este considerată invalidă:
/home/../../alina. De ce? Pentru că directorul home are un bunic ci doar un părinte: "/".
Descrierea soluției problemei
Pentru a rezolva problema, vom folosi o stivă. Path-ul primit ca și input va fi impărțit în funcție de "/".
Astfel, path-ul /home//mihai/./../alina/ va deveni un string array, cu următoarele elemente: ["", "home", "", "mihai", ".", "..", "alina"]. Așa cum se poate observa, dimensiunea cestui string array este de 8 elemente.
Pasul următor al algoritmul este să itereze de la stânga la dreapta peste cele 8 elemente. Vorbim așadar de o complexitate liniară.
În momentul iterării, în funcție de valoarea elementului curent din array, vom efectua una din următoarele operații:
- Dacă șirul de caractere este empty = "", nu vom face nimic cu starea curentă a stivei.
- Dacă șirul de caractere este egal cu ".", la fel nu vom face nimic cu starea curentă a stivei - nu vom avansa cu parcurgerea sistemului de fișiere.
- Dacă șirul de caractere este egal cu "..", va trebui să scoatem un element din stivă și în acest caz, îl vom scoate pe cel recent adăugat.
- Dacă nu ne aflăm în niciuna din cazurile de mai sus, vom adăuga un nou element pe stivă.
Stiva inițială va fi goală.
Iată cum arată stiva la parcurgerea fiecărui element din array-ul de 8 elemente:
- Stiva va rămâne goală după parcurgerea primului element = "".
- Stiva după parcurgerea celui de-al doilea element = "home":
- Stiva după parcurgerea celui de-al treillea element = "":
- Stiva după parcurgerea celui de-al 4-lea element = "mihai":
- Stiva după parcurgerea celui de-al 5-lea element = ".":
- Stiva după parcurgerea celui de-al 6-lea element = "..":
- Stiva după parcurgerea celui de-al 7-lea element = "alina":
- Path-ul simplificat este:
/home/alina.
De ce calea /home/../../alina este considerată invalidă? Să facem un exercițiu de imaginare și să vedem câte elemente sunt în stivă după ce procesăm primul ".." din array. În principiu nu mai este niciun element în stivă. All good until now. Dar ce se întâmplă când trebuie să procesăm un alt ".."? Păi teoretic ar trebui să scoatem un element din stivă. Dar nu mai există niciun element disponibil. So, în acest moment putem să spunem că path-ul respectiv este clar invalid.
Las implementarea în Java la latitudinea cititorului. Totul este straight-forward. :) Happy coding!
