Wielopoziomowa Lista Liczb Całkowitych

Zadanie z kursu ANSI C brzmiało:

Wielopoziomową Listę Liczb Całkowitych (w skrócie WLLC) definiujemy jako skończony (w tym także pusty) ciąg, którego elementami są liczby całkowite lub WLLC. Jeśli lista zawiera tylko liczby to nazywamy ją jednopoziomową. Przykłady L1 = [3,1,5]; L2 = [2,[4,7],[]]; L3 = [[[3],[5,8],2],[1,5]]. Lista L1 jest jednopoziomowa. Zdefiniować moduł WLLC (tzn. podać zawartość plików wllc.c oraz wllc.h), w którym:
- Zdefiniowana jest funkcja WLLC merge(WLLC l1, WLLC l2), która zwraca listę powstałą z dołączenia listy l2 na końcu listy l1. Na przykład dołączenie listy L1 na końcu listy L2 powinno stworzyć listę [2,[4,7],[],3,1,5].
- Zdefiniowana jest funkcja WLLC flat(WLLC li), która tworzy nową listę jednopoziomową zawierającą wszystkie liczby z listy li z zachowaniem ich kolejności. Na przykład wywołanie flat(L3) powinno zwrócić listę [3,5,8,2,1,5].

Ja na tym kolokwium podszedłem do tego zadania bardzo rutynowo i stworzyłem strukturę, która wyglądała mniej więcej tak:

struct WLLCnode
{
  bool  isWLLC;    // True jeśli element jest listą WLLC
  int   intvalue;  // Wartość liczbowa
  WLLC* WLLCvalue; // Wartość listowa
  WLLC* next;      // Wskaźnik na następny element
};
typedef WLLCnode* WLLC;

Po czym występowały definicje funkcji. Trochę się zamotałem z tymi wskaźnikami,

"Dać programiście wskaźniki to tak jakby dać małpie karabin maszynowy" Piotr Chrząstowski-Wachtel

pokreśliłem pół kartki ale ostatecznie coś wyszło i o dziwo okazało się poprawne. Nie mam zamiaru odtwarzać tego rozwiązania, ale wierzcie mi - było straszne :D. Natomiast Maciek zaczął to zadanie tak:

typedef char* WLLC;

i wszystkie funkcje pisze się miło i przyjemnie. Bardzo spodobało mi się to rozwiązanie. Z moją pomocą udało się zmniejszyć złożoność obu funkcji do liniowych i zmniejszyć rozmiar tych funkcji do kilku linijek.

Pierwsza funkcja jest bardzo prosta, aż niema co w niej opisywać. Rezerwujemy pamięć, kopiujemy pierwszą listę, kopiujemy drugą listę, wstawiamy przecinek w odpowiednie miejsce. Osobno rozważamy przypadki gdy lista jest pusta.

WLLC merge(WLLC a, WLLC b)
{
  int lena = strlen(a);
  int lenb = strlen(b);
  WLLC answer = malloc((lena + lenb) * sizeof(char));
  
  // Jeśli lista a jest pusta - zwróć listę b
  if (lena == 2)
    return strcpy(answer, b);

  // Analogicznie
  if (lenb == 2)
    return strcpy(answer, a);
  
  strcpy(answer, a);
  strcpy(answer + lena, b + 1);
  answer[lena - 1] = ',';

  return answer;
}

Z funkcją flat na początku były kłopoty. Maciek strasznie zakręcił... ale rozwiązanie jest dość proste:

WLLC flat(WLLC a)
{
  int  j = 1;
  bool inint = false;
  WLLC answer = malloc(strlen(a) * sizeof(char));
  
  answer[0] = '[';
  for (int i = 0; a[i] != '\0'; i++)
  {
    if (('0' <= a[i] && a[i] <= '9') || a[i] == '-')
    {
      answer[j++] = a[i];
      inint = true;
    }
    else
    {
      if (inint) answer[j++] = ',';
      inint = false;
    }
  }
  if (j == 1) j++;
  answer[j-1] = ']';
  answer[j]   = '\0';
  
  return answer;
}

Iterator i przebiega listę, którą chcemy spłaszczyć. Iterator j przebiega naszą listę wynikową. Jeśli na danej nam liście znajduje się cyfra - to ją przepisujemy. Jeśli nie, to sprawdzamy czy nowy znak zakończył nam jakąś liczbę (służy nam do tego zmienna "inint"). Jeśli zakończył to stawiamy przecinek. Na końcu zamykamy nawias i zwracamy wynik. Warunek if na samym końcu zapewnia nas, że zwrócimy poprawny wynik także dla listy pustej. Przykład użycia:

  WLLC L0 = "[]";
  WLLC L1 = "[3,1,5]";
  WLLC L2 = "[2,[4,7],[]]";
  WLLC L3 = "[[[3],[5,8],2],[1,5]]";
  
  printf("%s\n", merge(L2, L1));
  printf("%s\n", flat(L3));