V Úvodu do informatiky jste se asi potkali s pojmem množiny. Ve studijním textu najdeme definováno několik relací a operací na množinách. Uveďme si teď malý přehled:

Neprázdnou množinu A s konečným počtem prvků lze zadat výčtem jako A={a₁,…,a_n}, prázdnou množinu označujeme ∅. Sjednocení množin A a B se značí A ∪ B, průnik A ∩ B, rozdíl A \ B. Relace a ∈ A, A = B, A ⊂ B asi také znáte. Mohutností (kardinalitou) množiny označujeme počet jejích prvků.

Uvažujme následující abstraktní gramatiku. (Abstraktní gramatika odhlíží od přesné podoby jazyka, jako jsou oddělovače, závorkování apod. Slouží pouze k (orientačnímu) vyjádření jeho struktury. Pro rozpoznávání slov daného jazyka je potřeba ji zjednoznačnit a doplnit o chybějící technické detaily. ):

Výraz	  ::= Množina | Mohutnost | Výrok
Výrok	  ::= identifikátor ∈ Množina | Množina = Množina | Množina ⊂ Množina | NOT Výrok | Výrok AND Výrok | Výrok OR Výrok
Množina	  ::= ∅ | { Seznam } | Množina ∪ Množina | Množina ∩ Množina | Množina \ Množina
Seznam	  ::= identifikátor | Seznam , identifikátor
Mohutnost ::= card(Množina)

Zde „identifikátor” označuje jakýkoli řetězec složený z malých písmen a z čísel. Pokud někoho zmátla definice pro Seznam, pak vězte, že je to totéž, jako

Seznam ::= identifikátor (, identifikátor)*

Vaším úkolem je napsat program, který přečte vstup napsaný podle této gramatiky a odpoví takto:

• pokud vstupem je množina, zapíše ji výčtem prvků
• pokud byl vstupem výrok, vypíše jeho pravdivost
• pokud byl vstupem dotaz na mohutnost, vypíše mohutnost

Příklady:

Vstup:

({a,b,c} ∪ {b,c,d}) \ {d,maxipes}

Výstup (všimněte si zejména, že zápis množiny neobsahuje vícenásobné výskyty téhož prvku):

{a,b,c}

Vstup:

(maxipes ∈ ({a,b,c} ∪ {b,c,d}) \ {d,maxipes}) OR ({a} ⊂ {a,b})

Výstup:

True

Vstup:

card({a,maxipes,c} ∩ {maxipes,minikocka})

Výstup:

1

K tomu všemu je třeba zadefinovat vhodný datový typ k reprezentaci vstupu a rovněž zvolit podrobnou gramatiku pro vstup a implementovat jeho načítání. Možné rozšíření (za které můžete po domluvě obdržet zvýšení limitu pro počet řešitelů) je umožnění definování zkratek. Například tak, aby vstup mohl obsahovat následující definice:

A = {a,b,c}
B = {c,d,e}
C = {maxipes}
card((A ∪ B) \ C)

Odhadovaný počet řešitelů: 2.