Labb 9: Formelkoll

I denna labb ska du

• Skriva ett program som läser in molekylformler och kontrollerar om dom är syntaktiskt korrekta, med hjälp av rekursiv medåkning.

Förberedelser

1. Läs instruktionerna i Kattis för problemet formelkoll Links to an external site..
2. Skriv ett testprogram med unittest Links to an external site. för den första omgången med testdata (Sample Input 1/Sample Output 1).
3. Skriv ett testprogram för den andra omgången med testdata (Sample Input 2/Sample Output 2).

Introduktion

Molekylformler beskriver hur molekyler är uppbyggda. Molekylformler kan innehålla atomer, parenteser och siffror, exempelvis H2O (vatten) eller Ba(NO3)2 (bariumnitrat).

Uppgift

Din uppgift är att utföra en syntaxanalys på indata. Du ska läsa in en sträng från standard input och sedan tala om ifall formeln är syntaktiskt korrekt eller inte. Om den inte är korrekt ska du även skriva ut vad som är fel och var i formeln felet uppstod.

Till din hjälp får du nedan en BNF-syntax för molekylformler och en lista med atomer. Observera att alla atomer som finns med i listan räknas som korrekta. (Atomer som inte finns med i periodiska systemet räknas som inkorrekta men du behöver inte implementera alla atomer). Använd lämpligen rekursiv medåkning.

BNF-syntax

<formel>::= <mol> \n
<mol>   ::= <group> | <group><mol>
<group> ::= <atom> |<atom><num> | (<mol>) <num>
<atom>  ::= <LETTER> | <LETTER><letter>
<LETTER>::= A | B | C | ... | Z
<letter>::= a | b | c | ... | z
<num>   ::= 2 | 3 | 4 | ...

Här är en lista på godkända atomer. Hårdkoda den i programmet. Tips: kopiera in alla atomerna i en sträng och använd split() för att få en lista.

H   He  Li  Be  B   C   N   O   F   Ne  Na  Mg  Al  Si  P   S   Cl  Ar  K   Ca  Sc  Ti  V   Cr
Mn  Fe  Co  Ni  Cu  Zn  Ga  Ge  As  Se  Br  Kr  Rb  Sr  Y   Zr  Nb  Mo  Tc  Ru  Rh  Pd  Ag  Cd
In  Sn  Sb  Te  I   Xe  Cs  Ba  La  Ce  Pr  Nd  Pm  Sm  Eu  Gd  Tb  Dy  Ho  Er  Tm  Yb  Lu  Hf
Ta  W   Re  Os  Ir  Pt  Au  Hg  Tl  Pb  Bi  Po  At  Rn  Fr  Ra  Ac  Th  Pa  U   Np  Pu  Am  Cm
Bk  Cf  Es  Fm  Md  No  Lr  Rf  Db  Sg  Bh  Hs  Mt  Ds  Rg  Cn  Fl  Lv

Indata

Programmet ska läsa in en eller flera rader från standard input. Varje rad ska representera en (korrekt eller inkorrekt) formel. Inläsningen ska avslutas då tecknet # hittas.

Utdata

För varje rad programmet har läst in (utom raden med $\mathrm{\#}$) ska programmet berätta om formeln var syntaktiskt korrekt eller vilket fel som hittades. Om formeln innehöll flera fel ska bara det första felet skrivas ut. Var noga med att skriva output på exakt samma format som visas i exemplen nedan.

Sample Input 1/Sample Output 1

Na                     Formeln är syntaktiskt korrekt 
H2O                    Formeln är syntaktiskt korrekt 
Si(C3(COOH)2)4(H2O)7   Formeln är syntaktiskt korrekt 
Na332                  Formeln är syntaktiskt korrekt 
#

Sample Input 2/Sample Output 2

C(Xx4)5    Okänd atom vid radslutet 4)5
C(OH4)C    Saknad siffra vid radslutet C
C(OH4C     Saknad högerparentes vid radslutet
H2O)Fe     Felaktig gruppstart vid radslutet )Fe
H0         För litet tal vid radslutet
H1C        För litet tal vid radslutet C
H02C       För litet tal vid radslutet 2C
Nacl       Saknad stor bokstav vid radslutet cl
a          Saknad stor bokstav vid radslutet a
(Cl)2)3    Felaktig gruppstart vid radslutet )3
)          Felaktig gruppstart vid radslutet )
2          Felaktig gruppstart vid radslutet 2
#

Ditt program ska läsa formeln tecken för tecken och med rekursiv medåkning kolla syntaxen. Rekursiv medåkning innebär att huvudprogrammet först gör anropet readformel(), varefter readformel() anropar readmol() som anropar readgroup() och sedan eventuellt sej själv (men inte om inmatningen är slut eller om den just kommit tillbaka från ett parentesuttryck).

Funktionen readgroup() anropar antingen readatom() eller läser en parentes och anropar readmol() etc - allt enligt grammatiken. När ett syntaxbrott upptäcks genereras en exception (raise Syntaxfel("Saknad högerparentes")) som fångas i huvudprogrammet och där skrivs hela resten av indataraden ut.

Man måste ofta tjuvtitta på nästa tecken i kön (med peek()) för att veta vilken gren man ska följa i syntaxträdet.

Testning

Kattis kommer troligen att klaga på ditt program. Använd de två unittesterna du skrev i förberedelserna ovan för att kontrollera om programmet fungerar för de två givna omgångarna testdata.

Förutom de två givna omgångarna med testdata kör Kattis många andra tester. Du måste själv hitta på egna tester, och testa med dom för att ditt program ska bli tillräckligt bra för att godkännas av Kattis. Lägg till dina nya tester i unittest-programmet.

Betyg

Denna labb kan endast ge betyg E. Du måste lämna in den och redovisa den i tid för att få göra labbarna för högre betyg i period 2.

Redovisning

Labben lämnas in indivuellt med "Lämna in uppgift"-knappen högst upp på sidan, och ska redovisas muntligt av bägge gruppmedlemmarna. Skriv gruppmedlemmarnas namn i kommentarsfältet!

Vid redovisningen ska du kunna

• Visa godkänd kattisinskickning
• Beskriva hur rekursiv medåkning fungerar
• Visa hur dina funktioner speglar den givna syntaxen
• Visa ditt unittest-program