Kombinatorna logika

Osnovne informacije

Omejitve
  • Čas: 4 s
  • Spomin: 128 MB
Avtor:
  • Vid Kocijan
  • UPM 2018

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Kombinatorna logika je preprost jezik za opisovanje računskih izrazov. Izraz je sestavljen iz oklepajev, spremenljivk in operatorjev S in K. Pri tej nalogi se bomo omejili na izraze, ki ne vsebujejo spremenljivk. Napišite program, ki bo prebral izraz kombinatorne logike, ga okrajšal (tj. poračunal, kolikor je to možno) in izpisal postopek.

Na vhodu bo podan izraz iz črk S in K ter pravilno gnezdenih oklepajev. Operatorja S in K delujeta na drugih operatorjih ali izrazih, ki jima direktno sledijo, po naslednjih predpisih:

  • Kxy = x,
  • Sxyz = xz(yz),

kjer x, y in z predstavljajo neke izraze. V izrazu z več operatorji računamo od leve proti desni. Primere računanja si lahko ogledate na primerih spodaj.

V izrazu ne bo nobenih odvečnih oklepajev. Oklepaje lahko odstranimo, če z izbrisom para oklepajev ne spremenimo pomena izraza. V posebnem primeru to pomeni, da lahko vedno odstranimo oklepaje okoli ene same črke, npr. poenostavimo lahko (S) v S, in da lahko odstranjujemo levo poravnane oklepaje, npr. (((SK)K)S)S poenostavimo v SKKSS. Še en primer: Oklepaje v nizu (S((KK)S(K))) lahko poenostavimo v S(KKSK).

V kolikor operatorju S ali K ne sledi dovolj argumentov, okrajšave ne moremo narediti. Argument operatorju je vedno najkrajši neprazen strnjen niz, ki operatorju sledi in predstavlja veljaven izraz. V izrazu SK(SK)SK so (trije) argumenti prvega operatorja S sledeči: K, (SK) in S. Zadnji znak (torej K) ni argument operatorja S, saj S sprejme le 3 argumente.

Naloga

Napišite program, ki prebere izraz in ga poenostavi. Po vsakem koraku naj izpiše trenuten niz. Kadar je možno v nekem koraku izbrati več različnih operatorjev, naj program izbere tistega izmed njih, ki se v izrazu nahaja najbolj levo. Zagotovljeno je, da bo ta postopek vedno končen in skupna dolžina izpisa ne bo presegla 20\,000 znakov.

Vhodni podatki

V prvi vrstici je podan niz, sestavljen iz črk S, K in pravilno gnezdenih oklepajev. Niz bo podan brez odvečnih oklepajev.

Omejitve vhodnih podatkov

Niz na vhodu ne bo presegal dolžine 1000 znakov.

Izhodni podatki

Izpišite celoten postopek računanja danega izraza. Vsak izraz, ki ga program izpiše, naj bo podan brez odvečnih oklepajev. Za obliko izpisa si oglejte testne primere spodaj.

Omejitve izhodnih podatkov

Skupna dolžina izpisa ne bo presegla 20\,000 znakov.

Primeri

Vhod

SKKK

Izhod

SKKK
=KK(KK)
=K

Vhod

S(SK)(KS)(SKK)

Izhod

S(SK)(KS)(SKK)
=SK(SKK)(KS(SKK))
=K(KS(SKK))(SKK(KS(SKK)))
=KS(SKK)
=S

Vhod

SK

Izhod

SK

Vhod

S(KSK)

Izhod

S(KSK)
=SS

Vhod

S(KK)S

Izhod

S(KK)S

Komentar

Pri prvem primeru najprej uporabimo najbolj levi operator S, nato pa najbolj levi operator K.

Drugi primer je zgolj zaporedje uporab najbolj levega operatorja.

Pri tretjem primeru nobeden od operatorjev nima dovolj argumentov, zato ne moremo izračunati ničesar.

Pri četrtem primeru ima najbolj levi operator (tj. najbolj levi S) premalo argumentov, zato izberemo najbolj levi operator K.

Pri petem primeru nobeden od operatorjev nima dovolj argumentov, zato ne moremo izračunati ničesar. Najbolj levi operator K ima zgolj en argument, saj je njegov "doseg" zgolj znotraj oklepajev.

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task