Vyhodnoťte mi algebraický výraz! A hneď!

(Reverzná) poľská notácia zovaná tiež postfixová

(Reverzná) poľská notácia je takmer storočnou matematickou notáciou, najčastejšie používanou pre zápis algebraických výrazov. Bežný smrteľník zapisuje takéto výrazy v infixnej forme, teda operátor sa nachádza medzi operandmi. Napríklad

2 + 3 

alebo

2 * 5 + 10

alebo, s použitím zátvoriek, ktoré ujasňujú čitateľovi zápis:

(2 * 5) + 10

Pôvodnú (nereverznú) poľskú notáciu vymyslel poľský logik Jan Łukasiewicz už v roku 1924, pretože mu vyhovoval zápis, ktorý nepotreboval zátvorky a nemusel brať do úvahy priority operátorov (= pamätať si, že krát má prednosť pred plusom). Notácia bola prefixová, teda operátor sa písal pred svojimi operandmi:

V jeho ponímaní by to vyzeralo takto

+ 2 3

alebo

+ 10 * 2 5

Takýto výraz sa dá vyhodnotiť jedným prechodom zľava doprava.

Omnoho používanejšia a prehľadnejšia je reverzná poľská notácia zapisovaná v postfixovom tvare. Klasický príklad by vyzeral nasledovne:

2 5 * 10 +

Tento variant bol vynájdený nezávisle od seba viacerými ľuďmi (prvý návrh 1954, ďalšie v 60. rokoch), keď bolo treba implemenovať vyhodnocovanie výrazov v počítačoch. Z hľadiska implementácie je veľmi výhodné minimum požadovanej pamäte: na medzivýsledky postačuje jeden zásobník. V RPN možno teda vyhodnocovať výrazy takmer v „prúdovom” móde,

Napriek „prapodivnosti“ sa RPN rozšírila vo vreckových kalkulačkách: napr. HP kalkulačky to používali konzistentne už od roku 1972 (a to až do dnes). Zdatný používateľ vedel, že stačí zadať 2 a 5 a + a rovno videl výsledok; následne už len doklepol 10 a * a mal to hotové. Na webe HP je krásny príklad ako možno na RPN kalkulačke elegantne zadávať príjmy a výdaje na účte a priebežne sledovať aktuálny stav.

Rovnako sa používa v rozličných zásobníkových programovacích jazykoch: napr. v Postscripte; alebo v unixovskom klasickom nástroji dc, čo je RPN kalkulačka s ľubovoľnou presnosťou.

Len bokom: reverzná poľská notácia nemôže vzniknúť “otočením” zápisu klasickej poľskej notácie: príčinou sú nekomutatívne operátory. Pre výraz + 2 3 je reverzný zápis 3 2 +, ale pre / 6 3 by sme po reverznutí mali 3 6 /, čo dáva iný výsledok (nesprávny 0.5 voči správnej 2). Reverzná poľská notácia totiž vždy uvádza zápis v tvare

prvý_operand druhý_operand operátor

Algoritmus shunting-yard

Ukázali sme si výhodu reverznej poľskej notácie, a natíska sa otázka, ako dokážeme previesť klasický ľudský (infixný) zápis do tejto formy. Jeden z klasických algoritmov navrhol Dijkstra už v 1961 pre potreby vyhodnocovania výrazov v jazyku Algol. Nazval ho kúzelne: shunting yard, čo je názov pre zoraďovaciu stanicu (ranžír).

Železničiari používajú ranžír, čo je prakticky strom koľajníc, pri zoraďovaní vagónov do vlakov. Na začiatku koľajnicového stromu je briežok, na ktorý sa rušňom vytlačia vozne, ktoré potrebujú roztriediť. Vozeň za vozňom sa následne sa valí samospádom a železničiari ho prehadzovaním výhybiek pošlú na správnu koľajnicu. (Kto neverí, nech sa ide pozrieť na stanicu Bratislava-východ, alebo do Čiernej nad Tisou.)

Železničiarska analógia je milá v tom, že do algoritmu púšťame „vlak” s jednotlivými tokenmi algebraického výrazu a algoritmus ich postupne bude radiť v správnom poradí. Každému vozňu zodpovedá buď číslo alebo operátor.

  • Číslové vozne pošleme bez zmeny do výsledného vlakum
  • a zoraďovanie operátorov sa bude riadiť kúzelnou vlastnosťou: v RPN ich preusporiadame podľa klesajúcej priority vyhodnocovania (pričom zátvorky túto vlastnosť jemne narušujú: ale o tom potom.) Všimnime si to na príklade: 2 5 * 10 + má krát pred pluskom.

Triviálna bezzátvorková verzia

Najjednoduchšia verzia nebude používať zátvorky, a bude uznávať len binárne operátory (a i to len asociatívne zľava). Nepoužitie zátvoriek znamená, že je veľmi jednoduché dodržiavať vlastnosť neklesania operátorov. Operátory si budeme ukladať do špeciálneho zásobníka operátorov a spracované tokeny radiť do vlaku, pardon, výstupného frontu.

  1. Načítame token.

    • ak je to číslo, zaradíme ho do výstupného frontu
    • ak je to operátor O
      • vyhadzujeme postupne zo zásobníka operátorov operátory, ktoré majú prioritu vyššiu než operátor O.
      • operátor O vložíme na vrchol zásobníka operátorov
  2. Ak sme načítali všetky tokeny, postupne vyberáme operátory zo zásobníka a radíme ich do výstupného frontu.

Ukážme si to na jednoduchom príklade

2 * 5 + 10
  1. Načítame 2 a rovno ju pošleme do výstupu

    Výstup: 2

  2. Načítame * a pošleme ju do zásobníka operátorov

    Výstup: 2

    Zásobník operátorov: *

  3. načítame 5, pošleme ho do výstupu

    Výstup: 2 5

    Zásobník operátorov: *

  4. Načítame +. Zo zásobníka musíme vyhodiť operátory, ktoré majú prioritu vyššiu než +. Zatiaľ tam máme násobenie, ktoré je prioritnejšie než sčítanie, preto ho vyhodíme a vložíme tam plus.

    Výstup: 2 5

    Zásobník operátorov: +

  5. Načítame “10”, pošleme ho do výstupu

    Výstup: 2 5 * 10

    Zásobník operátorov: +

  6. Sme na konci, vyprázdnime zásobník operátorov:

    Výstup: 2 5 * 10 +

Implementácia v Jave

Naimplementovať to v Jave je otázka pár riadkov.

Tokenizácia

Budeme striktne očakávať vstup, kde jednotlivé operátory sú oddelené od čísiel medzerami. To nám umožní na tokenizáciu použiť triedu java.util.Scanner. Objekty tejto triedy fungujú ako iterátory a neskôr ich môžeme nahradiť lepšou implementáciou.

Operátory

Prioritu operátorov a budeme riešiť zoznamom operátorov, čím zároveň zabijeme aj druhú muchu jednou ranou: budeme vedieť veľmi rýchlo zistiť, či je znak operátorom alebo nie.

Pole by ušetrilo trochu pamäte, ale zase zneprehľadnilo kód: zoznamy majú totiž zabudované metódy na to, čo potrebujeme. Do úvahy by ešte pripadalo použitie reťazca “+-*/”.

private static final List<String> OPERATORS = Arrays.asList("+", "-", "*", "/");            
private boolean hasLowerOrEqualPrecedence(String operator1, String operator2) {
    int priority1 = OPERATORS.indexOf(operator1);
    int priority2 = OPERATORS.indexOf(operator2);
    return priority1 <= priority2;
}
 
private boolean isOperator(String token) {
    if(token.length() > 1) {
        throw new IllegalStateException("Token " + token + " is illegal.");
    }
    return OPERATORS.contains(token);
}

Detekcia čísla

Detekciu čísla zrealizujeme variantom metódy parseDouble(). Miesto vyhodenia výnimky budeme vracať booleovskú hodnotu.

private boolean isNumber(String token) {
    try {
        Double.parseDouble(token);
        return true;
    } catch (NumberFormatException e) {
        return false;
    }
}

Dátové štruktúry

Výstupný front môžeme zareprezentovať jednoduchým zoznamom (napr. typu LinkedList), kde pridávanie na koniec frontu zrealizujeme tradičnou metódou add().

Zásobník operátorov môžeme realizovať dvoma spôsobmi: buď použiť „zjavnú” triedu java.util.Stack, alebo využiť novšie API poskytujúce double ended queue (deque; front o dvoch koncoch) v role zásobníka.

Odporúčam použiť druhý prístup: klasický Stack totiž vyhadzuje v prípade prázdneho zásobníka pri metódach peek() a pop() nepríjemné výnimky, ktoréo treba odchytávať. Na druhej strane sa Deque správa elegantnejšie a pri prázdnom zásobníku vracia nully.

Jadro

Jadrom bude metóda parse(), ktorá zoberie na vstup reťazec podľa vyššieuvedených požiadaviek a vráti zoznam tokenov v poradí podľa RPN.

public List<String> parse(String expression) {
    Scanner expressionScanner = new Scanner(expression);
 
    List<String> outputQueue = new LinkedList<String>();
    Deque<String> operatorStack = new LinkedList<String>();
 
    while(expressionScanner.hasNext()) {
        String token = expressionScanner.next();
        if(isNumber(token)) {
            outputQueue.add(token);
            continue;
        }
        if(isOperator(token)) {
            String stackTop;
            while((stackTop = operatorStack.peek()) != null) {
                if(hasLowerOrEqualPrecedence(token, stackTop)) {
                    operatorStack.pop();
                    outputQueue.add(stackTop);
                } else {
                    // na vrchole zásobníka je už operátor s nižšou prioritou,
                    // nepokračujeme.
                    break;
                }
            }
            operatorStack.push(token);      
        }
    }
    // dočítali sme vstup, vyprázdnime zásobník
    while(!operatorStack.isEmpty()) {
        outputQueue.add(operatorStack.pop());
    }
    return outputQueue;
}

Nabudúce vylepšíme tento algoritmus o podporu zátvoriek! Zatiaľ si stiahnite zdrojový kód aktuálnej verzie.

Pridaj komentár

Vaša e-mailová adresa nebude zverejnená. Vyžadované polia sú označené *