C, vlastný zásobník a kontrola zátvoriek

Načo zásobník?

Zásobník je skvelá vec. Vieme ho využiť na zistenie, či je výraz správne uzátvorkovaný:

Napríklad tento program v jazyku Clojure je správne uzátvorkovaný:

(dotimes [card-number 3]
    (println "deal card number" (inc card-number)))

A tento JSON zase nie:

{ "mená" : [ "Adam", "Eva" }

Jednoduchý algoritmus vyzerá takto:

  1. načítame znak zo vstupu
  2. ak je to ľavá zátvorka ({, (, [, <)) dáme ju na vrch štósu
  3. ak je to pravá zátvorka ({, (, [, <)): a. vyberieme zátvorku z vrchu štósu b. ak to nie je kamarátka rovnakého typu (napríklad máme [, ale na vrchu štósu je ]), máme chybu a končíme.

Ešte okrajové prípady!

  • ak pri vyberaní zátvorky z vrchu štósu zistíme, že máme prázdny štós, máme priveľa pravých zátvoriek (ktosi zabudol uviesť ľavú zátvorku).
  • ak načítame všetky znaky a štós nie je prázdny, znamená to priveľa ľavých zátvoriek. To je častejšia chyba: znamená, že chýba niektorá pravá zátvorka.

Pre Clojure bude postup vyzerať nasledovne:

  • znak: (, strčíme na štós: (
  • znak: [, strčíme na štós: [ `(
  • znak: ], vytiahneme zo štósu [, štós: (
  • znak: (, strčíme na štós: ( (
  • znak: (, strčíme na štós: ( ( (
  • znak: ), vytiahneme zo štósu (, štós: ( (
  • znak: ), vytiahneme zo štósu (, štós: (
  • znak: ), vytiahneme zo štósu ( a štós ostane prázdny.

Pozrime sa na ten zlý JSON:

{ "mená" : [ "Adam", "Eva" }
  • znak: {, strčíme na štós: `{“
  • znak: [, strčíme na štós: [ {
  • znak: }, vytiahneme z vrchu štósu ]. To však nie je kamarátska zatvorka a máme chybu typu priveľa ľavých zátvoriek.

Ak si to zhrnieme, od štósu potrebujeme tri operácie:

  • vkladať na vrch
  • vyberať z vrchu
  • a zisťovať, či je prázdny

Mnohokrát sa dodáva ešte štvtá operácia:

  • obdivovať jeho vrch

V angličtine im zodpovedajú operácie push (natlač), pop (vyber), peek (nakukni) a empty (zisťovanie prázdnoty).

A prečo štós? Pretože to najlepšie zodpovedá štósu papierov, alebo ešte lepšie, štósu tanierov:

Štós tanierov

Po slovensky však žiadny informatik nepoužije slovo štós (aj keď slovenský jazykový korpus s tým nemá problém); zaužívalo sa totiž označenie zásobník, a to zrejme pod vplyvom služby v armáde:

Zásobník pre samopal CZ Scorpión si môžete kúpiť napríklad z AFG.sk:

K tomu samopal skoro zadarmo!

Implementácia v Céčku

Samostatné céčko má veľmi minimalistickú knižnicu a žiadny variant java.util.Stack, či pythonovských listov neexistuje.

Ak máme šťastie a programujeme pre BSD či Linux, vieme využiť knižnicu sys/queue.h a ak nie, môžeme si to urobiť po svojom.

Dátové štruktúry

Toto je zásobník:

Vraj balóniky a UML deti nesúvisia so zásobníkom? Au contraire!. Každý balónik je položka spájaného zoznamu a každá šnúrka nie je nič iné než spôsob, akým sa dostať k ďalšiemu balóniku (jeho pritiahnutím k ruke).

A nebudeme to viac tajiť, každá šnúrka predstavuje pointer na balónik, lebo ten, kto drží šnúrku, vie pritiahnutím chytiť aj samotný balónik na jej konci.

Každý balónik má okrem svojej farby, veľkosti a iných atribútov (napr. typu plynu vo vnútri, veď s héliom je zábava) šnúrku k nasledovnému balóniku, čiže tiež pointer na balónik.

V tejto analógii bude platiť:

Šnúrka je pointer!

Šťastné dieťa sa vie dostať vďaka šnúrke k prvému balóniku, a keď sa na to pozrieme inak, predstavuje radostnú radolesť, ktorá drží zoznam balónikov. (Toto súbalónie vie odovzdať inému dieťaťu, ak treba.)

Vyplýva z toho rozkošná vlastnosť: zoznam balónikov možno dľa ľubovole zamieňať s pointrom na prvý balónik.

Lebo kto má šnúrku k prvému balóniku, vie sa postupne dostať aj k tým ostatným.

Poďme to ale napísať v C!

Balónik zareprezentujeme ako štruktúru predstavujúcu položku zásobníka. V zásobníku nebudeme evidovať ani farbu, ani hélium, ale len znaky: lebo nezabúdame na úlohu zo začiatku článku.

struct polozka 
{
    char znak;
    struct polozka * dalsia;
};

Niektorým ľuďom prekáža, že struct polozka je definovaná ako zloženina znaku a pointra na struct položka, ale to nie je nič zvláštne: rekurzia je prirodzená vlastnosť nielen v matematike.

Nezabudnime tiež uviesť za koncovou kučeravou zátvorkou bodkočiarku!

Máme dátovú štruktúru a poďme si vyrobiť prázdny zoznam! Ten bude vyzerať takto:

Áno. Smutné-neveselé dieťa drží šnúrku, ale nemá na jej konci žiadny balónik. Nula balónikov znamená prázdny zoznam:

#include<stdlib.h>

int 
main(void) 
{
    struct polozka * prazdny_zoznam = NULL;
    return 0;
}

Premenná prazdny_zoznam má typ pointer na struct polozka (nezabúdajme, je to šnúrka! Šnúrka je pointer!) A keďže na jej konci nie je žiadny balónik, budeme to reprezentovať NULLovým pointerom.

Nezabúdajme tiež, že “zoznam položiek možno zamieňať s pointerom na jeho prvú položku!” a preto celý zoznam je typu struct polozka *.

Určite nás to bude iritovať — tieto multianalógie, ktoré musíme držať v hlave, sa ľahko zabúdajú.

Našťastie v C môžeme dávať dátovým typom vlastné pomenovania (prepytujem aliasy, aj keď žiadny céčkar to tak nevolá):

typedef struct polozka * ZASOBNIK;

V preklade: odteraz je dátový typ struct polozka * pokrstený na ZASOBNIK. (Niektoré konvencie v C hovoria, že typedef/aliasnuté dátové typy sú veľkými písmenami.)

Program po úprave bude vyzerať takto:

#include<stdlib.h>

int 
main(void) 
{
    ZASOBNIK prazdny_zoznam = NULL;
    return 0;
}

Prázdnota zásobníka

Dátové štruktúry by sme mali nateraz vybavené a je čas na algoritmy! Ehm, či skôr implementácie štyroch funkcií.

Začnime najjednoduchšou: zistením, či je zásobník prázdny. Hlavička funkcie?

int 
zasobnik_prazdny(ZASOBNIK zasobnik);

Funkcia vráti jednotku, ak je zásobník prázdny, a inak vráti nulu. A parametre? Vieme radostne uvažovať nad čŕstvo definovaným dátovým typom ZASOBNIK, za čím si vieme predstaviť pointer na prvý prvok zásobníka.

Implementácia je jednoduchá:

int 
zasobnik_prazdny(ZASOBNIK zasobnik) 
{
    return (zasobnik == NULL);
}    

Skvelé, môžeme otestovať program!

include<stdlib.h>

int main(void) {
    ZASOBNIK z = NULL;
    if (zasobnik_prazdny(z))
    {
        puts("Zasobnik je prazdny");
    } else {
        puts("Zasobnik NIE JE prazdny");
    }
    return 0;
}

Pridávanie na zásobník

Soundtrackom toho bloku je Garbage: Push It. Teda až na ten Garbage, snáď budeme pridávať na vrchol zásobníka rozumné veci.

Tu však bude algoritmus o niečo zložitejší, pretože musíme dodržať základnú zásadu pri hraní sa s balónikmi:

Balónik, ktorý nedrží žiadna ruka, alebo nie je priviazaný o iný balónik, uletí do nenávratna!

O uletených balónikoch sa porozprávame niekedy neskôr, v C to znamená veľkú galibu.

  1. Predstavme si teraz, že zoznam balónikov drží Zuzanka.

  2. Pre znak, ktorý pridávame, potrebujeme nafúknuť nový balónik. Bude ho musieť niekto držať (inak by uletel, čo znamená bedákanie!). Povoláme si na pomoc kamaráta Petríka, a dáme mu do ruky šnúrku k novému balóniku.

    Nafukovanie urobíme dynamicky. V pamäti vyhradíme priestor pre položku zoznamu (struct polozka), získame šnúrku k nemu (teda pointer) a potom sa s ním budeme baviť ďalej.

    struct polozka * p = malloc(sizeof(struct polozka));
    

    Funkcia malloc() alokuje presne toľko bajtov pamäte, koľko zaberá dátový typ struct polozka, čo zistíme pomocou pásmového metra funkcie sizeof. Pointer na novú položku (= šnúrku na balónik) dáme do ruky pomocnej premennej p˙.

    Bokom: ak sa zdá konštrukcia divná, netreba panikáriť. Ak chceme alokovať pamäť pre jeden int, píšme int * prvok = malloc(sizeof(int)). Ak chceme pamäť pre pätnásť charov (čiže 14znakový reťazec), char * pole = malloc(sizeof(char) * 15).

  3. Na čerstvo nafúknutý balónik naviažeme zvyšok zoznamu. Inak povedané, k balóniku, ktorý drží Petrík, priviažeme šnúrku, ktorá bude končiť na prvom balóniku Zuzanky. Síce sme to nepovedali, ale na jednom balóniku môže byť priviazaných viacero šnúrok (deti sú slušné, a nikdy sa nebudú o balóniky naťahovať.)

    V C kóde:

    (*p).znak = c; /* znak v premennej c pridávame na zásobník */
    (*p).dalsia = z
    

    Nezabúdajme: Petrík drží šnúrku k čerstvému balóniku. Ak chceme meniť vlastnosti balónika, musíme k nemu dostať cez šnúrku, čo zabezpečíme operátorom dereferencie, písaním ako *.

    • na nový balónik nakreslíme znak, ktorý bude držať
    • a priviažeme naň šnúrku k Zuzankinmu prvému balóniku. V tomto prípade sa oplatí overiť dátové typy:
      • položka dalsia je typu struct * polozka (šnúrka k balóniku) a premenná z (Zuzankinka ruka) je typu ZASOBNIK, čo je alias pre struct * polozka. Všetko je teda v poriadku.
  4. Teraz nastane už len kamarátska výmena. Ak Zuzanka pustí svoj balónik, nič sa nedeje, pretože celú reťaz balónikov drží Petrík. (Áno, Petrík drží celý nový zoznam balónikov!)

    V C kóde sa výmena nemusí nijak prejaviť.

  5. Ak Petrík odovzdá svoju reťaz Zuzanke, ktorá má prázdne ruky, sme skoro na konci. Petríka pošleme domov (bude síce plakať, ale v C premenné nikdy neplačú), a sme hotoví! Máme dlhší zásobník!

    z = p;
    

Poďme si celý kód zosumarizovať. Funkcia bude potrebovať dve veci: zásobník a znak, ktorý sa pridá na jeho vrchol.

Čo bude vracať? Môže vracať čerstvo rozšírený zásobník. Prvý nástrel funkcie môže byť takýto, ale pozor! obsahuje viacero chýb:

ZASOBNIK 
zasobnik_push(ZASOBNIK z, char c) 
{
    struct polozka * p = malloc(sizeof(struct polozka));
    (*p).znak = c; /* znak v premennej c pridávame na zásobník */
    (*p).dalsia = z;
    z = p;                
    return z;
}

Môžeme ho otestovať:

include<stdlib.h>

int 
main(void) 
{
    ZASOBNIK z = NULL;
    z = zasobnik_push(z, '(');
    z = zasobnik_push(z, ')');

    if (zasobnik_prazdny(z)) 
    {
        puts("Zasobnik je prazdny");
    } else {
        puts("Zasobnik NIE JE prazdny");
    }
    return 0;
}

Ak program spustíme mali by sme vidieť:

Zasobnik NIE JE prazdny

Poďme však veľmi rýchlo doopravovať zasobnik_push(). V prvom rade:

Pri každom volaní funkcie malloc() overte, či vrátila nulu. (čítanie z “GNU Coding Standards”, 4.2, ods. 3).

Môže sa veľmi ľahko stať, že malloc() zlyhá a to najčastejšie vo chvíli, keď sa minie dostupná pamäť pre váš program.

Čo však spraviť v takej chvíli?

Ak malloc zlyhá v neinteraktívnom programe, považujte to za fatálnu chybu. (čítanie z “GNU Coding Standards”, 4.2, ods. 7).

Program tak môže rovno skončiť, napríklad s exit kódom 2, čo bude naša dohoda indikujúca nedostatok pamäte. Aby sme po kóde nemali pohodené magické čísla, definujeme si konštantu:

#define EXIT_MALO_PAMATE 2

ZASOBNIK 
zasobnik_push(ZASOBNIK z, char c) 
{
    struct polozka * p = malloc(sizeof(struct polozka));

    if(p == NULL) {
        exit(EXIT_MALO_PAMATE);
    }

    (*p).znak = c;
    (*p).dalsia = z;
    z = p;                
    return z;
}

Druhá úprava bude estetická: v jazyku C je pristupovanie k vlastnostiam balónikov cez šnúrky (čítajme to ako “pristupovanie k položkám struct cez pointre”) natoľko bežné, že si to vyslúžilo vlastnú syntax:

Namiesto:

(*p).znak = c;
(*p).dalsia = z;

môžeme písať šípkovú syntax:

p->znak = c;
p->dalsia = z;

Nakúkanie do zásobníka

Konečne vieme pridávať dáta! Ale ak nechceme mať zo zásobníka čiernu dieru, chytro dopíšme spôsob, ako naň nakúkať.

Opäť prvé, aj keď neveľmi správne, riešenie:

char 
zasobnik_peek(ZASOBNIK z) 
{
    return z->znak;
}

Skúsme ho overiť:

int 
main(void) 
{
    ZASOBNIK z = NULL;
    z = zasobnik_push(z, '(');

    printf("%c", zasobnik_peek(z));

    return 0;
}

Po spustení by sme mali uvidieť vypísanú zátvorku. Skúsme ale toto!

ZASOBNIK z = NULL;
printf("%c", zasobnik_peek(z));

Po spustení uvidíme takmer určite:

SEGMENTATION FAULT.

Do funkcie totiž príde premenná typu ZASOBNIK obsahujúca NULL, ktorá rozhodne nemá položku s menom znak. Čo je v Jave výnimka NullPointerException, v C je to nepovolený prístup do pamäte a pád programu.

Rýchlo opravme funkciu! Čo však v prípade prázdneho zásobníka? Ktosi navrhol, že môžeme vracať špeciálny znak, napríklad \0.

char 
zasobnik_peek(ZASOBNIK z) 
{
    if (zasobnik_prazdny(z)) 
    {
        return '\0';
    } else
    {
        return z->znak;
    }
}

Pop!

Čas na získavanie balónikov, praskanie a deštrukčnú činnosť! Algoritmus pre popovanie bude takýto:

  1. Predstavme si teraz, že zoznam balónikov drží Zuzanka. Zbavme sa prvého balónika, ale bez toho, aby uletel!

  2. Povoláme na pomoc kamaráta Petra a povieme mu, nech podrží prvý balónik zo zoznamu, čo je rovnaký balónik, ku ktorému drží šnúrku Zuzanka.

    struct polozka * p = NULL;
    p = z;
    
  3. Niekde bokom si poznačíme znak z prvého balónika. Budeme ho potrebovať neskôr.

    char c;
    c = z->znak;
    
  4. Zuzanke povieme, nech si pritiahne k ruke druhý balónik v poradí.

    z = z->dalsia;
    

    Teraz je veľmi dôležité, aby prvý balónik držal Peter, pretože inak by uletel do nenávratna!

    Zuzanka v tejto chvíli drží kratší zoznam a mohli by sme už končiť. Ale ešte jedna vec!

  5. Prvý balónik už nebudeme potrebovať: znak, ktorý bol na ňom namaľovaný, už máme poznačený bokom. V takom prípade ho potrebujeme prasknúť. Balóniky, ktoré sú dynamicky alokované structy (alokované cez malloc()) zaberajú pamäť a ak ich nepotrebujeme, pamäť musíme ručne uvoľniť.

    Uvoľnenie pamäte dosiahneme cez funkciu free().

    free(p);
    

    V C platí zásada, že každé volanie malloc() by malo mať skamarátené volanie free()!

Sumárny kód, tradične s mnohými chybami, bude vyzerať:

char
zasobnik_pop(ZASOBNIK z) 
{
   char c;
   struct polozka * p = NULL;

   p = z;
   c = z->znak;
   z = z->dalsia;
   free(p);

   return c;
}

Skúsme si ho overiť, a to na príklade prázdneho zásobníka:

int 
main(void) 
{
    ZASOBNIK z = NULL;

    printf("%c", zasobnik_pop(z));

    return 0;
}

Uvidíme:

SEGMENTATION FAULT!

Program chcipne niekde v okolí c = z->znak. Ak sme dávali pozor pri predošlej sekcii, vieme prečo: NULLový pointer nemá znak.

Musíme teda overiť, či náhodou nePOPujeme z prázdneho zásobníka! Ak áno, môžeme vrátiť tradičný \0.

char
zasobnik_pop(ZASOBNIK z) 
{
   char c;
   struct polozka * p = NULL;

   if (zasobnik_prazdny(z)) 
   {
        return '\0';
   }

   p = z;
   c = z->znak;
   z = z->dalsia;
   free(p);

   return c;
}

Skúsme teraz toto:

int 
main(void) 
{
    ZASOBNIK z = NULL;
    z = zasobnik_push(z, '(');
    z = zasobnik_push(z, '{');

    printf("Caka sa '{', prichadza '%c' ", zasobnik_pop(z));
    printf("Caka sa '(', prichadza '%c' ", zasobnik_pop(z));

    return 0;
}

Po spustení uvidíme:

Caka sa '{', prichadza '{''
Caka sa '(', prichadza '{'

Dvakrát sa POPne kučeravá zátvorka! Ak by sme sa na to pozreli hlbšie, zistili by sme, že pop() nefunguje správne: stále sa totiž vytiahne zo zásobníka tá istá najvrchnejšia položka, alebo inými slovami: funkcia nefunguje ako pop(), ale ako peek().

ČOŽE?

Naša funkcia vracia jediný parameter: znak, ale v skutočnosti potrebujeme vracať až dve veci! Nielen znak, ale aj kratší zásobník!

ČOŽE?

Doteraz sme funkciu chápali ako mäsomlynček, do ktorého narveme vstupné parametre, a z jeho druhého konca vypadne spracovaný výsledok.

Lenže céčkové funkcie vedia fungovať aj ako kuchynský robot-mixér, kam narveme dáta, necháme si ich pomixovať a potom ich z neho vyberieme. V našom prípade potrebujeme “pomixovať” premennú so zásobníkom: presnejšie, potrebujeme si z nej nechať odseknúť prvý prvok.

Takéto spracovanie parametrov v C sa nazýva odovzdávanie parametrov odkazom. Premenná posielaná do funkcie odkazom je nielen vstupná (putuje do mlynčeka), ale vstupno/výstupná. Funkcia vie vo svojom vnútri meniť obsah premennej a zmeny budú vidieť aj po skončení vykonávania funkcie.

Ak chceme označiť premennú ako vstupno-výstupnú, použijeme … TADÁ … pointery!

Hlavička funkcie bude vyzerať:

char
zasobnik_pop(ZASOBNIK *z) 

V tomto prípade sa z premennej z stane pointer na ZASOBNIK. Ak nechceme pracovať s pointrom na ZASOBNIK, ale so ZASOBNIKom, použijeme starú známu dereferenciu, teda operátor *.

Začneme vidieť hviezdičky pred očami!

char
zasobnik_pop(ZASOBNIK *z) 
{
   char c;
   struct polozka * p = NULL;

   if (zasobnik_prazdny(*z)) /* dereferencia! */
   {
        return '\0';
   }

   p = *z; /* dereferencia! */
   c = (*z)->znak; /* dereferencia! */
   *z = (*z)->dalsia; /* 2x dereferencia! */
   free(p);

   return c;
}

Dalo by sa povedať, že vstupno-výstupné premenné stačí mechanicky predradiť operátorom dereferencie a všetko pôjde po poriadku. S jedinou poznámkou: ak máme vstupno-výstupnú premennú reprezentujúcu *pointer na struct` a chceme pristupovať k jej položkam, potrebujeme výraz korektne uzátvorkovať:

(*z)->znak;

Vyskúšajme si to na predošlom prípade… Ale pozor! Funkcia zasobnik_pop už neberie ZASOBNIK, ale pointer naň!

Ak máme premennú a chceme získať jej adresu (teda získať na ňu pointer), použijeme operátor referencie: ampersand &.

Ampersand a hviezdička sú skamarátené operátory: hviezdička ide po šípke, čiže z pointeru získa obsah. Ampersand zase pre danú premennú získa jej adresu v pamäti, čiže vracia pointer.

Pekná (iná) analógia sú kľúče od hotelovej izby: ak máte v ruke kľúče, držíte pointer. Hviezdička znamená dokráčať do izby a otvoriť si ju a mať možnosť používať jej inventár. Ampersand použitý na izbu znamená získanie kľúčov od nej.

int 
main(void) 
{
    ZASOBNIK z = NULL;
    z = zasobnik_push(z, '(');
    z = zasobnik_push(z, '{');

    printf("Caka sa '{', prichadza '%c' ", zasobnik_pop( &z ));
    printf("Caka sa '(', prichadza '%c' ", zasobnik_pop( &z ));

    return 0;
}

Úprava tlačenia!

Vráťme sa ešte k tlačeniu vecí na vrchol zásobníka: funkcia zasobnik_push bude vyzerať “viac céčkovejšie”, ak ju upravíme v duchu popu: bude brať vstupno/výstupnú premennú ZASOBNIK, a nebude vracať nič.

#define EXIT_MALO_PAMATE 2

void
zasobnik_push(ZASOBNIK *z, char c) 
{
    struct polozka * p = malloc(sizeof(struct polozka));

    if(p == NULL) {
        exit(EXIT_MALO_PAMATE);
    }

    (*p).znak = c;
    (*p).dalsia = *z;
    *z = p;                
}

Lebo céčkovou filozofiou funkcií často býva vracať parametre cez volania odkazom a návratové hodnoty rezervovať pre úspech/neúspech funkcie. (Takto napríklad funguje scanf a mnoho funkcií z stdio.h.)

Máme celý algoritmus!

Ak sa pozrieme, čo všetko je hotové, zistíme, že… máme všetko, čo sme od zásobníka potrebovali.

Je čas urobiť celý algoritmus z úvodu!

#include<stdlib.h>
#include<stdio.h>

typedef struct polozka *ZASOBNIK;

#define EXIT_MALO_PAMATE 2

struct polozka
{
  char znak;
  struct polozka *dalsia;
};

int
zasobnik_prazdny (ZASOBNIK zasobnik)
{
  return (zasobnik == NULL);
}

void
zasobnik_push (ZASOBNIK * z, char c)
{
  struct polozka *p = malloc (sizeof (struct polozka));

  if (p == NULL)
    {
      exit (EXIT_MALO_PAMATE);
    }

  (*p).znak = c;
  (*p).dalsia = *z;
  *z = p;
}

char
zasobnik_pop (ZASOBNIK * z)
{
  char c;
  struct polozka *p = NULL;

  if (zasobnik_prazdny (*z))
    {
      return '\0';
    }

  p = *z;
  c = (*z)->znak;
  *z = (*z)->dalsia;
  free (p);

  return c;
}

int
je_v_pare (char z1, char z2)
{
  return (z1 == '(' && z1 == ')') ||
    (z1 == '{' && z2 == '}') || (z1 == '[' && z2 == ']');
}

int
main ()
{
  int c;
  char vrchol_zasobnika;
  ZASOBNIK z = NULL;

  while ((c = getchar ()) != EOF)
    {
      if (c == '(' || c == '{' || c == '[')
    {
      zasobnik_push (&z, c);
    }
      else if (c == ')' || c == '}' || c == ']')
    {
      if (zasobnik_prazdny (z))
        {
          fprintf (stderr, "Privela pravych zatvoriek! %c\n", c);
          return -1;
        }
      vrchol_zasobnika = zasobnik_prazdny (z);
      if (!je_v_pare (c, vrchol_zasobnika))
        {
          fprintf (stderr, "Zatvorky nie su v pare! %c <-> %c\n", c,
               vrchol_zasobnika);
          return -1;
        }
    }
    }

  if (!zasobnik_prazdny (z))
    {
      fprintf (stderr, "Privela lavych zatvoriek! '%c'\n", zasobnik_pop (&z));
    }

  return 0;
}

Čo sme získali

Na začiatku sa síce zdalo, že chýbajúci zásobník v C je strašná tragédia, ale úprimne: po svojom sme ho implementovali veľmi rýchlo a tiež efektívne. V skutočnosti sme dokonca implementovali spojový zoznam, aj keď doň môžeme pridávať prvky len na začiatok a uberať ich tiež len zo začiatku.

Zároveň sme ukázali množstvo céčkoidných vlastností: pointery, structy, a dokonca aj odovzdávanie parametrov odkazom!

Pridaj komentár

Vaša e-mailová adresa nebude zverejnená. Vyžadované polia sú označené *