Automaadid, keeled ja translaatorid 2017/18 kevad

HtmlStrip

Meie eesmärk on kirjutada meetod, mis eemaldab kujunduskäske (tags) HTML dokumendist. Proovime kõigepealt siis kirjutada selline meetod, mis kõige lihtsama sisendi puhul töötab:

• Sisend: <b>foo</b>
• Eeldatav väljund: foo

Meetodi signatuur võiks olla järgmine:

public class HtmlStrip {
    public static String removeHtmlMarkup(String s) {
        StringBuilder sb = new StringBuilder();
        // TODO: midagi peaks ilmselt tegema.
        return sb.toString();
    }
}

Kirjutame kohe ka esimene test:

public class HtmlStripTest {
    @Test
    public void testRemoveHtmlMarkup() throws Exception {
        check("foo", "<b>foo</b>");
    }

    public void check(String expected, String input) {
        assertEquals(input, expected, HtmlStrip.removeHtmlMarkup(input));
    }
}

Esimene katse

Idee võiks olla selline, et loeme tähthaaval sisendit ja me lihtsalt kopeerime seda väljundisse (echo). Kui aga näeme märki <, siis lähme ignoreerimise režiimi. Seda ideed võib joonistada olekumasinana, mille põhjal saame järgmist koodi:

public static String removeHtmlMarkup(String s) { StringBuilder sb = new StringBuilder(); boolean tag = false; for (char c : s.toCharArray()) { if (c == '<') { tag = true; } else if (c == '>') { tag = false; } else if (!tag) { sb.append(c); } } return sb.toString(); }

NB! Implementatsioon on pisut vigane, nimelt sisendi <b>f>5</b> puhul peaks väljund olema f>5, aga programm annab teise vastuse. Olekumasin (paremal) on siiski korrektne, seega ei tohiks liiga raske olla seda viga parandada. Palun tee seda! Nii, väga hea, aga meil on kahjuks suurem mure: <a href='>'>foo</a>. Selle sisendi jaoks on ka olekumasin vigane!

Teine katse

Meil oleks uut olekut vaja, et vältida seda probleemi, kui sõnede sees esineb '>'. Kõigepealt lisame vajalike teste, sest meile ei meeldi pimedas programmeerida:

    @Test
    public void testRemoveHtmlMarkupWithQuotes() throws Exception {
        check("foo", "<a href='>'>foo</a>");
    }
    @Test
    public void testRemoveHtmlMarkupWithJustQuotes() throws Exception {
        check("'foo'", "'<b>foo</b>'");
        check("'foo'", "'foo'");
    } 

Nüüd joonistame uue automaadi ja kirjutame ka sellele vastav kood:

public static String removeHtmlMarkup(String s) { StringBuilder sb = new StringBuilder(); boolean tag = false; boolean qte = false; for (char c : s.toCharArray()) { if (c == '<' && !qte) { tag = true; } else if (c == '>' && tag && !qte) { tag = false; } else if (c == '\'' && tag) { qte = !qte; } else if (!tag) { sb.append(c); } } return sb.toString(); }

Ma ei ole veel päris kindel...

See kood arenes üsnagi katse-eksitus meetodil. Ma ei tea, mis ta täpselt teeb, sest need kõrvaltingimused on päris keerulised. Me peame sõltuvalt sisendist ja automaadi olekust mingi otsuse tegema. Siiamaani oleme põhiliselt sisendi järgi hargnenud ja siis oleku peale mõelnud. Kirjutame nüüd aga rohkem olekumasina vaatevinklist:

public static String removeHtmlMarkup(String s) { final int INI = 0; final int TAG = 1; final int QTE = 2; StringBuilder sb = new StringBuilder(); int state = INI; for (char c : s.toCharArray()) { switch (state) { case INI: if (c == '<') state = TAG; else sb.append(c); break; case TAG: if (c == '>') state = INI; if (c == '\'') state = QTE; break; case QTE: if (c == '\'') state = TAG; break; } } return sb.toString(); }

Selle implementatsiooni suur eelis on see, et on palju kergem veenduda, et kood vastab mudelile. Eelmine lahendus läbib ka minu teste, aga kes teab... Viimase koodi suhtes olen palju optimistlikum! Samas, alati ei pruugi oleku järgi hargnemine olla kõige mugavam. Kodutöö on näiteks selline, kus minu jaoks oli mugavam sisendi järgi ikkagi hargneda. Alati on aga abiks olekumasina välja joonistamine paberil!

Kodutöö soojendus

Kirjutame siin ülaloleva koodi ümber kodutööle sobivas formaadis. Toome ka selline lahenduse, kus hargneme põhiliselt tähtede järgi (nii on kodutöös mugavam), aga ikkagi on kasutatud paberil joonistatud automaati, et paremini aru saada toimuvast. Kodutööga analoogselt tuleb implementeerida klass StripMachine, millel on meetod process ja raamistik hoolitseb selle eest, et tähthaaval sisendit sellele sööta:

    private static String cleanUp(String s) {
        StringBuilder sb = new StringBuilder();
        StripMachine machine = new StripMachine();
        for (char c : s.toCharArray()) sb.append(machine.process(c));
        return sb.toString();
    }

Kui olekumasina joonist vaadata, siis on selge, et väljastamine toimub ainult algseisundis, kui sisendtäht ei ole <, seetõttu võime kõigepealt otsustada, kas on vaja midagi väljastada või mitte. Me peame seda kohe algul otsustama, kuna seisund võib pärast muutuda. Salvestame otsuse tulemust muutujas echo. Ülejäänud loogika on üsna otse joonise pealt tulnud:

public class StripMachine { enum States { INI, TAG, QTE, DQT } private States state = INI; public String process(char c) { boolean echo = state == INI; switch (c) { case '<': if (state == INI) state = TAG; return ""; // Seda ei väljastata! case '>': if (state == TAG) state = INI; break; case '\'': if (state == QTE) state = TAG; else if (state == TAG) state = QTE; break; } return echo ? Character.toString(c) : ""; } }

Sinu kord

Võiks proovida, et ka tavaliste jutumärkidega töötaks. Siis peab olema nii, et kui alustame ühte tüüpi jutumärkidega, siis lõpetame ainult sama tüüpi jutumärgiga: "John's" ja 'Ta ütles, "Tere!"'. Vajalikud testid on failis StripMachineTest.java.