Úloha: Hodnota řetězcových výrazů

Úkolem bude vyhodnotit řetězcové výrazy, které jsou sestaveny do formy jednoduchého lineárního programu. K dispozici je 26 proměnných s jednoznakovými identifikátory malé anglické abecedy. Každá proměnná obsahuje jeden řetězec, který je před zahájením programu prázdný. Znaky v řetězci jsou indexovány od nuly.
S řetězci je možno provádět pouze tři následující operace:
   Insert - vložení jednoho řetězce do jiného řetězce na určenou pozici
   Delete - smazání části řetězce
   Length - určení délky řetězce
Operace jsou v programu představovány funkcemi, které je možno v jednom příkazu libovolně kombinovat. Funkce jsou mnemonicky označeny počátečním písmenem odpovídající operace. Nejprve uvedeme jednoduchý příklad.
x="abefgh"
y=I(x,2,"cd")
z=D(y,1,4)
w=I(z,L(z),z)
První příkaz vloží do proměnné x řetězec abefgh. Druhý příkaz vloží do proměnné y řetězec, který vznikne z řetězce uloženého v x tak, že se za jeho druhý znak vloží řetězec cd. Proměnná y pak bude obsahovat řetězec abcdefgh. Třetí příkaz vloží do proměnné z řetězec, který vznikne z řetězce uloženého v y tak, že se v něm smažou všechny znaky od pozice 1 do pozice 4 včetně. Proměnná z pak bude obsahovat řetězec afgh. Čtvrtý příkaz provede následující: Nejprve ve funkci L() vyhodnotí délku řetězce afgh uloženého v z, což je 4. Poté vytvoří řetězec, který vznikne vložením kopie tohoto řetězce na pozici 4 v témže řetězci. Protože řetězec afgh má právě čtyři znaky, bude kopie vložena na jeho konec, a v proměnné w se tak octne řetězec afghafgh.
Jak ukazuje poslední řádek příkladu, funkce je možno do sebe libovolně vkládat. Například po provedení příkazů
s="="
t=I(I("10000300",L("xxx"),D("+::2",1,2)),7,s)
bude v t uložen řetězec 100+200=300.

Nyní jednotlivé součásti programu specifikujeme podrobněji.

Program je neprázdná posloupnost přiřazovacích příkazů následovaná příkazem end.
Přiřazovací příkaz se skládá z levé strany, symbolu přiřazení a řetězcového výrazu.
Levá strana přiřazovacího příkazu obsahuje jediný znak, malé písmeno anglické abecedy. Tento znak je zároveň identifikátorem řetězcové proměnné, program může obsahovat až 26 různých proměnných.
Symbol přiřazení je znak rovnítka.
Pravá strana přiřazovacího výrazu je řetězcový výraz.
Řetězcový výraz je buď řetězcová konstanta nebo volání řetězcové funkce.
Řetězcová konstanta je posloupnost tisknutelných znaků ascii (32 - 127). Její zápis je povinně uveden a ukončen znakem úvozovky, které samy nejsou součástí řetězcové konstanty. Řetězcová konstanta neobsahuje znak úvozovky, může být i prázdná. Neplatí lomítková konvence pro definici jiných znaků, žádný znak řetězcové konstanty nemění význam jiných znaků.
Volání řetězcové funkce je buď volání funkce Insert nebo volání funkce Delete.

Volání funkce Insert má tvar
   I(<kam_str>,<kam_index>,<co_str>)
kde <kam_str>, resp. <co_str> je řetězcová konstanta nebo volání řetězcové funkce nebo identifikátor proměnné a <kam_index> je celočíselná konstanta nebo volání celočíselné funkce.
Funkce I vrací řetězec, který vznikne vložením řetězce <co_str> do řetězce <kam_str> mezi znaky na pozicích <kam_index>-1 a <kam_index>. Pokud je hodnota <kam_index> rovna nule, vkládá funkce I řetězec <co_str> na začátek řetězce <kam_str>. Pokud je hodnota <kam_index> větší nebo rovna délce řetězce <kam_str>, vkládá funkce I řetězec <co_str> na konec řetězce <kam_str>.
Př. I("abc",2,I("13",1,"222")) vrací ab12223c.

Volání funkce Delete má tvar
   D(<kde_str>,<od_index>,<do_index>)
kde <odkud_str> je řetězcová konstanta nebo volání řetězcové funkce nebo identifikátor proměnné, <od_index>, resp. <do_index> je celočíselná konstanta nebo volání celočíselné funkce.
Funkce D vrací řetězec, který vznikne z řetězce <kde_str> smazáním podřetězce začínajícího na pozici s indexem <od_index> a končícím na pozici s indexem <do_index>. Pokud je hodnota <od_index> větší než hodnota <do_index> nebo pokud je řetězec <kde_str> prázdný, funkce D vrátí řetězec <kde_str> beze změny. Pokud jsou obě hodnoty <od_index>, <do_index> větší nebo rovny délce retězce <kde_str>, vrací funkce D řetězec <kde_str> beze změny. Pokud je hodnota <do_index> větší nebo rovna délce řetězce <kde_str>, použije funkce D místo ní index posledního znaku v řetězci <kde_str>.
Př. D(D("abcdefghij",2,3),3,4) vrací abehij.

Celočíselná konstanta je neprázdná posloupnost znaků z množiny {'0', '1', ..., '9'}, která může začínat nulou pouze když je jednoprvková. Všechny celočíselné konstanty jsou nezáporné.

Volání celočíselné funkce má tvar
   L(<čeho_str>)
kde <čeho_str> je řetězcová konstanta nebo volání řetězcové funkce nebo identifikátor proměnné.
Funkce L implementuje operaci Length a vrací celé nezáporné číslo, které je délkou řetězce <čeho_str>. Délka prázdného řetězce je 0.
Př. L("aaabbb") vrací hodnotu 6.

Během vyhodnocování výrazu se nemění hodnota žádné proměnné na pravé straně tohoto výrazu. Před prováděním programu jsou všechny proměnné inicializovány prázdným řetězcem.
Úlohou je zjistit, jak se změní hodnoty všech proměnných, které se vyskytly na levé straně nějakého příkazu v programu.

Vstup

Na vstupu je program, každý řádek vstupu obsahuje právě jeden příkaz, poslední řádek obsahuje příkaz end. Program může obsahovat mezery v řetězcových konstantách, jinak neobsahuje mezery žádné. Program je zapsán syntakticky správně podle uvedených pravidel.

Výstup

Na výstupu je seznam hodnot proměnných po skončení programu. Uvedeny jsou pouze ty proměnné, které se vyskytly nalevo v některém z přiřazovacích příkazů programu. Každý řádek výstupu obsahuje jeden prvek seznamu, výstup neobsahuje prázdné řádky. Prvek seznamu má stejný tvar jako přiřazovací příkaz, za identifikátorem proměnné a symbolem přiřazení následuje řetězcová konstanta. Prvky seznamu jsou uvedeny v abecedním pořadí identifikátorů na levé straně.

Příklad

Na vstupu je program:
b=D(I("DUV",3,"VUD"),L(b),L("V"))
e=I(I("",L(c),"DUD"),L(""),I("RAR",1,"DE"))
a=D(I("DA",L(c),a),1,L(d))
c=D(I(d,0,"RE"),3,L(d))
c=I(D("DE",1,L(b)),3,I(c,0,""))
d=D(I("RE",L("VA"),b),L("RUD"),0)
c=I(I(a,0,""),L(""),I(c,3,"DEV"))
end
Výstup:
a="DA"
b="VVUD"
c="DREDEVDA"
d="REVVUD"
e="RDEARDUD"

Testovací data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data


Poznámka
Pro pokročilejší řešitele i pro začínající zájemce uvádíme jako přehledový doplněk zadání bezkontextovou gramatiku, která generuje libovolný program, jak byl popsán výše.
<program>             -> <prirazovaci_prikazy><prikaz_end>
<prirazovaci prikazy> -> <prirazovaci_prikaz><prirazovaci_prikazy> | <prirazovaci_prikaz>
<prirazovaci prikaz>  -> <id_promenne><prirazeni><prava_strana>
<prikaz_end>          -> end
<id_promenne>         -> a | b | c | d ... y | z
<prava_strana>        -> <retezcova_konstanta> | <retezcova_funkce>
<retezcova funkce>    -> <funkce_Insert> | <funkce_Delete>
<funkce_Insert>       -> I(<retezcovy_param>,<ciselny_param>,<retezcovy_param>) 
<funkce_Delete>       -> D(<retezcovy_param>,<ciselny_param>,<ciselny_param>) 
<retezcovy_param>     -> <retezcova_konstanta> | <retezcova funkce>
<ciselny_param>       -> <ciselna_konstanta> | <funkce_Length>
<funkce_Length>       -> L(<retezcovy_param>) 
<ciselna_konstanta>   -> <prvni_cislice><zbytek_cisla> | <cislice>
<zbytek_cisla>        -> <cislice><zbytek_cisla> | <cislice>   
<prvni cislice>       -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<cislice>             -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<retezcova_konstanta> -> <uvozovky><uvozovky> | <uvozovky><retezec><uvozovky>
<retezec>             -> <retezec><znak> | <znak>
<znak>                -> znak ascii od 20H do 7F včetně 
<prirazeni>           -> =   // znak rovnitka, ascii 3DH
<uvozovky>            -> "   // znak uvozovek, ascii 22H