Dnesni zadani:
Na vstupu je boolovsky vyraz, to je vyraz, kde mate promenne a operatory.
Operator je: (), !, &, |, ->, <-> neboli zavorky, negace, konjunkce, disjunkce, implikace, ekvivalence. Priorita je dana tak, jak jsem to napsal zleva doprava. Kazdy atom (promenna nebo operator) je oddeleny zleva i zprava jednou mezerou. Promenna je posloupnost alfanumerickych znaku. Vstup je korektni. Jeste byl vstup zjednoduseny tim, ze nemusite hledet na prioritu, protoze jsou vzdy dvojice uzavorkovany. Takze se nestalo, ze by na vstupu bylo ( a & b & c ) ale ( a & ( b & c ) ).
Cely ten vyraz je v souboru, ktery prijde jako prvni parametr.
Ukolem je prevest vyraz na konjunktivni normalni formu (dale CNF) a vypsat vysledek na konzoli.
CNF je konjunkce klauzuli. Klauzule je disjunkce literalu a literal je promenna nebo jeji negace. Takze napriklad (( a & ( b | ! c)) & d). To je cele. Napsal na tabuli hinty, jak se to dela. Snad je to zhruba takhle:
~> znaci ze leva strana se nahradi za pravou
! ! a ~> a
a -> b ~> ! a | b
a <-> b ~> ( ! a | b ) & ( a | ! b )
! ( a & b ) ~> ! a | ! b
! ( a | b ) ~> ! a & ! b
( a & b) | c ~> ( a | c ) & ( b | c )
a | ( b & c ) ~> ( a | b ) & ( a | c )
CNF muze byt libovolna, nemusi byt minimalni, pouze rozumne velka (aby se to dalo kontrolovat) a muzete pocitat s prioritou, tzn. nemusi to byt uzavorkovane tak blbuvzdorne, jak na vstupu. Testovaci data dodal, ale tu stranku ted z hlavy nevim, snad to nekdo doplni.
Byly 3 hodiny casu (pokud nakonci nepridal). No a byl tam naky divny clovicek, ktereho jsem vzivote nevidel a vzhledem k tomu, ze jsem prisel pozde, tak jmeno nepovim (edit: tak pry kolega Sery
).
Ja to teda nedal, vzdal jsem po 2 hodinach, protoze jsem zvolil dost nestastne datovou strukturu a pak uz se mi to nechtelo predelavat.
Pokud si to budete zkouset, tak asi doporucuju strom. Na tom je nejtezsi to nacteni a do toho se mi nechtelo jit. Takze jsem to resil v poli, tak, ze jsem postupne rusil jednu vec za druhou. Pak jsem se ale dost zasekal a porad jeste nevim proc. Az budu mit naladu, tak si to znova proberu.
Uspesnost asi musi doplnit nekdo, kdo tam vydrzel do konce.
Hodne stesti, M.