HW4: Evaluátor kostkových výrazů
Odevzdávání částí A a B je ukončeno.
Autoři zadání xhanulik Roman Lacko
Odevzdávané soubory src/*
Konec odevzdání části A 2026-04-08 24:00
Konec odevzdání části B 2026-05-07 24:00
Kostru k úkolu nelze stáhnout

Představení úkolu

Stolní RPG hry jako Dungeons & Dragons používají standardizovaný zápis pro házení kostkami – tzv. dice notation. Výraz 2d6 + 3 znamená: „hoď dvěma šestistěnnými kostkami a přičti 3". Hráči a herní systémy takové výrazy vyhodnocují neustále, a proto existuje potřeba nástroje, který je dokáže automaticky zparsovat a vyhodnotit.

Specifikace jazyka kostkových výrazů

Podporované výrazy

Jazyk podporuje aritmetické výrazy nad kostkami a celými čísly.

Konstrukce Syntaxe Příklad

Hod kostkou

XdY

2d6 – hoď 2× kostkou d6

Kladné celé číslo

N

42

Sčítání

A + B

1d8 + 4

Odčítání

A - B

2d6 - 1

Násobení

A * B

1d4 * 3

Unární mínus

-A

-1d6, 1 + -3

Závorky

(A)

(1d6 + 2) * 3

Keep highest

XdYhZ

4d6h3 – hoď 4d6, použij 3 nejvyšší

Keep lowest

XdYlZ

4d6l1 – hoď 4d6, použij 1 nejnižší

Poznámky:

  • XdY znamená hod X nezávislými kostkami, každá má hodnoty 1..Y.

  • Písmena d, h, l jsou vždy malá.

  • Mezi tokeny (operátory, závorkami, čísly, výrazy hodu kostkou) může být libovolné množství bílých znaků.

    • 2d6 + 3, 2d6+3 i `2d6+ 3 ` jsou platné výrazy.

  • Zápis kostky (XdY, XdYhZ, XdYlZ) nesmí obsahovat žádné mezery.

    • 2 d6 je chybný zápis.

    • 2d6 + 3 je platný výraz.

    • - 2d6 je platný výraz.

  • Pro konstrukce XdYhZ a XdYlZ je chyba, pokud:

    • Z > X

    • Z == 0

  • Pro hod kostkou XdY platí:

    • X ≥ 1

    • Y ≥ 1

  • Unární mínus se váže na nejbližší následující výraz a nelze použít uvnitř zápisu kostky.

  • Literály musí být v rozsahu typu int.

Priorita operátorů

Priorita odpovídá standardní aritmetice:

  • Unární mínus (nejvyšší)

  • Násobení *

  • Sčítání a odčítání +, -

  • Závorky (mění pořadí vyhodnocení)

Binární operátory +, -, * jsou asociativní zleva.

První část (A)

Vaším úkolem je napsat interpret jazyka kostkových výrazů. Napíšete parser pro kostkové výrazy a evaluátor, který zpracovaný výraz vyhodnotí a vrátí výsledek hodu.

Opaque kostkový výraz

Struktura dice_expr představuje kostkový výraz. Její vnitřní reprezentace není součástí rozhraní a je plně v režii implementace.

typedef struct expr dice_expr;

Požadované rozhraní

Vaším úkolem je implementovat následující rozhraní pro parsování a vyhodnocení kostkových výrazů:

typedef enum {
    DICE_OK = 0,
    DICE_ERR_SYNTAX,  // chyba syntaxe: neplatný znak, konec vstupu, závorka,
                      // přebytečný vstup, chybný zápis kostky, neplatné Z,
                      // přetečení číselného literálu
    DICE_ERR_PARSE,   // jiná chyba parsování (alokace paměti apod.)
    DICE_ERR_EVAL,   // chyba při vyhodnocení výrazu
} dice_error;

dice_error dice_parse(const char *input, dice_expr **out);
dice_error dice_eval(const dice_expr *dice_expression, int *out);
void dice_free(dice_expr *dice_expression);

Parsování kostkového výrazu

Funkce dice_parse():

  • zpracuje vstupní řetězec (string) input,

  • vytvoří interní reprezentaci výrazu dice_expr.

Výstup:

  • při úspěchu nastaví *out na vytvořený výraz a vrátí DICE_OK,

  • při chybě nastaví *out na nullptr a vrátí příslušný chybový kód.

Chybové kódy jsou následující:

Kód chyby Situace Příklad vstupu

DICE_ERR_SYNTAX

Neplatný znak, předčasný konec vstupu, chybějící závorka, přebytečný vstup, chybný zápis kostky (Xd0, 0dY, chybějící strany), neplatné Z v XdYhZ/XdYlZ, nebo přetečení číselného literálu

3d6 + @, 3d6 +, (3d6, 3d6 2, 3d0, 4d6h5, 9999999999d6

DICE_ERR_PARSE

Jiná chyba parsování (selhání alokace paměti)

—

Evaluace kostkového výrazu

Funkce dice_eval() vyhodnotí předaný výraz typu dice_expr.

Výstup:

  • při úspěchu uloží výsledek do *out a vrátí DICE_OK,

  • při chybě uloží do *out hodnotu 0 a vrátí chybový kód DICE_ERR_EVAL.

Možné chyby:

  • vstupní argument nullptr,

  • Generátor náhodných čísel vrátil hodnotu mimo [1, sides],

  • Mezivýsledek nebo výsledek přesahuje rozsah int,

  • další běhové chyby.

Generování náhodných čísel

Při vyhodnocení hodu kostkou potřebuje dice_eval() zdroj náhodnosti. Ten je implementován knihovnou rng, která exportuje poskytuje následující rozhraní:

/* Nastaví počáteční stav generátoru pseudonáhodných čísel. */
void rng_seed(unsigned seed);

/* Vrátí pseudo-náhodné číslo v rozsahu 0 až max-1. */
uint16_t rng_uniform(uint16_t max);

Pro vygenerování hodu kostkou se Y stranami zavolejte rng_uniform(Y) + 1, čímž získáte požadovanou hodnotu v rozsahu [1, Y].

Funkce rng_seed() inicializuje generátor a musí být zavolána před prvním voláním rng_uniform(). Testy ji využívají k nastavení deterministické sekvence hodů — dvě volání dice_eval() se stejným seedem vždy produkují stejný výsledek.

Funkci rng_uniform() volejte pouze při skutečném vyhodnocení hodu kostkou. Zbytečná volání (např. zpracování výrazů bez hodu) by narušila deterministickou sekvenci a znemožnila správné testování.

Pořadí vyhodnocení

Kostkový výraz nelze vyhodnotit pouhým čtením znak po znaku, protože obsahuje závorky a operátory s různou prioritou. Je proto nutné nejprve správně rozpoznat strukturu výrazu a teprve poté jej vyhodnotit. Při vyhodnocování je důležité respektovat pořadí operací a pravidla priority. Vyhodnocení probíhá tak, že se postupuje systematicky zleva doprava, přičemž se vždy nejprve vyhodnotí levá část výrazu a až poté pravá část.

Toto pořadí je zvlášť důležité u hodů kostkou, protože každý hod spotřebovává náhodná čísla jako vedlejší efekt. Pořadí vyhodnocení proto ovlivňuje výsledný výsledek a musí být jednoznačné, konzistentní a deterministické.

Uvažujte výraz 1d6 - 1d4. Jeho strukturu lze znázornit pomocí stromu:

  Odčítání     ← kořen, vyhodnotí se poslední
   /   \
Hod     Hod    ← listy, vyhodnotí se první, zleva doprava
1d6     1d4

Nejprve se vyhodnotí oba operandy (hody kostkami) zleva doprava a teprve poté se aplikuje operace odčítání. Evaluátor proto postupuje tak, že vždy nejprve vyhodnotí levý podstrom, následně pravý podstrom a až poté provede samotnou operaci v aktuálním uzlu. Tento postup zajišťuje správné a deterministické pořadí vyhodnocení, které je důležité zejména u operací s vedlejším efektem, jako je hod kostkou.

Příklady kostkových výrazů zapsaných jako stromy

Výraz 2d6 + 3:

  Sčítání
   /   \
Hod     Číslo
2d6      3

Možné vyhodnocení:

  • hod 2d6: padne 2 a 5 → součet 7

  • výraz: 7 + 3 = 10

Výraz 4d6h3 * 2:

    Násobení
     /   \
Keep h.  Číslo
4d6h3      2

Možné vyhodnocení:

  • hod 4d6: padne například 1, 6, 3, 4

  • vybereme 3 nejvyšší: 6, 4, 3 → součet 13

  • výraz: 13 * 2 = 26

Výraz -(1d4 + 1):

 Unární mínus
      |
   Sčítání
    /   \
 Hod    Číslo
 1d4      1

Možné vyhodnocení:

  • hod 1d4: padne 3

  • výraz v závorce: 3 + 1 = 4

  • aplikace unárního mínusu: -4

Druhá část (B)

V první části jste napsali interpret, který zparsuje kostkový výraz a jednou ho vyhodnotí. V praxi ale hráč ani návrhář herního systému nechce znát jeden hod, ale chce vědět, co od daného výrazu očekávat: jaká je nejmenší a největší možná hodnota, jaký je průměrný výsledek a jak typicky vypadá distribuce hodů, když výraz padne dostatečně mnohokrát.

V druhé části tedy doplníte rozšíříte svou implementaci z části A o dvě nové funkce, které tento statistický pohled na kostkový výraz poskytnou:

  • dice_eval_stats() — analytická funkce. Statistiky neodvozuje experimentálně, ale spočítá je přímo z výrazu. Funkce odvodí minimum, maximum a očekávanou hodnotu pomocí pravidel daných v zadání. Žádný hod kostkou se neprovádí, generátor náhodných čísel se vůbec nevolá.

  • dice_eval_n() — paralelní vzorkování. Výraz se vyhodnotí celkem n-krát s nezávislými hody a z posbíraných vzorků se spočítají sumární statistiky (krajní hodnoty, aritmetický průměr a tři kvartily).

Jazyk kostkových výrazů se v této části nemění — žádné nové konstrukce ani operátory. Pouze se rozšiřuje rozhraní knihovny o dvě nové funkce a dvě nové datové struktury (dice_stats, dice_n_stats).

Analytická statistika výrazu

Funkce dice_eval_stats() vrací statistické vlastnosti spočtené přímo z výrazu.

typedef struct {
    int    min;     /* minimální možná hodnota výrazu */
    int    max;     /* maximální možná hodnota výrazu */
    double mean;    /* očekávaná hodnota výrazu       */
} dice_stats;

dice_error dice_eval_stats(const dice_expr *expr, dice_stats *out);

Pravidla výpočtu

Hodnoty se počítají rekurzivně podle struktury výrazu:

Výraz min max mean

N

N

N

N

XdY

X

X * Y

X * (Y + 1) / 2

XdYhZ

Z

Z * Y

Z * (Y + 1) / 2

XdYlZ

Z

Z * Y

Z * (Y + 1) / 2

-A

-Amax

-Amin

-Amean

A + B

Amin + Bmin

Amax + Bmax

Amean + Bmean

A - B

Amin - Bmax

Amax - Bmin

Amean - Bmean

A * B

min ze 4 součinů (viz níže)

max ze 4 součinů (viz níže)

Amean * Bmean

Poznámky:

  • U XdYhZ a XdYlZ je mean definován velmi zjednodušeně jako Z * (Y + 1) / 2, tedy jako kdyby šlo o ZdY. Tato definice je pro účely této úlohy závazná a od přesné hodnoty (která vyžaduje výpočet pořádkových statistik) se může lišit.

  • U násobení A * B může mít Amin..Amax nebo Bmin..Bmax zápornou hodnotu (kvůli unárnímu mínusu), proto min a max musí při výpočtu využít ze všech čtyř krajních součinů Amin * Bmin, Amin * Bmax, Amax * Bmin, Amax * Bmax k nalezení minimální a maximální hodnoty.

  • Pro očekávanou hodnotu součinu lze využít, že podvýrazy A a B čerpají náhodnost z disjunktních hodů, jsou tedy nezávislé: E[A*B] = E[A] * E[B].

Chybové stavy

Situace Výsledek

expr == nullptr nebo out == nullptr

DICE_ERR_EVAL

Přetečení rozsahu int při výpočtu min nebo max

DICE_ERR_EVAL

Při chybě je proměnná pro uložení statistiky *out nastavena na nuly a funkce vrátí chybový kód.

Paralelní vzorkování

Funkce dice_eval_n() vyhodnotí výraz celkem n-krát pomocí zadaného počtu vláken a vrátí sumární statistiky pozorovaných vzorků.

typedef struct {
    int    min;       /* nejmenší pozorovaný vzorek    */
    int    max;       /* největší pozorovaný vzorek    */
    double mean;      /* aritmetický průměr vzorků     */
    int    q1;        /* dolní kvartil (25. percentil) */
    int    median;    /* medián        (50. percentil) */
    int    q3;        /* horní kvartil (75. percentil) */
} dice_n_stats;

dice_error dice_eval_n(const dice_expr *expr,
                       dice_n_stats    *out,
                       unsigned         n,
                       unsigned         threads);

Sémantika:

  • Funkce vyhodnotí výraz expr celkem n-krát.

  • Označme S[0..n-1] posloupnost vzorků seřazenou vzestupně. Výstupní hodnoty jsou definovány takto (bez interpolace; indexy jsou celočíselné výrazy v C se zaokrouhlením dolů):

    • min = S[0],

    • q1 = S[n / 4],

    • median = S[n / 2],

    • q3 = S[3 * n / 4],

    • max = S[n - 1].

  • mean = aritmetický průměr všech n vzorků.

Před funkcí dice_eval_n() je opět potřeba volat rng_seed().

Paralelizace

Implementace musí využít vlákna knihovny C23 <threads.h> (thrd_create, thrd_join). Počet vláken je předáván parametrem threads.

Chybové stavy

Situace Výsledek

expr == nullptr nebo out == nullptr

DICE_ERR_EVAL

n == 0 nebo threads == 0

DICE_ERR_EVAL

Selhání jednotlivého vzorku (přetečení, RNG mimo rozsah, …​)

DICE_ERR_EVAL

Běhové chyby selhání vytvoření vlákna

DICE_ERR_EVAL

Při chybě je obsah *out nastaven na nuly a funkce vrátí chybový kód.

Poznámky

Část A

  • Dbejte na správnou práci s dynamicky alokovanou pamětí.

  • Pro reprezentaci kostkových výrazů můžete využít abstraktní syntaktický strom (AST) v kombinaci s tagged union.

Část B

  • Zachovejte funkcionalitu z části A neboť je součástí testů.

  • Nové funkce a struktury přidejte do souborů src/dice.c a src/dice.h.

vygenerováno 2026-05-12 21:01 upravit