Problema Dir – OJI 2007, Clasa a 10-a

• Dificultate:
• Autor: Alin Burța
• Online: InfoArena, PbInfo

Rezumat

Se consideră un disc ce conține mai multe foldere și fișiere. Un folder poate conține atât fișiere, cât și alte foldere. Folderele sunt scrise cu majuscule, iar fișierele cu minuscule, însă ambele tipuri de nume pot conține și cifre arabe. Ni se dă un șir de caractere ce reprezintă structura fișierelor de pe discul respectiv. Un folder este codificat astfel: NUME_FOLDER(listăDeFoldereȘiFișiere), unde lista conține elementele folder-ului separate prin virgulă. Desigur, subfolderele respectă aceeași regulă.

De exemplu, string-ul FOLDER1(FOLDER2(),FOLDER3(FOLDER4(poveste,basm),basm)) îi corespunde pozei de mai jos:

Pentru structura de fișiere dată, ni se cere afișarea în ordine lexicografică a căilor tuturor fișierelor de pe disc, precum și numărul lor. Fiecare nume de folder trebuie urmat de caracterul backslash.

Soluție

Vom evalua expresia, reținând pe o stivă numele folderelor ce constituie calea curentă. Pentru fiecare nou fișier găsit, formăm un șir de caractere ce reprezintă calea lui, folosind conținutul stivei și numele fișierului. Adăugăm acest string într-un vector pe care la final îl vom sorta, pentru a-i putea afișa elementele în ordinea cerută.

Am ales să creez un struct Str pentru șirurile de caractere, ce conține doar un vector de tip char, și să supraîncarc operatorul <. Asta ca să pot sorta vectorul de șiruri la final. În rest, am aplicat o tehnică folosită și în problema Rețeta. Am ținut o copie a șirului str în aux, și am aplicat strtok pe copie, delimitând numele de fișiere și de foldere de restul codificării. Apoi, am parcurs șirul str ca la orice altă problemă de evaluare de expresii, și când am găsit un început de nume, am adăugat valoarea din aux pe stivă, trecând la următorul separator.

Sursă C++

#include <cstring>
#include <fstream>
#include <algorithm>

#define SMAX 1610

std::ifstream fin("dir.in");
std::ofstream fout("dir.out");

struct Str {
    char str[SMAX];
};

bool operator<(Str x, Str y) {
    return strcmp(x.str, y.str) < 0;
}

char str[SMAX];
char aux[SMAX];

// Vectorul cu căile de fișiere:
int nrSol;
Str sol[SMAX];

// Stiva:
int vf;
char st[SMAX][SMAX];

/// Funcția ce adaugă un nou fișier în sol
void add() {
    strcpy(sol[nrSol].str, st[1]);
    for (int i = 2; i <= vf; i++) {
        strcat(sol[nrSol].str, "\\");
        strcat(sol[nrSol].str, st[i]);
    }
    nrSol++;
}

int main() {
    int i;
    char *p;

    fin >> str;
    strcpy(aux, str);

    // Aplicăm strtok pe copie:
    p = strtok(aux, "(,)");
    while (p)
        p = strtok(NULL, "(,)");

    // Evaluăm expresia:
    for (p = str; *p; p++)
        if (*p == ')') {
            if ('a' <= st[vf][0] && st[vf][0] <= 'z') {
                // Folder-ul precedent a avut un fișier:
                add();
                vf--;
            }
            vf--;
        }
        else if (*p == ',') {
            if ('a' <= st[vf][0] && st[vf][0] <= 'z') {
                // Am avut un fișier înainte de virgulă:
                add();
                vf--;
            }
        }
        else if ('a' <= *p && *p <= 'z' || 'A' <= *p && *p <= 'Z') {
            // Am găsit un fișier sau folder nou:
            strcpy(st[++vf], aux + (p - str));
            p += strlen(st[vf]) - 1;
        }

    // Sortăm soluțiile:
    std::sort(sol, sol + nrSol);

    fout << nrSol << '\n';
    for (i = 0; i < nrSol; i++)
        fout << sol[i].str << '\n';
    return 0;
}

Dacă ai vreo nedumerire cu privire la problema Dir, lasă un comentariu și te voi ajuta