Zkouška 22.1.2019 - "Všechno je buňka"

Základní kurs objektově orientovaného programování v C++. Třídy a objekty, zapouzdření, metody, plymorfismus. Abstraktní datové typy, přetěžování. Kontejnery, iterátory, algoritmy. Šablony, generické programování, kompilační polymorfismus. Výjimky. Bezpečné a přenositelné programování, vazby na OS.
Vilda
Matfyz(ák|ačka) level I
Příspěvky: 12
Registrován: 15. 1. 2018 15:02
Typ studia: Informatika Bc.

Zkouška 22.1.2019 - "Všechno je buňka"

Příspěvek od Vilda »

Dnes zadával Robert Husák. Úloha byla značně jednodušší než předchozí termín. Stačilo si udělat základní objektový návrh a pak rozumně zparsovat vstup. Vzorové řešení je prý na 200 řádků, já to mám na 231, takže tam jsou asi nějaké blbosti navíc. Klíčové je však používat shared pointery, neboť ty se postarají automaticky o všechno. Odcházel jsem po necelých dvou hodinách jako první a pár dalších se už taky chystalo.
Hlavní myšlenka
Cílem úlohy je vytvořit interpreter jednoduchého jazyka, který pracuje se stromovými strukturami na haldě. Jazyk pracuje se dvěma typy objektů:

Celočíselná konstanta (typ int)
Buňka binárního stromu: obsahuje levého a pravého syna, přičemž každý z nich může být buď opět buňka, nebo celočíselná konstanta.
Tyto objekty jsou přiřazovány do proměnných, pomocí nichž je můžeme skládat do složitějších struktur a výsledek následně vypisovat. Příklad použití:

print 42
$value = 42
print $value

$left = cell $value 43
$right = cell 1 2
$top = cell $left $right
print $top
$top2 = $top
print $top2

$leftRight = right $left
print $leftRight
$rightLeft = left $right
print $rightLeft
Výstup:

42
42
((42, 43), (1, 2))
((42, 43), (1, 2))
43
1
Vstup
Argumenty programu
Program je možné volat s libovolným počtem argumentů. Pokud není zadán žádný argument, načtěte příkazy ze standardního vstupu. V opačném případě zpracujte příkazy ze souborů, jejichž cesty byly zadány jako argumenty.

Formát souboru s příkazy
Každý příkaz se nachází na samostatném řádku. Prázdné řádky a řádky, které obsahují jen bílé znaky, ignorujte. Jednotlivé tokeny příkazu jsou oddělené libovolným počtem bílých znaků, vždy však alespoň jedním. Existuje pět možných příkazů:

Přiřazení:
[targetVariable] = [value]
Do proměnné [targetVariable] přiřaďte hodnotu [value]. Hodnota může být buď obsah jiné proměnné, nebo celočíselná konstanta.

Vytvoření buňky:
[targetVariable] = cell [leftValue] [rightValue]
Vytvořte novou buňku, která má levého syna [leftValue] a pravého syna [rightValue]. Opět, [leftValue] i [rightValue] mohou být buď celočíselné konstanty, nebo hodnoty jiných proměnných. Vytvořenou buňku přiřaďte do proměnné [targetVariable].

Výpis hodnoty:
print [value]
Vypište hodnotu [value] na výstup. Opět, [value] může být buď celočíselná konstanta, nebo obsah proměnné. Celočíselnou konstantu vypište standardně v desítkové soustavě, buňku vypište rekurzivně ve formátu (levý, pravý), kde levý a pravý jsou výpisy hodnot synů.

Získání levého syna:
[targetVariable] = left [cellVariable]
Do proměnné [targetVariable] přiřaďte levého syna buňky uložené v proměnné [cellVariable].

Získání pravého syna:
[targetVariable] = right [cellVariable]
Do proměnné [targetVariable] přiřaďte pravého syna buňky uložené v proměnné [cellVariable].

Názvy proměnných vždy začínají znakem $ a kromě něj obsahují jen alfanumerické znaky. Příklady platných proměnných: $var, $camelVar, $CamelVar2, $42. Příklady neplatných proměnných: $with_underscore, $$doubleDollar, noDollar. Hodnotou ([*value] v příkazech výše) může být buď celočíselná konstanta, nebo název proměnné (potom je potřeba vyhledat její hodnotu a použít ji v příkazu).

Výstup
Před interpretací každého zadaného souboru vypište na první řádek jeho cestu s dvojtečkou na konci (při načítání příkazů ze standardního vstupu tento řádek nevypisujte). Následují všechny výstupy z příkazů print, každý na samostatném řádku. Pokud se v souboru objevily nějaké chyby (viz níže), vypište každou z nich na samostatný řádek (tj. výpisy chyb budou prokládané s výstupy programu). Za výstupem z daného souboru vypište jeden volný řádek.

Interpretace každého souboru musí začínat s čistým stavem, tj. proměnné přiřazené v jednom souboru se nepřenášejí do dalšího. Zpracujte jednotlivé příkazy dle jejich zadání výše a vypište výstupy z příkazů print. V případě chyby v nějakém příkazu jeho výsledek ignorujte, vypište chybu spolu s číslem řádku a pokračujte dalším příkazem. Možné chyby:

Syntax error on line 123 - nastává při špatném počtu argumentů, špatné struktuře příkazu, neznámých klíčových slovech, neplatných jménech proměnných apod.
Unknown variable on line 123 - nastává při použití nedefinované proměnné jako hodnoty v některém z příkazů
Invalid operation on line 123 - nastává při zavolání operace left nebo right na celočíselnou konstantu (příp. na proměnnou, která ji obsahuje)
Testovací vstupy
basic.in:
print 42
$value = 42
print $value

$left = cell $value 43
$right = cell 1 2
$top = cell $left $right
print $top
$top2 = $top
print $top2

$leftRight = right $left
print $leftRight
$rightLeft = left $right
print $rightLeft

list.in:
print 42

$list = cell 4 -1
$list = cell 3 $list
$list = cell 2 $list
$list = cell 1 $list

$l = $list
print $l
$v = left $l
print $v

$l = right $l
print $l
$v = left $l
print $v

$l = right $l
print $l
$v = left $l
print $v

$l = right $l
print $l
$v = left $l
print $v

$l = right $l
print $l
$v = left $l
print $v


Výstup
basic.in:
42
42
((42, 43), (1, 2))
((42, 43), (1, 2))
43
1

list.in:
42
(1, (2, (3, (4, -1))))
1
(2, (3, (4, -1)))
2
(3, (4, -1))
3
(4, -1)
4
-1
Invalid operation on line 30
4
Dva vstupy jsem vynechal (errors.in a tree.in). Celé zadání je na http://mff.roberthusak.cz/zkouska2, ale je možné, že tam nebude dlouho.

Samozřejmě zadávání probíhalo asi 20 minut a řešili se tam detaily, které nejsou explicitně zmíněné v zadání. Dokonce kreslil nějaké ukázky na tabuli a říkal různé triky, takže psát to tam je snazší než si to přečíst a kódit doma. Bylo dovolené kódit na vlastních strojích, já to dělal na Linuxu, takže ve svém řešení mám makefile. https://github.com/zouharvi/mff-things/ ... 1/cpp_test
Odpovědět

Zpět na „NPRG041 Programování v C++“