V minulom dieli sme si urobili jednoduchý parser algebraických výrazov založený na Dijkstrovom železničiarsko-posunovačskom algoritme shunting yard. Pre jednoduchosť sme však vynechali podporu zátvoriek. Bez nich je to však dosť ťažké a to hlavne v kilometrových výrazoch, preto to napravme. V januári 2012 koloval Facebookom test gramotnosti národa

9 + 0 + 9 + 0 + 9 * 0 + 9

Výsledkom bol festival komentárov:

NULA !! :D ale dobrej chyták pro blondýny :D :D :D

Vy lopaty, je to jednoduché 27×9, ktery ko**t přišel na to, že přednost ma krát, drž se

výsledok je 9 .. lebo HOCIČO KRÁT NULA JE NULA !!! To pre tých, čo nechodili na základku :DDD

Nevím, jestli ti, kteří napsali, že výsledek je nula nebo 27 jsou mentálně zavostalí, nebo si dělali prdel, každopádně výsledek je 9

Nešťastný národ obvykle vyhodnocoval výraz zľava doprava. Keby používali shunting yard, alebo aspoň zátvorky, nedajbože reverznú poľskú notáciu, výsledok by bol jasnejší.

Nejeden skutočný znalec matematiky vie, že prehľadnejšie by to vyzeralo takto:

9 + 0 + 9 + 0 + (9 * 0) + 9

čo je, prirodzene, 27. V RPN je výraz nasledovný

9 0 + 9 + 0 + 9 0 * + 9 +

Pridajme teda podporu zátvoriek

Dijkstra v minulom dieli pozoroval, že po prepise výrazu do reverznej poľskej notácie sú operátory v zásobníku uvedené v opačnom poradí podľa priority. Popri tom si tiež všimol (a my si to všimneme spolu s ním), že zátvorky odtieňujú výraz od „okolitého sveta”. Dohromady to znamená, že operátory na zásobníku už nemusia byť v globálnom v klesajúcom (presnejšie nerastúcom ;-) poradí, ale táto vlastnosť bude i naďalej platiť pre operátory v rámci jedného zátvorkového bloku.

Ak pôjdeme vyhodnocovať jemne modifikovaný príklad z minula

10 + (2 * 5)

tak je očividné, že na to, aby sme mohli spracovať celý súčet, musíme vyhodnotiť obsah súčinu v zátvorke. Inými slovami, na sčítanie môžeme v tomto príklade zabudnúť až do chvíle, kým nevyhodnotíme vnútro zátvoriek.

Samotná modifikácia algoritmu nie je až taká náročná — do rozhodovania stačí dodať pár vetiev. Ľavú zátvorku budeme považovať za špeciálny operátor s extrémne nízkou prioritou (a budeme ju pchať do zásobníka operátorov podľa klasickýh pravidiel). Jej pravú formu budeme považovať za špeciálny prípad — povieme si o ňom o sekundu.

• ak načítaný token je ľavá zátvorka (, vložíme ju na zásobník. (Tu sa prejavuje zákon nízkej priority zátvorky: keďže žiaden operátor nemá nižšiu prioritu než ona, nikdy nebudeme pred jej vložením zo zásobníka vyhadzovať iné operátory).
• ak je načítaný token pravá zátvorka 0, indikuje to ukončenie aktuálneho uzátvorkovaného bloku.
  1. V takom prípade vyberajme postupne operátory zo zásobnika a presúvame ich do výstupného frontu až do chvíle, kým sa na vrchole zásobníka neocitne ľavá zátvorka (.
  2. Vyberme i ľavú zátvorku, ale do výstupného frontu ju nedávame. (RPN totiž neuznáva zátvorky!)
  3. Ak nedajturing zistíme, že sme pri vyberaní operátorov narazili na spodok zásobníka, znamená to nesprávne uzátvorkovanie. V tomto prípade môžeme rovno skončiť chybou.

Potrebujeme ešte zmeniť jednu vec: a to správanie na konci algoritmu, po dočítaní všetkých dát zo vstupu. V jednoduchej verzii to vyzeralo tak, že sme len postupne presunuli operátory zo zásobníka do výstupného frontu. Tu to bude temer také isté: rozdiel bude v tom, že …

• ak narazíme pri vyprázdňovaní zásobníka na ľavú zátvorku, znamená to zlé uzátvorkovanie a končíme chybou.

Takýto príklad ľahko nastane v prípade hlúpeho vstupu

2 + (

Podľa vyhodnocovania vložíme 2 do výstupnej fronty. Následne zoberieme +. Zásobník je prázdny a teda niet čo vyhadzovať, a teda plusko vložíme na jeho vrchol. Nasleduje ľavá zátvorka, ktorú rovno vložíme do zásobníka a základe prvého bodu. Vstup sme dočítali a čo sa stalo? Zásobník vyzerá nasledovne

+ ( 

Je koniec vstupu; vyprázdňujeme zásobník. Hneď prvý operátor je ľavá zátvorka, čo je zlé — vyhadzujeme výnimku a končíme.

Implementácia v Jave

Implementácia je jednoduchá: mechanicky prepíšeme príslušné vetvy v podmienkach do kódu:

if("(".equals(token)) {
    operatorStack.push(token);
}
if(")".equals(token)) {
    String stackTop;
    // príznak nájdenia zodpovedajúcej ľavej zátvorky
    boolean foundMatchingBrace = false;
    while((stackTop = operatorStack.peek()) != null) {
        if("(".equals(stackTop)) {
            // našli sme ľavú zátvorku, končíme vyhadzovnaie
            operatorStack.pop();
            foundMatchingBrace = true;
            break;
        } else {
            // vyhadzujeme operátory do výstupného frontu
            outputQueue.add(operatorStack.pop());
        }                       
    }
    // vyčerpali sme zásobník bez nájdenia `(`, syntaktická chyba.
    if(!foundMatchingBrace) {
        throw new ParseException("Mismatched right brace ')'.");
    }
}

Vyprázdňovanie zásobníka po dočítaní vstupu je takmer také isté: zoberieme do úvahy zle spárované zátvorky.

while(!operatorStack.isEmpty()) {
    String operator = operatorStack.pop();
    if("(".equals(operator)) {
        throw new ParseException("Mismatched left brace ')'.");
    }
    outputQueue.add(operator);
}

Ešte drobnosť: výnimka ParseException je naša vlastná a takmer už nemôže vyzerať jednoduchšie.

public static class ParseException extends Exception {
    public ParseException() {
        super();
    }
    public ParseException(String message, Throwable cause) {
        super(message, cause);
    }
    public ParseException(String message) {
        super(message);
    }
    public ParseException(Throwable cause) {
        super(cause);
    }
}

Kompletný finálný kód si môžete stiahnuť v separátnom súbore. Keďže kód má veľký počet pestrých vstupov a možných výstupov, je viac než vhodné vytvoriť k nemu unit test (pre JUnit), ktorý si môžete tiež stiahnuť zo samostatného súboru.