Nemzetközi Informatikai Diákolimpia 1991

Egy s-kifejezés S-ek és zárójelek sorozata, melyet a következő rekurzív módon definiálunk.
 

A.	S egy s-kifejezés.
B.	Ha M és N s-kifejezések, akkor (MN) is az.

Például ((((SS)(SS))S)(SS)) egy s-kifejezés.

A záró zárójelekúj információt nem tartalmaznak, ezért ezeket el lehet hagyni. Azaz az (MN) helyett (MN-et írhatunk. Az előző példa s-kifejezése ekkor így fog kinézni. ((((SS(SSS(SS

Feladat:

1. Írj egy genskif nevű eljárást, amely s-kifejezéseket generál. Az eljárás n állományt állítson elő. Az i. állomány tartalmazza az összes i hosszúságú s-kifejezést (hosszúság=az s-kifejezésben felhasznált S-ek száma). Az állományban az s-kifejezéseket pontosvessző válassza el, az állományt pedig egy pont zárja le.

Írj programot, amely beolvas egy n (n<=10) egész számot, és az előbbi eljárást felhasználva az összes előállított s-kifejezéseket kiírja a képernyőre.

Válasszunk egy s-kifejezéseken értelmezett műveletet. Az egyetlen, ami szóba jöhet, a következő:

Az s-kifejezés bármely (((SA)B)C) alakú része, ahol A, B és C is s-kifejezések, átírható a következő formára: ((AC)(BC)) azaz rész₁(((SA)B)C)rész₂ -> rész₁((AC(BC))rész₂

E szabály alkalmazását az s-kifejezés egyszerűsítésének nevezzük.

Több különböző stratégia szerint választhatjuk ki az s-kijfejezés egyszerűsítendő részét. Az s-kifejezés normalizálásának nevezzük azt, ha az egyszerűsítést egymás után többször is elvégezzük, mindaddig, amíg az eredmény s-kifejezés tovább már nem egyszerűsíthet?.

Az egyszerűsítési folyamatra egy lehetséges példa:

((((SS)(SS))S)(SS)) -> (((SS)((SS)S))(SS)) -> ((S(SS))(((SS)S)(SS))) -> ((S(SS))((S(SS))(S(SS))))

2. Válassz egy megfelelő adatszerkezetet az s-kifejezések tárolására, amely lehetővé teszi az egyszerűsítésések alkalmazását! Írj egy readskif és writeskif eljárást, amely beolvas, illetve kiír egy s-kifejezést és közben elvégzi a szükséges konverziókat a kifejezés szöveges alakja és általad választott tárolási módja között! Programodnak ezt a transzformációt be is kell mutatnia.

3. Írj egy reduce nevű eljárást, amely egy s-kifejezés egy-egy kijelölt részén végrehajt egy egyszerűsítési lépést! A programod mutassa be az eljárás működését!

4. Írj egy normalize eljárást, amely egy adott s-kifejezésre ismételten választ egy részkifejezést, s erre végrehajtja az egyszerűsítést mindaddig, amíg az eredményként kapott s-kifejezés tovább már nem egyszerűsíthető, vagy az egyszerűsítések száma meghalad egy értéket! Mutasd be az eljárás működését!

5. Végül az egészet foglald össze egyetlen programba, amely a következőket tudja!

a) bekéri a felhasználótól az n hosszúságot,
b) a genskif által előállított n hosszú s-kifejezéseket használja fel,
c) transzformálja az s-kifejezéseket az általad választott tárolási módra,
d) normalizálja, ha lehetséges,
e) eredményül adja a normalizált s-kifejezést,
f) eredményül adja az egyes s-kifejezéseken végzett egyszerűsítések számát, vagy a 'nem normalizált' üzenetet abban az esetben, ha a normalizálás 30 lépésen belül nem sikerült,
g) eredményül adja a nem normalizált s-kifejezések számát az összes n hosszúságú kifejezés számához viszonyítva.