I digitala konstruktioner förekommer det ofta olika typer av logiska
uttryck, t ex
/MEME = /AS + A5 + /A6 + /A7
vilket betyder att signalen MEME blir aktiv då signalerna AS,A6 och
A7 är logiskt låga (noll) och A5 är logiskt hög (ett).
Att det står '/' framför betyder alltså att aktiv är
noll och inaktiv är ett.
Ovanstående formel är ganska lätt för oss människor
att förstå, men om man skall implementera den i ett chip är
det inte helt självklart hur man skall gå till väga. Ett
sätt är att använda programmerbar logik, t ex sk FPGA:er.
För att de skall vara så flexibla som möjligt så brukar
man konstruera dem med hjälp av sk lookup-tabeller. Det betyder att
man tar antalet insignaler och konstruerar en tabell som har 2(antalet signaler)
celler. Sedan placerar man en 0:a eller 1:a i cellerna och på så
sätt kan man bestämma utsignalen för varje insignalkombination.
Det finns många sätt att beskriva en sådan tabell. Ett
sätt är att skriva upp den som sk mintermer. Då skriver
man upp alla insignaler som ger 1 på formen: aBCdE etc. Att bokstaven
är stor betyder att signalen måste vara hög (1) och att
bokstaven är liten betyder att signalen måste vara låg
(0). I detta exempel betyder det alltså att om signalerna a och d
är 0 medan b, c och e är 1 så blir utsignalen 1. Om det
finns flera kombinationer som ger en 1:a ut så skriver man upp dem
efter varandra, t ex: aB|Ab betyder att både a=0,b=1 och a=1,b=0 ger
utsignalen 1 medan resten av kombinationerna (a=0,b=0 och a=1,b=1) ger utsignalen
0.
Er uppgift blir ett skriva ett program som läser in ett logiskt uttryck
och skriver ut det min-termuttryck som beskriver det inlästa uttrycket.
De logiska uttrycken består av bokstäverna a-e samt tecknen &
| ( ) ! där & betyder logiskt och, | betyder logiskt eller och
! betyder logiskt icke. En begränsning finns vad gäller de logiska
uttrycken p; ! får endast vara unär operator till en bokstav,
dvs !(a&b) är ett otillåtet logiskt uttryck. Mintermuttrycket
skall endast bestå av samma bokstäver som fanns i det inlästa
logiska uttrycket. Bokstäverna i ett deluttryck (av ett mintermuttryck)
skrivs i bokstavsordning (där både A och a anses vara mindre
än B osv). Om uttrycket skulle visa sig reduceras till ett konstant
värde så skall dock bara resultatet skrivas ut (dvs 0 eller 1).
Indata:
Första raden anger antalet testfall programmet skall behandla (N).
Därefter följer de N testfallen med ett testfall (logiskt uttryck)
per rad. Det finns inget logiskt uttryck som består av mer än
80 tecken, samt så förekommer det inga blanktecken i de logiska
uttrycken.
Utdata:
Skall bestå av N rader, en för varje testfall i form av ett mintermuttryck.
Det får inte förekomma några blanktecken i mintermuttrycken,
och de ingående deluttrycken i ett mintermuttryck skall sinsemellan
vara sorterade i växande (ASCII-)ordning.
Exempel:
Indata:
5 a|b|c a&b&c a&(b|c) (a|!a)&(b|!b) a&(b|!b)
Utdata:
ABC|ABc|AbC|Abc|aBC|aBc|abC ABC ABC|ABc|AbC 1 AB|Ab