4. Ako sa to ráta?

Julka má veľa domácich úloh. Nebaví ju ale stále počítať komplikované príklady ručne. Rozhodla sa siahnuť po modernom pomocníkovi - kalkulačke. Zistila však, že na svojom iPade stále nemá predinštalovanú kalkulačku, ktorú by mohla použiť. Preto musela oprášiť svoju malú starú kalkulačku. Hneď pri prvom príklade ale nastal problém. Jej kalkulačka nedokáže vypočítať všetky výrazy. Viete jej pomôcť zistiť, ktoré výrazy dokáže Julka vyrátať?

Úloha

Julkina kalkulačka dokáže vykonávať iba základné operácie - sčítavanie, odčítavanie, násobenie a delenie. Ako bežná jednoduchá kalkulačka, ani táto nepodporuje zátvorky a operácie vždy vykonáva medzi posledným výsledkom a zadanou hodnotou. Teda, ak zadáme 1 + 2 =, na display-i svieti 3, pre pripočítanie čísla \(4\) stlačíme + 4 = a na display-i sa zobrazí 7.

V pamäti kalkulačky má Julka uložený nový svetový rekord počtu desatinných miest pre konštantu Pí, ktorý by bola škoda stratiť (teda pamäť kalkulačky nepoužívajte). Takisto, nemôžeme sa s medzivýsledkami spoliehať na Julkinu pamäť. Všetky operácie musia byť vykonané na kalkulačke a nesmieme si pamätať žiadne medzivýsledky “v hlave.”

Výraz je potrebné na kalkulačke vykonať tak, ako je zadaný na vstupe – teda, nemôže si ho Julka upraviť do iného tvaru, maximálne môže prehodiť poradie operandov. \(1 + 2\) môže zadať aj ako \(2 + 1\), ale napríklad \(3 + (1 - 2)\) nemôže zadať ako \(3 - (2 - 1)\), aj napriek tomu, že ide o výraz získaný ekvivalentnou úpravou.

Formát vstupu

Na vstupe sú dva riadky. V prvom riadku je číslo N - počet operácií a operandov na vstupe. V druhom riadku nasleduje N medzerou oddelených operandov (kladných celých čísiel) a operácií (+, -, *, /).

Matematické výrazy sú na vstupe zadané v tzv. prefixovom zápise (Polish notation). Na rozdiel od bežne používaného infixového zápisu, ktorý umiestňuje znamienka operácií medzi operandy (3 + 2), v prefixovom zápise ich píšeme pred operandami (+ 3 2). Napríklad 1 + 2 * 3 zapíšeme ako + 1 * 2 3. V prefixovom zápise nie je potrebné používať zátvorky, keďže poradie operácií je vždy zľava doprava: (1 + 2) * 3 zapíšeme ako * + 1 2 3.

Môžete predpokladať, že výraz na vstupe je validný.

Formát výstupu

Na výstup vypíšte ANO alebo NIE podľa toho, či dokáže Julka vyrátať zadaný výraz na svojej kalkulačke.

Hodnotenie

Sú \(4\) sady vstupov. Platia v nich nasledovné obmedzenia:

Príklady

Input:

5
+ + 1 2 3

Output:

ANO

Najprv zrátame 1 + 2, potom k výsledku pripočítame 3.

Input:

7
+ + 1 2 + 3 4

Output:

NIE

Potrebovali by sme si niekde pamätať medzivýsledok 1+2 alebo 3+4.